方案最佳优先搜索算法 [英] Best First Search algorithm in Scheme

问题描述

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

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

假设我有一个5x5的网格，并在位置（1,5），一个机器人，我的目标是在机器人移动到（5,1）。一路上很少有障碍，比如（X，1,3），（X，2,3） ，（X，5,3），（X，4,2）

打印出的路线，机器人已经通过了。

我使用的是贪婪最佳优先搜索算法找到一个思维路径机器人的目标

我的问题是，我是新来的方案不知道如何我应该开始解决这个有点问题。

我应该这样做？

 （定义网格LW）--define网格的长度和宽度？

（定义机器人）--define初始位置

（定义目标）--define目标位置

（定义块）--define障碍块

并创建一个主功能（定义bestfirstslove）
 

要解决这个问题呢？

我如何创建一个网格？我应该如何处理这一问题？我怎样才能打印出机器人移动的步骤是什么？

帮助是非常AP preciated :)

解决方案

好了，你要做的第一件事就是离散化您的搜索空间。用你的一个5x5的网格的例子，这意味着你有一个共25个机器人能占据。

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

GBFS是一种简单的算法，其要求如下（和你最需要的，这些模块的任何路径寻找算法）：

1. 的的函数列出所有节点的所有邻居。的例如：在我们上面指定的网格，邻居们平凡的决定（+ 1，-1排列在两个方向当然是有一些边界检查，并检查的如果它是一个障碍的）。

2. 的的数据结构来跟踪打开节点的：打开节点是这还有待检验。因此在本例中code在维基百科，你开始的初始位置，找到自己的继任者（使用上述功能）以及基于启发式（可以使用的欧氏或曼哈顿距离目标和继任者启发式），将其添加到打开清单 - 这是更好地为的优先级队列

3. 你的主要功能的：这将从根本上开始的初始位置（1,5）并找到其邻国并把它们添加到基于对目标的欧氏距离的优先级队列。然后递归（即做同样的事情，你做了什么与初始位置）的名单上，直到你找到你的目标。

所以，你应该注意的贪婪最好的首先是你可能没有最佳路径，但你保证终端和路径（如果存在的话）。你应该想想其他的算法，如A *或广度优先或深度优先，看看什么对你的要求。

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

解决方案

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

1. 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).

2. A data structure to keep track of Open nodes: Open nodes 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 the Open "list" - which is better implemented as a priority queue.

3. 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.

这篇关于方案最佳优先搜索算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！