方案中的最佳优先搜索算法
好吧，这是一个家庭作业问题，我只是不知道如何开始。一些帮助和提示将不胜感激。
我需要使用启发式函数来解决迷宫类型的问题。
假设我有一个 5x5 网格，一个机器人位于 (1,5) 位置，我的目标是将机器人移动到 (5,1)。一路上几乎没有障碍，例如 (X,1,3)、(X,2,3)、(X,5,3)< /code>, (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)
解决问题？
如何创建网格？我应该如何解决这个问题？如何打印机器人行走的步数？
非常感谢帮助:)
Okay this is a homework question, and I just don't have a clue how I suppose to start. Some help and hints will be much appreciated.
I need to use a heuristic function to solve a maze type problem.
Suppose I have a 5x5 grid, and a robot in position (1,5) and my goal is to move the robot to (5,1). Along the way there are few obstacles, say (X,1,3), (X,2,3), (X,5,3), (X,4,2)
Print out the route the robot has gone through.
I'm thinking using the greedy best first search algorithm to find a path for robot to the goal
My problem is, I'm new to scheme have no idea how I should start on solving this kinda problem.
Should I ?
(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)
to solve the problem ?
How can I create a grid ? How should I approach to this problem ? How can I print out the steps the robot travels ?
Help is much appreciated :)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
好的，所以您要做的第一件事就是离散化您的搜索空间。以 5x5 网格为例，这意味着您的机器人总共可以占据 25 个点。
然后，您选择搜索算法。您选择了贪婪最佳优先搜索（GBFS），所以我们就这样吧，但在实际情况下，您应该根据您的问题要求来选择它。
GBFS 是一种简单的算法，需要以下功能（对于任何路径查找算法，您都需要这些模块中的大部分）：
列出任何节点的所有邻居的函数。 例如，在我们上面指定的网格中，邻居是简单确定的（通过一些边界检查在两个方向上进行 +1、-1 排列，当然，检查是否是障碍物） .
跟踪
Open节点的数据结构：Open节点是尚未被访问的节点检查了。因此，在维基百科的示例代码中，您从初始位置开始，找到其后继位置（使用上述函数）并基于启发式（您可以使用目标和目标之间的欧几里德或曼哈顿距离）后继者作为启发式）将其添加到Open“列表”中 - 最好将其实现为优先级队列。你的主要函数：这本质上将从初始位置
(1,5)开始，找到它的邻居并将它们添加到基于到目标的欧几里得距离的优先级队列。然后在该列表上递归（即执行与初始位置相同的操作），直到找到目标。因此，关于贪婪最佳优先，您应该注意的是，您可能没有最佳路径，但可以保证终止和一条路径（如果存在）。您应该考虑其他算法，例如 A* 或宽度优先或深度优先，看看哪种算法适合您的要求。
Ok, so the first thing you do is discretize your search space. Using your example of a 5x5 grid, this means you have a total of 25 points your robot can occupy.
Then, you select your search algorithm. You've chosen Greedy Best First Search (GBFS), so let's go with that, but in a real situation you should choose it as per your problem requirements.
GBFS is a simple algorithm and requires the following ( and you'll need most of these modules for any path finding algorithm):
A function to list all the neighbors of any node. E.g. in the grid we've specified above, the neighbors are trivially determined (+1,-1 permutations in both directions with some boundary checking and of course, check if it's an obstacle).
A data structure to keep track of
Opennodes:Opennodes are nodes which are yet to be examined. So in the example code in Wikipedia, you start with the initial position, find its successors (using the above function) and based on a heuristic (you can use the Euclidean or Manhattan distance between the goal and the successor as a heuristic) you add it to theOpen"list" - which is better implemented as a priority queue.Your main function: This will essentially start with the initial position
(1,5)and find its neighbors and add them to the priority queue based on the Euclidean distance to the goal. Then recurse (i.e. do the same thing as what you did with the initial position) on that list until you find your goal.So, what you should note about Greedy Best First is you may not have the optimal path, but you're guaranteed termination and a path (if one exists). You should think about other algorithms like A* or Breadth First or Depth First and see what works for your requirements.
可能相关：C#：A-Star 在 CodeProject 诞生
Probably related: C#: A-Star is born at CodeProject