方案最佳优先搜索算法(Best First Search algorithm in Scheme)

好吧，这是一个家庭作业的问题，我只是没有一个线索我怎么想开始。一些帮助和提示将非常感激。

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

假设我有一个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)

解决这个问题？

如何创建一个网格？我应该如何看待这个问题？我怎样才能打印出来的机器人行进的步骤是什么？

帮助是非常赞赏:)

Answer 1:

好了，你要做的第一件事是离散的搜索空间。使用5×5格你的榜样，这意味着你有一个总的25点你的机器人可以占用。

然后，您选择的搜索算法。您已选择贪婪最佳优先搜索（GBFS），让我们一起去那，但在实际情况中，你应该选择它按您的问题要求。

GBFS是一个简单的算法，需要以下（和你最需要这些模块查找算法任何路径）：

该功能可以列出任何节点的所有邻居。 例如，在我们上面指定的网格，邻居平凡的决定（+ 1，-1在一些边界检查，当然两个方向排列，检查它是否是一个障碍 ）。
一种数据结构，以保持跟踪Open节点 ： Open节点是其中还没有被检查的节点。因此，在维基百科中的示例代码，你的初始位置开始，找到它的后继者（使用上述功能）以及基于启发式 （您可以使用目标和继任启发式之间的欧几里德或曼哈顿距离）添加它在Open “清单” -这是更好的作为优先级队列来实现。
你的主要功能 ：这基本上是先从初始位置(1,5)并发现它的邻居，并将它们添加到基于该目标的欧氏距离优先级队列。然后递归（即做同样的事情，你做了与初始位置的）名单上，直到你找到你的目标。