It sounds like you'll want to run A* once to find the optimal path, then a simple breadth-first search to find all paths, pruning those that become more costly than the 10% threshold as you go.

How big is the search-space/graph/whatever? You could just run breadth-first searches. It'll start by finding an optimal path, then you can pick the first path/solution it finds that's at least N% different.

find path, penalize all nodes of that path with additional cost(10% additional cost?), find next path, do the same, etc... tried something like that?

I don't think there can be a general solution to this problem - it's got to be domain specific. I mean, if you think about the edge cases, it's actually impossible to find a path that is n% different from the optimal for all cases (not if you want the path to look at least somewhat "natural" anyway)

For example, if you think about a completely open environment with no obstacles at all, the optimal path would be a simple straight line. Any deviation from that straight line will appear unnatural and artifical.

On the other end of the scale, you have an environment where there is only one possible path (as someone else mentioned, a maze is an example of this kind of environment). In that case, if you change the path even one node, the solution becomes impossible.

Personally, I'm having a hard time trying to figure out what application you're working on that would have this requirement. You said, "users enter in the percent difference they require the alternative paths to be." I can only guess that it's some kind of AI, perhaps, where you want it to appear like the entity takes wrong turns or somehow appears more "human" by not being able to find the optimal path immediately... maybe?

I think it would be easier to figure out with some more information, perhaps. It sounds like an interesting problem, though :-)

There definitely exists an algorithm that will find the optimal path that is at least x% different than the optimal path if it exists for a general graph.

Just run a search on a graph where each node is a pair consisting of a node from the original graph and a counter that counts how many edges from the optimal path were taken to reach it. Nodes with a counter above a certain value simply don't exist in this new graph, and the edges can be easily mapped from the old graph to the new graph. The new graph is much bigger and so doing a search on it will take longer. Distance to goal from the original graph could be a good heuristic.

This will find an optimal solution but it probably won't be very fast.

Quote: Original post by Vorpy
There definitely exists an algorithm that will find the optimal path that is at least x% different than the optimal path if it exists for a general graph.

My point was not that it's not possible to find such solutions, just that many of them are not going to look "natural", if that's a requirement... Take my example of the environment with no obstacles at all -- a "90% optimal" path would end up zig-zagging or otherwise deviating, for no apparent reason.

I assume what the OP wants, though, is that in an environemnt with many different possibile routes to the destination, you can ask the path-finder to find an "almost" optimal solution (within some percentage margin). But as I said, the actual algorithm you'd want to choose would depend on your specific requirements (so if "the chosen path needs to 'seem' natural to a human" was a requirement, then that would mean you can't deviate from an 'obvious' path, for example).

Quote: Original post by DvDmanDT
How big is the search-space/graph/whatever? You could just run breadth-first searches. It'll start by finding an optimal path, then you can pick the first path/solution it finds that's at least N% different.

Around 3 million edges.

Quote: Original post by Codeka

Quote: Original post by Vorpy
There definitely exists an algorithm that will find the optimal path that is at least x% different than the optimal path if it exists for a general graph.

My point was not that it's not possible to find such solutions, just that many of them are not going to look "natural", if that's a requirement... Take my example of the environment with no obstacles at all -- a "90% optimal" path would end up zig-zagging or otherwise deviating, for no apparent reason.

Well, there are on-road and off-road networks, not free-space movement, so paths will follow graph edge lines. There is no need to "look realistic" since following graph edges is the only possibility.

Quote: I assume what the OP wants, though, is that in an environemnt with many different possibile routes to the destination, you can ask the path-finder to find an "almost" optimal solution (within some percentage margin). But as I said, the actual algorithm you'd want to choose would depend on your specific requirements (so if "the chosen path needs to 'seem' natural to a human" was a requirement, then that would mean you can't deviate from an 'obvious' path, for example).

You are correct - I do want many different possible routes that are "almost" optimal by some percent. There is no requirement to seem natural since we are running these algorithms on pre-generated graphs.

Quote: Original post by Vorpy
There definitely exists an algorithm that will find the optimal path that is at least x% different than the optimal path if it exists for a general graph.

Just run a search on a graph where each node is a pair consisting of a node from the original graph and a counter that counts how many edges from the optimal path were taken to reach it. Nodes with a counter above a certain value simply don't exist in this new graph, and the edges can be easily mapped from the old graph to the new graph. The new graph is much bigger and so doing a search on it will take longer. Distance to goal from the original graph could be a good heuristic.

This will find an optimal solution but it probably won't be very fast.

I've decided to simply store the optimal solution as I search, but instead of stopping the search once it's been found, continue searching and compare each solution to the optimal one, storing the ones that meet the threshold, and stopping the search once the requested number of routes have been found or once the search space is exhausted.

There are two ways that pop into my mind as to how to go about implementing such a task. Neither are optimal solutions, nor are they valid 100% of the time; they are, however, food for thought.

First method: Use A* to find the original optimal path. Remove all the edges (or at least the "non-critical" edges) from the graph. Repeat A* to determine the NEXT optimal path. When I say "non-critical edges" I am referring to the edges that are not the only way from one part of the graph to another. Any edge or vertex that is the "only way" to go must be flagged, preferably when you do the first A* iteration or when you pluck the first solution from the graph.

Second Method: Start at the root node. Choose the lowest cost path for the first solution, and the next lowest cost path for the second solution. Run A* again using the current vertecies (not the root vertex) as the source. Compute both solution per each step of A* and VIOLA!! You will have different solutions/paths with a single pass. Of course, graph variances could result in solutions like both paths being identical save their source nodes, and so on so forth. So there will need to be some element of checking.

Perhaps keep each solution as their own subgraph, and if subgraphs merge, then don't add that path to the solution. That would prevent the solutions from ever merging save for at the end.