Home • Profile • Private Messages • Usergroups • Memberlist • Search • FAQ • Log in • Register 
Fragments A Collection of Statements, kinda 
Algorighm for ordering of priorities? Goto page 1, 2 Next 
Author  Message  

fuoco Joined: 04 Feb 2005 Posts: 4 
Posted: Fri Feb 04, 2005 7:19 am Post subject: Algorighm for ordering of priorities? There is a list of tasks to be done. There is a list of priorities, in the format {1} [task1] must be done before [task2] with importance 5 {2} [task2] must be done before [task3] with importance 3 {3} [task3] must be done before [task1] with importance 2 The algorithm must order tasks in such order so that the sum of the realized priorities to be maximal. For example here we can order tasks in this order [task1], [task2], [task3]. In this case priorities {1} and {2} will be realized. The sum of their importances is 5+3 = 8, which is the best way to order. How to make a program to find the best way to order tasks? 

martin Site Admin Joined: 19 Jan 2004 Posts: 455 Location: In the middle of Sweden 
Posted: Fri Feb 04, 2005 8:47 am Post subject: Fuoco, I think this problem is equivalent to "the travelling salesman" problem, which is an NPcomplete problem (i.e. you're not guaranteed to ever find the optimal solution, but of course there's a strategy to find candidate solutions). Maybe look into "priority queues", that is a binary organized heap (the reference to where it's described escapes me right now), but only as part of the implementation. In any case, I'll have to think about this for a while. I'm sure it's going to keep me awake... if you find a solution before me, I'd love to see it! 

martin Site Admin Joined: 19 Jan 2004 Posts: 455 Location: In the middle of Sweden 
Posted: Fri Feb 04, 2005 8:52 am Post subject:
As I understood it, you only "get" the points if the order is realized. So the sum won't contain the points for the tasks that are out of order. Huh... wasn't much clearer, was it? 

martin Site Admin Joined: 19 Jan 2004 Posts: 455 Location: In the middle of Sweden 
Posted: Sun Feb 06, 2005 10:30 am Post subject: Fuoco, So, I've been thinking... First, the problem is a directed cyclic graph that needs to be transformed to a directed acyclic graph (DAC). This is the same problem as "the travelling salesman problem", also called TSP. Except that the TSP has as target to minimize the cost, that is, the sum of the remaining edges. If you now change the "priority" to "cost", for instance by taking cost = (1 / priority), you then have to minimize the total of the cost. As far as I can see, this is then exactly the same as the TSP, which has been described in hundreds of articles. And no, I don't have a simple solution to the TSP I can give, not that I can remember anyway. You need to read up on it, I'm afraid. A little caveat: I'm only 99% sure it's exactly equivalent to the TSP. So please don't murder me if you discover it wasn't so after spending 6 weeks reading up on the litterature... 

fuoco Joined: 04 Feb 2005 Posts: 4 
Posted: Sun Feb 06, 2005 5:21 pm Post subject: Martin, 10x very much for the help! I will search for a solution and if i find one, I will post it. 

fuoco Joined: 04 Feb 2005 Posts: 4 
Posted: Mon Feb 07, 2005 7:54 am Post subject:
I've been thinking and I saw that the travelling salesman problem is not the same as priority problem. The salesman must find only one route, but here we must calculate also all parallel routes. See the scheme:
Here if we order the points in the order [T1], [T2], [T2] the Travelling salesman algorithm will return lenght 2 + 3 = 5 because it is the shortest way, but if we consider points as tasks for execution, we see that the priority with importance 4 is also realized like these with importance 2 and 3, so the sum is 2 + 3 + 4 = 9. The problem is not only to find a route in the graph, but to find all parallel routes that can be passed after ordering the tasks and the sum of these routes to be maximal. 

martin Site Admin Joined: 19 Jan 2004 Posts: 455 Location: In the middle of Sweden 
Posted: Mon Feb 07, 2005 9:13 am Post subject: Fuoco, You're right, I missed that difference entirely. Time for more thinking... Being entirely simplistic, what happens if you start with assigning each node the sum of all outgoing edges (sum of all priorities if it came first), then picking out the node with the maximum sum as first. Then repeating with the remaining nodes. I assume you've tried. Does it select suboptimal results, or is is simply hard to prove that it's optimal? 

martin Site Admin Joined: 19 Jan 2004 Posts: 455 Location: In the middle of Sweden 
Posted: Mon Feb 07, 2005 9:54 am Post subject: Modification to the previous: Assign each node a value equal to the sum of all outgoing priorities minus the sum of all incoming priorities. Then select the node with the highest value and place it first. Repeat with the remainders until empty. 

martin Site Admin Joined: 19 Jan 2004 Posts: 455 Location: In the middle of Sweden 
Posted: Mon Feb 07, 2005 10:17 am Post subject: Fuoco, I've found a journal for you: "Journal of Experimental Algorithmics" (JEA), from the ACM. If you go to www.acm.org, digital library, you'll find it. At the very least, you can browse the titles and abstracts. It almost seems as if it's the "journal of travelling saleman and similar problems"... The problem now is to find out what your problem actually is called in academia, else you have to read all those articles. On the other hand, this journal is published once a year, so it's not that much to check out. To actually read the articles, you must be a member of the ACM. Maybe you can get access through a university. Else, if there is some abstract or title that strikes you as likely, I can check it out for you, since I do subscribe to their library. 

fuoco Joined: 04 Feb 2005 Posts: 4 
Posted: Thu Mar 03, 2005 9:22 am Post subject: Thank you Martin for the help, your second suggestion is efficient in most cases, but not always. Therefore I used another algorithm parallelly with this, based on sorting the priority list and executing them in descending order when possible. Finally the better result of the two algorithms is displayed. The results are very good, and what is most important the time is acceptable. 10x again for the efforts! 

ac Joined: 19 Jan 2004 Posts: 25 Location: Location: Location:! 
Posted: Sun Mar 06, 2005 7:12 pm Post subject: An alternative view. Now that this topic is resolved, perhaps it is appropriate to insert my own priority optimization algorithm. Generally, with priorities > n, where n=2, priorities n+1 ... n+n2 won't happen. This, of course, is an empirical assertion straight out of General Systems theory, and, like Euclid's 5th (or indeed Beethoven's or Jack Daniel's) may not readily succumb to mathematical proof. 

martin Site Admin Joined: 19 Jan 2004 Posts: 455 Location: In the middle of Sweden 
Posted: Wed Mar 09, 2005 10:07 am Post subject: I was going to reply to this, but I got two other things to do. 

ac Joined: 19 Jan 2004 Posts: 25 Location: Location: Location:! 
Posted: Wed Mar 09, 2005 3:21 pm Post subject: I can understand the pressure you're under. By the way, what's an "algorighm"? Is it related to an algolrhythm? I use those a lot in my music. They sound a lot like ancient mainframes straining to execute primordial structured code. 

martin Site Admin Joined: 19 Jan 2004 Posts: 455 Location: In the middle of Sweden 
Posted: Wed Mar 09, 2005 3:29 pm Post subject: No, it's derived from "algoright", once you get it just so. But the stage before is commonly called "algorighm"; a contraction of "algoright" and "um...". 

ac Joined: 19 Jan 2004 Posts: 25 Location: Location: Location:! 
Posted: Wed Mar 09, 2005 3:35 pm Post subject: Of course, either of us could be algowrong. 


All times are GMT + 1 Hour 

You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum 