2

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

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

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

解决问题？

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

非常感谢您的帮助:)

4

2 回答 2

3

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

然后，您选择您的搜索算法。您选择了贪婪最佳优先搜索 (GBFS)，所以让我们继续使用它，但在实际情况下，您应该根据您的问题要求选择它。

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

  1. 列出任何节点的所有邻居的函数。例如，在我们上面指定的网格中，邻居是很容易确定的（在两个方向上+1，-1 排列，并进行一些边界检查，当然，检查它是否是障碍物）。

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

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

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

于 2009-10-16T01:56:18.153 回答
0

可能相关：C#：A-Star 诞生于 CodeProject

于 2009-10-16T00:57:20.597 回答