8 replies to this topic

[debp]

Hey,

I have the following problem:
I have a cyclic weighted graph (the graph is one big cycle) with N nodes (in the picture, there are 4 nodes); Node 1 being the starting node.
In the picture you can see blue numbers, which represent a point in time where an event occurs. Events always occur regularly (e.g.: 10,20,30... or 21,42,63 ...)
My agent has to "catch" all events (either going to a specific node and then waiting, or arriving simultaneously) and starts at time 0 at the starting node.
The red numbers are the weights (time to travel from one node to another).

The question/problem:

I need an algorithm that outputs the optimal way.
Optimal way = You have to "catch" all events and use the shortest time possible.

The problem is, I can only think of an algorithm that goes through all possible ways (e.g. Nodes 2-3-4, 2-4-3, 3-2-4, ...), but that's factorial (ouch).
Can anyone help me with my problem? Maybe you know a common algorithm that does something similar?
Well, any thoughts are appreciated.

P.S.: The purple numbers in the picture are all possibilities with their time they need (e.g. 2-3-4 and 3-2-4 only need 40 time units).

P.P.S.: One example (for the 2-3-4 possibility):
- Agent is at Node 1 at time 0
- Agent goes to Node 2, needs 4 time units -> t = 4
- Waiting for the event at Node 2 (so, we wait until t = 10)
- Agent goes to Node 3, needs 2 time units -> t = 12
- Waiting for the next event (until t = 21)
- Agent goes to Node 4, needs 2 time units -> t = 23
- Waiting for the last event (until t = 40)
- All events visited, done (with t = 40)



debp

Attached Files

•  Unbenannt.png   9.67K   619 downloads

[WingedPanther]

Start with a complete list of the times. Find the current location and the next location to get to. Each node can calculate the distance to the target node, then simply go their via the "correct" direction. Since this is a cyclic graph, you can store your data in an array, and use the indices to determine the distance ((n-m)%p or (m-n)%p) between nodes.

[debp]

Thanks for your answer.
Well, what is the "correct" direction?
I can't just go to the shortest path, because that's not necessarily the right path (imagine the next node has a time of 1000, then you would need to wait that long, but instead, you could visit other nodes and be quicker)!


One Example (Attachment):

With your method, the agent would move to node 2, because it is the shortest path, then wait 1000 (well, actually 999, because you needed 1 to get to the node) and then move to the other nodes and therefore you will need more than 1000 time units (which is not the optimal way).

Attached Files

•  Unbenannt2.png   9.76K   175 downloads

Edited by debp, 17 September 2008 - 10:33 AM.

[WingedPanther]

I think you misunderstood: I would move to the "next" in the sense of the node that has the next item coming up, not necessarily the adjacent node. Basically, I would go to the next node I can reach in time. Be aware that greedy algorithms and minimax algorithms generally produce "good" solutions, but not necessarily optimal solutions.

[debp]

Thanks for the clarification.

But I need an algorithm that produces the optimal solution, not just "good" solutions, as you say.
With the greedy approach, it would not always work.

Can you help me with that?
I tried a lot of examples on paper, but I guess I don't have the experience with algorithms to find a solution...

[WingedPanther]

One thing you can do is create a "distance map" using a 2d array. That will allow you to look up the distance to any node from any node.

Another thing you can do is find incremental solutions. Find all the times to get 1 node. Then find all the times to get 2 nodes. Then find all the times to get 3 nodes. At this point, if you have the same three nodes "gathered" and are at the same node, you only need to keep the progression with the lowest time.

Alternately: you can find one node sequence's time. Then, you can start going through the n! permutations of node orders, but as you are working through a permutation, if your time exceeds a found sequence's time you can abandon all the full permutations that start with that sequence and look for a new one. You don't have to find all the times, just all the times that are shorter than the current shortest time.

[debp]

Thank you again for your answer :)

Quote

One thing you can do is create a "distance map" using a 2d array. That will allow you to look up the distance to any node from any node.

Is the distance map just a tool for the solutions you provided? Because it sounds like this 2d array is a solution on its own...

Edited by debp, 18 September 2008 - 09:22 AM.

[WingedPanther]

2d arrays of various sorts can be used to store weighted graphs/digraphs of all sorts.

[John]

I would recommend creating a "node" object / structure. Each node object would know what nodes it was adjacent to and the weight of the arc connecting its adjacent nodes. In essence, you are representing the graph using an adjacency matrix, and can thus employ graph algorithms very easily. I had to create a graph data structure for one of my algorithm classes, and this was the method I used.