algorithm - 如何使用AI找到点之间的最短路线？

Question

我正在尝试通过在 hackerrank 上尝试问题来提高我的 AI 知识.

问题之一是:

Princess Peach is trapped in one of the four corners of a square grid. You are in the center of the grid and can move one step at a time in any of the four directions. Can you rescue the princess?

详情为here .

我需要一个提示来系统地解决这个问题。是最短路线问题吗？或者人工智能的哪些算法/概念可以用来解决这个问题？

谢谢。

Answer 1

这是 shortest path problem ，其中节点是网格中的单元格，边是从单元格到单元格的可能移动。

最简单的解决方案是使用 BFS (因为图表未加权)。一项改进是使用 bi-directional BFS .

面向人工智能的改进是使用知情算法，例如A* .你将需要一个 admissible heuristic使用它的功能，你能想到吗？ (有一个经典的众所周知的，但我会让你自己弄明白)。