Algorithm - Help please.

[imcram]

Hi,
I want an algorithm that will provide the best path given a set of nodes. However, I have been unable to come up with a solution though I have tried for some time now. I want to know whether this can even be done. Here are my needs.

1. I have a set of nodes, usually about, 20 nodes.
2. Every node is connected to each other and I know all the initial weights.
3. I have to visit every node exactly once in the path. However, there is a special node that can be visited any number of times in the path.
4. The cost of travelling between two nodes are dynamic. Say the weigths S->A is 10 and A->B is 25. Now, if I were to take the path S->A->B, it would cost me not 10 + 25 = 35, but, 10 + (10 + 25) = 45. That is, you carry the last weights with you. So, as soon as you travel S->A, the weights of the edges connected to A are incremented by 10 (the cost of S->A.)
This is the cause of the headache for me. if this wasn't the case, applying Dijkstra's algorithm would have solved the problem. But because of this reason, I can't eliminate any path just by looking at the cost so far.

5. As soon as the path reachs the special node, say G, all the weights are reset to their original weights.

So, can anyone tell me an algorithm for this? I would be very greatful. Thank you.

[JosAH]

4. The cost of travelling between two nodes are dynamic. Say the weigths S->A is 10 and A->B is 25. Now, if I were to take the path S->A->B, it would cost me not 10 + 25 = 35, but, 10 + (10 + 25) = 45. That is, you carry the last weights with you. So, as soon as you travel S->A, the weights of the edges connected to A are incremented by 10 (the cost of S->A.)

Can you elaborate on this 'rule' a bit more? What if the path has three vertexes,
say S --> A --> B with individual edge costs equal to 10, 25 and 15. What would
the cost of the path be?

Second: is the starting vertex fixed?

kind regards,

Jos

[imcram]

Can you elaborate on this 'rule' a bit more? What if the path has three vertexes,
say S --> A --> B with individual edge costs equal to 10, 25 and 15. What would
the cost of the path be?

Second: is the starting vertex fixed?

kind regards,

Jos

Yes, the starting node is fixed.

Ok, lets say that we have four edges. S, A, B, C

At the beginning, this is how the weights stand:

S->A 10
A->B 25
B->C 15

We are not concerned about the other edges at the moment, so we do not need their weights for this example.

Now, if we were to take the path S->A->B->C, the total cost will be,

S->A A->B B->C

10 + (10) + 25 + ((10) + 25) + 15

so, total cost = 10 + (10 + 25) + ((10) + 25) + 15 = 95.

Hope that cleared up. It's like the weights accumulate when we visit a node. So, we have to carry all those past "sins" with us as well.

[imcram]

Can you elaborate on this 'rule' a bit more? What if the path has three vertexes,
say S --> A --> B with individual edge costs equal to 10, 25 and 15. What would
the cost of the path be?

Second: is the starting vertex fixed?

kind regards,

Jos

Yes, the starting node is fixed.

Ok, lets say that we have four edges. S, A, B, C

At the beginning, this is how the weights stand:

S->A 10
A->B 25
B->C 15

We are not concerned about the other edges at the moment, so we do not need their weights for this example.

Now, if we were to take the path S->A->B->C, the total cost will be,

S->A A->B B->C

10 + (10) + 25 + ((10) + 25) + 15

so, total cost = 10 + (10 + 25) + ((10) + 25) + 15 = 95.

Hope that cleared up. It's like the weights accumulate when we visit a node. So, we have to carry all those past "sins" with us as well.

Ah, the end node is fixed as well. it is the special node G.

[JosAH]

Allow me to summarize; please correct me if I'm wrong:

1) the start and end nodes are fixed;
2) there's one special node (distinct from the start and end nodes?)
3) every node should be visited exactly once except for that special node;
4) the costs of all edges are reset when the special node is visited.

Is that right? May I ask you a question: where does that problem come from?

kind regards,

Jos

[imcram]

Allow me to summarize; please correct me if I'm wrong:

1) the start and end nodes are fixed;
2) there's one special node (distinct from the start and end nodes?)
3) every node should be visited exactly once except for that special node;
4) the costs of all edges are reset when the special node is visited.

Is that right? May I ask you a question: where does that problem come from?

kind regards,

Jos

If u really want to know, try this :

http:\\www.marc .lk

If u've read the overview, perhaps u may be able to deduce what i am trying to do. I'll tell u how it came to this.
I programmed my bot so it will drop everything it is carrying when the package count it carries hits a certain value. So, I have multiple dropoff points when the robot decides that time's up (The number of dropoff points rarely exceed 20). So, the drpoff points are the nodes. I can use Dijkstra's (A* is bad coz we have teleport beams.) algorithm to check for the distances between each and every pair of nodes. And I have to bring all the goodies home. Currently, my bot is not doing a bad job of it. But, it would perform way better if I could program it to find the best path. That's where the problem comes from. Unfortunately I have been unable to find adequate resources on the internet about pathfinding when there are time & space variant weights. (As u can see, the only things I have been able to find are these words for it.). Anyway, I appreciate it if u could help. Thanx.

And about your query:

The special node is the end node.

[r035198x]

Just subscribing to it.

Sounds interesting.

[r035198x]

If u really want to know, try this :

http:\\www.marc .lk

If u've read the overview, perhaps u may be able to deduce what i am trying to do. I'll tell u how it came to this.
I programmed my bot so it will drop everything it is carrying when the package count it carries hits a certain value. So, I have multiple dropoff points when the robot decides that time's up (The number of dropoff points rarely exceed 20). So, the drpoff points are the nodes. I can use Dijkstra's (A* is bad coz we have teleport beams.) algorithm to check for the distances between each and every pair of nodes. And I have to bring all the goodies home. Currently, my bot is not doing a bad job of it. But, it would perform way better if I could program it to find the best path. That's where the problem comes from. Unfortunately I have been unable to find adequate resources on the internet about pathfinding when there are time & space variant weights. (As u can see, the only things I have been able to find are these words for it.). Anyway, I appreciate it if u could help. Thanx.

And about your query:

The special node is the end node.

Hey can you check the link again it says domain name does not exist.

[JosAH]

This one works: http://www.marc.lk/index.php

kind regards,

Jos

[Banfa]

You have said you need to calculate the "best" path but you have not said how you are qualifying a path as "best".

Is there a limit to the number of steps you take or is it solely on final score.

You have not actually said if you are trying to minimise or maximise the score. However I assume minimise because the solution for maximise is trivial (go to nodes in order largest to smallest only visiting node G at the end).

It is not clear how node G effects the score, listing nodes as ID(score) what would this path score

S -> A(10) -> B(20) -> G -> C(30)

?

[JosAH]

You have said you need to calculate the "best" path but you have not said how you are qualifying a path as "best".

Is there a limit to the number of steps you take or is it solely on final score.

You have not actually said if you are trying to minimise or maximise the score. However I assume minimise because the solution for maximise is trivial (go to nodes in order largest to smallest only visiting node G at the end).

It is not clear how node G effects the score, listing nodes as ID(score) what would this path score

S -> A(10) -> B(20) -> G -> C(30)

?

I just read the link the OP suppplied: it's about maximizing profits; the trouble
is that the cost/profit model is not linear, i.e. the profit is defined on the vertexes
while the edges contain the costs. The profits become costs again if the profit
has been 'taken'. I don't have a cookbook solution for this problem, I have to
give it some more thoughts ...

Even worse, this problem involves two phases: investigation of the solution space
(which comes with its own costs) and the 'harvesting' phase, collecting the
profits. Both phases can be merged of course.

At this very moment I'm thinking of 'attractors' but I don't know (yet?) how to
make this idea operational.

kind regards,

Jos

[imcram]

I just read the link the OP suppplied: it's about maximizing profits; the trouble
is that the cost/profit model is not linear, i.e. the profit is defined on the vertexes
while the edges contain the costs. The profits become costs again if the profit
has been 'taken'. I don't have a cookbook solution for this problem, I have to
give it some more thoughts ...

Even worse, this problem involves two phases: investigation of the solution space
(which comes with its own costs) and the 'harvesting' phase, collecting the
profits. Both phases can be merged of course.

At this very moment I'm thinking of 'attractors' but I don't know (yet?) how to
make this idea operational.

kind regards,

Jos

I do apologise, but I am looking at ur post and I do not understand all the jargon. However, I thank u all for ur concern. As it stands, even if I do get the answe from one of u to my problem, I think I will not be able to implement it in a day(There is a deadline, and it is tommorrow midnight & me being the snail I am I'll never get it done in time.). However, I would still like to know the answer to this problem sooner or later coz it really interests me.

So, I should clear it up a bit more.

The bot can carry packages. And each of the nodes are drop off points having various packages. So, at one point in time, the bot decides that it's had its share of exploring for the day and decides to go home with all the packages. The goal is to get the best packages to the starting point(G). Once the bot arrives at the starting point, there is no point in carrying the packs anymore, so it drops everything. So, once the robot arrives at the starting point, it does not have storage anymore. This is good as there is a penalty in battery cost for moving with packages onboard. (I hope I am not obscuring things even more.) That is why all the weights reset once the "special node" is visited.
So we have the distance between two nodes, the distance has to be multiplied by the battery life needed to move per unit length to find out the weight of the edge. The battery life required for unit length depends upon the number of packages the bot is carrying. Thus, it depends on the history of the path as the bot picks up packages at every node except G. So, I can't find out the lowest cost path which will visit all the nodes once(except G), and end with G. I don't think brute force is feasible, right?

Anyway, thanx.

Ah, and what are "attractors "?

[JosAH]

Ah, and what are "attractors "?

Consider them little magnets, i.e. they attract the robot. The more profit can
be collected, the harder they "attract". The farther away from the robot the
less they attract. The lower the battery level the more a fresh battery attracts.

The trouble with those attractors is (in contrast to real magnets) that there
can be an equilibrium in which the robot just moves a bit back and forth
without really being able to make a decision. The behaviour all depends on
how you define the attracting forces.

kind regards,

Jos

ps. I don't know whether or not attractors are the/a solution; it was just an idea
that came up when I read the problem description in the link you supplied.

[imcram]

Consider them little magnets, i.e. they attract the robot. The more profit can
be collected, the harder they "attract". The farther away from the robot the
less they attract. The lower the battery level the more a fresh battery attracts.

The trouble with those attractors is (in contrast to real magnets) that there
can be an equilibrium in which the robot just moves a bit back and forth
without really being able to make a decision. The behaviour all depends on
how you define the attracting forces.

kind regards,

Jos

ps. I don't know whether or not attractors are the/a solution; it was just an idea
that came up when I read the problem description in the link you supplied.

Ah, so u r talking about the whole big thing. OK. I think attractors would work better if u knew the whole scenario. Right? The map is not known at the start, it will only reveal itself when/if the bot explores. So, I guess unexplored areas are attractors themselves. attractors saying "explore me!". But I am not sure as to how much help they'd be in the exploration period. Ah, wait, perhaps the idea is very useful.
Anyway, I am thinking whether attractors can be used for the finishing manouver, which in my case is collecting packages and bringing them home. Plz let me know if u have any ideas on this.

[JosAH]

I think (for the lack of any better idea) that the attractor scenario needs a really
accurate quantification, i,e, the actual numbers you assign for the actual forces
with which objects 'attract' because you don't want your robot standing still with
a dead battery near the destination location and being 'ah, to bad, it was nearly optimal'.

I don't have any better ideas (yet?) though ... Here's another question: do you
*know* that there are so many yellow objects available no matter the space
ship layout? Or could it be that the entire space ship happens to be empty?

kind regards,

Jos