Just another Perl shrine | |
PerlMonks |
Re: Priority Sorting Challengeby kvale (Monsignor) |
on Jun 01, 2004 at 16:00 UTC ( [id://358165]=note: print w/replies, xml ) | Need Help?? |
As Abigail-II says, a topological sort is the right algorithm to use if all you have are a set of dependencies to satisfy. If you also have some sort of importance metric on top of the dependencies, the problem is a little harder.
The topological sort will produce a forest, i.e. a set of dependency trees. Among those trees you will find one containing your most important task. Follow the tree back to the root and execute those tasks needed for the most important task. Mark all these tasks as 'done' and find the next most inportant undone task and repeat the procedue, etc. If there are equal priorities, just pick one randomly or create another criterion that breaks the symmetry. For a circular dependency, there is not much to be done, except to restructure your tasks. It is a pathological case and there is no valid solution as far as the computer is concerned. -Mark
In Section
Seekers of Perl Wisdom
|
|