Comment Re:Game movement AI (Score 1) 144
No, finding a path from A to B can easily be implemented (there are many efficient algorithms for that (e.g. Djikstra's...))
The traveling salesman problem is a bit different (but this little difference makes it - as you said - almost impossible to solve):
given: a set of cities and roads.
question: which is the most efficient way to visit all cities only once.
solution: you have to test all possible solutions!!! (the only way to shorten this search is by using heuristics e.g. if a to b and c to d cross and there is a connection a to c and b to d then you take this one (which makes the to paths shorter).
The traveling salesman problem is a bit different (but this little difference makes it - as you said - almost impossible to solve):
given: a set of cities and roads.
question: which is the most efficient way to visit all cities only once.
solution: you have to test all possible solutions!!! (the only way to shorten this search is by using heuristics e.g. if a to b and c to d cross and there is a connection a to c and b to d then you take this one (which makes the to paths shorter).
