dynamic path finding? i.e. set of valid edges are path dependent.

[chopperdudes]

so at my job, i'm working on a problem. don't know if i'm allowed to say what i'm working on so.... but my boss wanted me to look at it from 2 perspectives. the first of which is implementing a genetic/swarm intelligence algorithm, which i have done and works fairly decently. the second of which boils down to a path finding problem...

however, this path finding problem is unusual in the following sense, in that each node doesn't have a set set of edges, in fact, the set of valid edges for each node depends on the path taken so far. you can think of the problem as follows: one can calculate a "distance" between any 2 nodes, but this distance is only meaningful if that node is a valid next node from the current node as some function of the path it's already taken. if this is still too abstract, think of overlaying some mesh points on a planar geometry, and i am to find a line segment between some 2 mesh points which will have to satisfy some geometric requirements i.e. concavity. the weights can also be negative.

as of now i have generated (i.e. for any 2 points), a tree of valid lines which has a head at one point, and its leaves always end on the 2nd point. but anything past say... 50 nodes is really not feasible by pure bruteforcing. i was wondering if there's any way to tackle this problem deterministically?

[mirhagk]

With negative weights, and requiring an exact answer, I don't think you can do anything other than brute force. If the wieghts can be negative then you can't make any assumptions and you have to expand every path.