3 ms·

I am a noob on this AI stuff but it seems to me that heuristics would be better if they take into account distance to the target without being permitted to go t

I am a noob on this AI stuff but it seems to me that heuristics would be better if they take into account distance to the target without being permitted to go through already visited nodes (so they can only go through unknown nodes treating them as empty) Say this example: BBBBBBBBBBBBBBBB GBR BBBBBBBBBBBBBBBB (switch off diagonal for stronger effect) Shows how badly A* and best first algorithms suffer from open spaces problem and would benefit from that change. I realize that computing such heuristic exactly would be costly but even something like 2x weight for nodes already visited in straight line to the target would improve it a lot.

keeperofdakeys 15y ago
The algorithms themselves are almost unaware of a path, they simply visit nodes, check their neighbours, then continue with another node from the queue. Breadth First Search simply does this in a predictable order, but of course it isn't prioritising nodes closest to the goal; that's where the other three come in. Every node has a path cost, how many moves it took to make it to the node. You can also define a distance heuristic, that calculates geometric distance to the goal as a strict underestimate. All these algorithms simply exit when the goal node is reached, and a path has been created by the algorithm. Dijkstra, or also known as Uniform Cost Search, will pick nodes with the lowest path cost from the queue first. This works well on graphs, but not so well on open spaces. It should be mentioned that this algorithm is complete, and optimal. That is, it will find a path if one exists, and it will find the path of lowest path cost (note there may be many such paths of equal path cost). Then we have A, which is also complete and optimal. This uses the sum of path cost and distance heuristic. This means it will nodes closer to the goal, but long-windy paths will confuse it. Finally we have Best First Search. It should be mentioned this is actually a family, of which Dijkstra and A are members. In this program, it only considers distance heuristic. So nodes that are geometrically closer to the goal are evaluated first. It should be mentioned that it isn't optimal - it might not find the path of lowest cost. If the optimal path requires at first winds away form the goal, these nodes aren't considered until later, or maybe never.

keeperofdakeys 15y ago

The algorithms themselves are almost unaware of a path, they simply visit nodes, check their neighbours, then continue with another node from the queue. Breadth First Search simply does this in a predictable order, but of course it isn't prioritising nodes closest to the goal; that's where the other three come in. Every node has a path cost, how many moves it took to make it to the node. You can also define a distance heuristic, that calculates geometric distance to the goal as a strict underestimate. All these algorithms simply exit when the goal node is reached, and a path has been created by the algorithm. Dijkstra, or also known as Uniform Cost Search, will pick nodes with the lowest path cost from the queue first. This works well on graphs, but not so well on open spaces. It should be mentioned that this algorithm is complete, and optimal. That is, it will find a path if one exists, and it will find the path of lowest path cost (note there may be many such paths of equal path cost). Then we have A, which is also complete and optimal. This uses the sum of path cost and distance heuristic. This means it will nodes closer to the goal, but long-windy paths will confuse it. Finally we have Best First Search. It should be mentioned this is actually a family, of which Dijkstra and A are members. In this program, it only considers distance heuristic. So nodes that are geometrically closer to the goal are evaluated first. It should be mentioned that it isn't optimal - it might not find the path of lowest cost. If the optimal path requires at first winds away form the goal, these nodes aren't considered until later, or maybe never.