algorithm - 方案中的最佳优先搜索算法

Question

好吧，这是一个家庭作业问题，我只是不知道如何开始。一些帮助和提示将不胜感激。

我需要使用启发式函数来解决迷宫类型的问题。

假设我有一个 5x5 网格，机器人位于 (1,5) 位置，我的目标是将机器人移动到 (5,1)。一路上几乎没有障碍，例如 (X,1,3)、(X,2,3)、(X,5,3), (X,4,2)

打印出机器人走过的路线。

我正在考虑使用greedy best first search algorithm找到机器人到达目标的路径

我的问题是，我是计划新手，不知道应该如何开始解决这种问题。

我应该吗？

(define grid l w) --define the length and width of the grid ? 

(define robot) --define the initial position

(define goal) --define the goal position 

(define blocks) --define the obstacle blocks

and create a main function (define bestfirstslove)

解决问题？

如何创建网格？我应该如何解决这个问题？如何打印机器人行走的步数？

非常感谢您的帮助:)

Answer 1

好的，所以您要做的第一件事就是离散化您的搜索空间。以 5x5 网格为例，这意味着您的机器人总共可以占据 25 个点。

然后，您选择搜索算法。您选择了贪婪最佳优先搜索 (GBFS)，所以我们就这样做，但在实际情况中，您应该根据您的问题要求来选择它。

GBFS 是一个简单的算法，需要以下内容(对于任何路径查找算法，您都需要这些模块中的大部分):

1. 列出任何节点的所有邻居的函数。在我们上面指定的网格中，邻居是简单确定的(通过一些边界检查在两个方向上+1，-1排列，当然，检查是否是障碍物)。

2. 跟踪Open节点的数据结构:Open节点是以下节点:尚待检验。因此，在维基百科的示例代码中，您从初始位置开始，找到其后继位置(使用上述函数)并基于启发式(您可以使用目标和目标之间的欧几里德或曼哈顿距离)后继者作为启发式)将其添加到Open“列表”中 - 最好将其实现为优先级队列。

3. 您的主要函数:这基本上将从初始位置 (1,5) 开始，找到其邻居并添加根据到目标的欧几里德距离将它们放入优先级队列。然后在该列表上递归(即执行与初始位置相同的操作)，直到找到目标。

因此，关于贪婪最佳优先，您应该注意的是，您可能没有最佳路径，但可以保证终止和一条路径(如果存在)。您应该考虑其他算法，例如 A* 或宽度优先或深度优先，看看哪种算法适合您的要求。