Graph search problem with route restrictions

I want to calculate the most profitable route and I think this is a type of traveling salesman problem.

I have a set of nodes tha开发者_StackOverflowt I can visit and a function to calculate cost for traveling between nodes and points for reaching the nodes. The goal is to reach a fixed known score while minimizing the cost.

This cost and rewards are not fixed and depend on the nodes visited before.

The starting node is fixed.

There are some restrictions on how nodes can be visited. Some simplified examples include:

• Node B can only be visited after A
• After node C has been visited, D or E can be visited. Visiting at least one is required, visiting both is permissible.
• Z can only be visited after at least 5 other nodes have been visited
• Once 50 nodes have been visited, the nodes A-M will no longer reward points
• Certain nodes can (and probably must) be visited multiple times

Currently I can think of only two ways to solve this:

a) Genetic Algorithms, with the fitness function calculating the cost/benefit of the generated route

b) Dijkstra search through the graph, since the starting node is fixed, although the large number of nodes will probably make that not feasible memory wise.

Are there any other ways to determine the best route through the graph? It doesn't need to be perfect, an approximated path is perfectly fine, as long as it's error acceptable.

Would TSP-solvers be an option here?

With this much weird variation and path-dependence, what you're actually searching is not the graph itself, but the space of paths from the root, which is a tree. If the problem is as general as you say, you're not going to be able to do better than directly searching the "tree-of-paths", saving the best value and the corresponding path. If you can transform it into any way so that there is no such path-dependence, you should probably do so.

If you can't, there are two basic options: breadth-first, which will return the paths in order of length, but at the cost of high memory usage, as there are many temporary paths that must be stored. Depth-first search only needs to store a single path (which can be done entirely as a series of recursive calls), but has no natural stopping point, and is not guaranteed to actually terminate if there is no upper bound on the path size.

If you're lucky enough that the cost increases monotonically with each additional step, you can instead order by cost. The first one that's good enough is the one you then want. Breadth firs search is sometimes implemented by putting the paths to explore on a queue. Change this to a priority queue based on the cost, and you now have a "cost first search", known formally as Uniform-cost search.

If the cost function can decrease by adding on the path, A* search can be modified to do the search, but you no longer have the guarantee that you can stop early.