Fragments
A Collection of Statements, kinda
Algorighm for ordering of priorities?
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Fragments Forum Index -> General
View previous topic :: View next topic  
Author Message
fuoco



Joined: 04 Feb 2005
Posts: 4

Reply with quote

PostPosted: 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?
Back to top
View user's profile Send private message
martin
Site Admin


Joined: 19 Jan 2004
Posts: 455
Location: In the middle of Sweden

Reply with quote

PostPosted: Fri Feb 04, 2005 8:47 am    Post subject:

Fuoco,

I think this problem is equivalent to "the travelling salesman" problem, which is an NP-complete 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!
Back to top
View user's profile Send private message Send e-mail Visit poster's website
martin
Site Admin


Joined: 19 Jan 2004
Posts: 455
Location: In the middle of Sweden

Reply with quote

PostPosted: Fri Feb 04, 2005 8:52 am    Post subject:

nevelsteen wrote:
If you sort the entire list of tasks according to importance value (a priority queue) then adding the top values will always leave you with the highest sum.

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?
Back to top
View user's profile Send private message Send e-mail Visit poster's website
martin
Site Admin


Joined: 19 Jan 2004
Posts: 455
Location: In the middle of Sweden

Reply with quote

PostPosted: 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...
Back to top
View user's profile Send private message Send e-mail Visit poster's website
fuoco



Joined: 04 Feb 2005
Posts: 4

Reply with quote

PostPosted: 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.
Back to top
View user's profile Send private message
fuoco



Joined: 04 Feb 2005
Posts: 4

Reply with quote

PostPosted: Mon Feb 07, 2005 7:54 am    Post subject:

Quote:
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.


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:

Code:
[T1] ---> [T2] ----> [T2]
 |  2            3    |
 |                    |
 |_________>__________|
      4
   


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.
Back to top
View user's profile Send private message
martin
Site Admin


Joined: 19 Jan 2004
Posts: 455
Location: In the middle of Sweden

Reply with quote

PostPosted: 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?
Back to top
View user's profile Send private message Send e-mail Visit poster's website
martin
Site Admin


Joined: 19 Jan 2004
Posts: 455
Location: In the middle of Sweden

Reply with quote

PostPosted: 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.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
martin
Site Admin


Joined: 19 Jan 2004
Posts: 455
Location: In the middle of Sweden

Reply with quote

PostPosted: 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.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
fuoco



Joined: 04 Feb 2005
Posts: 4

Reply with quote

PostPosted: 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!
Back to top
View user's profile Send private message
ac



Joined: 19 Jan 2004
Posts: 25
Location: Location: Location:!

Reply with quote

PostPosted: 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.
Back to top
View user's profile Send private message Visit poster's website
martin
Site Admin


Joined: 19 Jan 2004
Posts: 455
Location: In the middle of Sweden

Reply with quote

PostPosted: Wed Mar 09, 2005 10:07 am    Post subject:

I was going to reply to this, but I got two other things to do.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
ac



Joined: 19 Jan 2004
Posts: 25
Location: Location: Location:!

Reply with quote

PostPosted: 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.
Back to top
View user's profile Send private message Visit poster's website
martin
Site Admin


Joined: 19 Jan 2004
Posts: 455
Location: In the middle of Sweden

Reply with quote

PostPosted: 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...".
Back to top
View user's profile Send private message Send e-mail Visit poster's website
ac



Joined: 19 Jan 2004
Posts: 25
Location: Location: Location:!

Reply with quote

PostPosted: Wed Mar 09, 2005 3:35 pm    Post subject:

Of course, either of us could be algowrong.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Fragments Forum Index -> General All times are GMT + 1 Hour
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
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


Powered by phpBB © 2001, 2005 phpBB Group
Theme created by K.Nevelsteen