Scheme中的最佳优先搜索算法

小编典典

Scheme中的最佳优先搜索算法

algorithm

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

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

假设我有一个5x5的网格，并且一个机器人位于（1,5）位置，而我的目标是将机器人移至（5,1）。一路上有几个障碍，比如说(X,1,3)，(X,2,3)，(X,5,3)，(X,4,2)

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

我正在考虑使用贪婪的最佳优先搜索算法来找到机器人到达目标的路径

我的问题是，我是新手，不知道该如何解决这个问题。

我是不是该？

(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)

解决问题？

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

非常感谢帮助:)

阅读 335

2020-07-28

共1个答案

小编典典

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

然后，选择搜索算法。您选择了贪婪的最佳优先搜索（GBFS），因此，我们继续进行下去，但是在实际情况下，应根据您的问题要求进行选择。

GBFS是一种简单的算法，需要以下内容（对于任何路径查找算法，您都需要这些模块中的大多数）：

列出任何节点的所有邻居的功能。 例如，在我们上面指定的网格中，邻居是很容易确定的（在两个方向上进行+ 1，-1排列，并进行了一些边界检查，当然要检查 它是否是障碍物 ）。
跟踪Open节点的数据结构：Open节点是尚未检查的节点。因此，在Wikipedia的示例代码中，您从初始位置开始，找到其后继者（使用上述功能），并基于 启发式方法 （您可以将目标与后继者之间的欧氏距离或曼哈顿距离用作启发式方法）进行添加将其添加到Open“列表”中-最好将其实现为 优先级队列 。
您的主要功能 ：这实际上将从初始位置开始，(1,5)并找到其邻居，然后根据与目标的欧几里得距离将其添加到优先级队列中。然后在该列表上递归（即执行与初始位置相同的操作），直到找到目标。

因此，关于Greedy Best First的注意事项是您可能没有最佳路径，但是可以保证终止和一条路径（如果存在）。您应该考虑其他算法，例如A
*或“广度优先”或“深度优先”，然后看看哪种算法可以满足您的要求。

2020-07-28