# Transversing possible multiple paths from one origin to one destination

Marilyn de Queiroz

Sheriff

Posts: 9063

12

posted 5 years ago

I want to go from point a to point b but I can get there multiple ways ... not only directly ... sometimes with one point between, sometimes more than one point between.

To complicate the issue further, I need to be able to go backwards ...

So I can go direct from a to b

I can go from a -> a' -> b

I can go from a -> a" -> c -> d -> back to c and over to b

I can go from a -> b -> a -> b multiple times

I can go from a -> a' -> b -> a' -> b

as long as the first is a and the last is b.

Any ideas on the best algorithm to do this?

To complicate the issue further, I need to be able to go backwards ...

So I can go direct from a to b

I can go from a -> a' -> b

I can go from a -> a" -> c -> d -> back to c and over to b

I can go from a -> b -> a -> b multiple times

I can go from a -> a' -> b -> a' -> b

as long as the first is a and the last is b.

Any ideas on the best algorithm to do this?

JavaBeginnersFaq

"Yesterday is history, tomorrow is a mystery, and today is a gift; that's why they call it the present." Eleanor Roosevelt

Marilyn de Queiroz

Sheriff

Posts: 9063

12

posted 5 years ago

There is a threshold ... the total [length] of all paths must be less than the threshold. Path lengths are variable.

"Yesterday is history, tomorrow is a mystery, and today is a gift; that's why they call it the present." Eleanor Roosevelt

Marilyn de Queiroz

Sheriff

Posts: 9063

12

posted 5 years ago

Once I find all possible paths, I can handle the rest of the logic ... not the shortest, but the longest (less than the threshold) with certain constraints ...

Ernest Friedman-Hill wrote:Are you looking for the shortest path, or just enumerating paths? The first is the Traveling Salesman problem, of course.

Once I find all possible paths, I can handle the rest of the logic ... not the shortest, but the longest (less than the threshold) with certain constraints ...

"Yesterday is history, tomorrow is a mystery, and today is a gift; that's why they call it the present." Eleanor Roosevelt

posted 5 years ago

But that would be true of the Travelling Salesman problem too. Find all possible paths, sort by path length, and bingo you have the solution. So "Find all possible paths" isn't a good first step.

Marilyn de Queiroz wrote:Ernest Friedman-Hill wrote:Are you looking for the shortest path, or just enumerating paths? The first is the Traveling Salesman problem, of course.

Once I find all possible paths, I can handle the rest of the logic ...

But that would be true of the Travelling Salesman problem too. Find all possible paths, sort by path length, and bingo you have the solution. So "Find all possible paths" isn't a good first step.

Mike Simmons

Ranch Hand

Posts: 3076

14

posted 5 years ago

Well, one can replace "find all possible paths" with "find all possible paths with total length less than the threshold". That's a little better. You can reject any proposed route as soon as it exceeds the max allowable length. Still, this could well be computationally intractable if the threshold is too high. Maybe that's unavoidable, maybe not.

Marilyn, can you elaborate at all on the "with certain constraints"?

It might be worthwhile to look at Dijstra's algorithm for some ideas. As a first step, you could calculate the minimum distance from endpoint b for every point on the map. At least, every point within the threshold. Then as you walk "every possible path" starting from a, you can reject a path as soon as [current distance from a] + [minimum distance from b] > [threshold distance]. Early rejection is essential to minimize time wasted on paths that can't possibly pan out.

Marilyn, can you elaborate at all on the "with certain constraints"?

It might be worthwhile to look at Dijstra's algorithm for some ideas. As a first step, you could calculate the minimum distance from endpoint b for every point on the map. At least, every point within the threshold. Then as you walk "every possible path" starting from a, you can reject a path as soon as [current distance from a] + [minimum distance from b] > [threshold distance]. Early rejection is essential to minimize time wasted on paths that can't possibly pan out.

Mike Simmons

Ranch Hand

Posts: 3076

14

posted 5 years ago

This also smells like the sort of problem that might be best addressed with ant colony optimization. That may be more involved than you want to deal with, however. Perhaps it's best to start with a simple find-every-path-less-than-threshold approach, and see how long it takes, for actual real data that you need to work with. If that's fast enough, then you're done. If not, more complex refinements are possible.

Marilyn de Queiroz

Sheriff

Posts: 9063

12

posted 5 years ago

Thank you.

Each point to point path has an assigned length and an assigned number of "collectable points". Some have negative collectable points. The goal is to capture the maximum number of collectable points while on the way from start to end without exceeding the threshold allowed for that pair of points. So rather than the shortest distance, we (usually) want the longest. However, if I can capture more points by going from a to b (shortest distance), back to a and back to c (starting at a and ending at c) than I can by going from a to b to d to e to c (longer distance), then I want the first option. Or maybe I will get more points by going from a to b to c to b to c ... (where all 3 options are below the threshold for the a to c pair)

I'll check out those urls.

Each point to point path has an assigned length and an assigned number of "collectable points". Some have negative collectable points. The goal is to capture the maximum number of collectable points while on the way from start to end without exceeding the threshold allowed for that pair of points. So rather than the shortest distance, we (usually) want the longest. However, if I can capture more points by going from a to b (shortest distance), back to a and back to c (starting at a and ending at c) than I can by going from a to b to d to e to c (longer distance), then I want the first option. Or maybe I will get more points by going from a to b to c to b to c ... (where all 3 options are below the threshold for the a to c pair)

I'll check out those urls.

"Yesterday is history, tomorrow is a mystery, and today is a gift; that's why they call it the present." Eleanor Roosevelt