我一直在阅读关于寻路算法的文章，现在我正在寻找一个能够像A*算法一样工作，但是代理不能对角移动的算法。节点是否仍会对角扩展或者是以其他方式呈现？也许它与A*不相关吗？请考虑以下图像，其中三角形是我们的代理，棕色矩形是网格正方形之间的障碍物，箭头只是为了清楚起见，当没有面对此障碍物时，您仍可以通过具有障碍物“边界”的正方形行走。您会建议哪种算法作为这些特征的路径查找问题的基础？如果已发布类似内容，请原谅，我没有找到它。
2个回答
6
A*是一种用于图形搜索的算法，给定起始位置和一组目标节点，它会基于图形的顶点和边找到一条路径。
如果您希望您的代理无法对角移动，您需要设计您的图形，使得对角线顶点之间没有边。
我假设您正在使用一个next:V->2^V函数来获取您的代理可以下一步到达的所有位置。如果是这种情况，请确保从该函数中不返回对角线。
- amit
2
正如amit所说，A*是一种搜索算法，可以应用于（几乎）任何搜索问题。
任何“搜索问题”都可以用以下参数描述（或定义）：
- 起始状态（位置） - 转移函数（如果给定任何状态a，则可以在一个步骤中获得的状态是什么） - 终止状态（位置）
起始状态和终止状态以及转移函数可以明确或隐含地给出，例如，在通过网格移动时（就像在您的问题中），下一个位置可以是任何邻居（上，下，左，右+可能对角线），或者在一个空间中可能包含显式信息。终止状态也可以事先知道（例如，具有坐标（x，y）的状态），或者可以根据状态的某些特征来定义（例如，如果网格中有硬币，则终止状态可以是任何具有硬币的状态）。
最常见的搜索算法包括BFS、DFS、迭代深度优先搜索（非定向）、爬山法、A*（定向）。还有许多其他算法-请看维基页面右侧的图形。其中一些是“完全的”（意思是，即使在无限搜索空间中，如果存在结束状态，也将始终找到 - BFS、A*），而有些则不是（DFS、爬山法）。另一种分类是通过算法的“最优性”。最优搜索将找到最佳解决方案或通往最佳解决方案的最佳路径（非加权图的BFS、A*），而其他搜索将找到任何可接受的解决方案或通往解决方案的任何可能路径（加权图的BFS）。通常，计算复杂度、内存要求和实现简单性之间存在折衷。定向搜索还会使用一些关于结束状态的预先已知信息来指导搜索（从任何给定状态估计结束状态的距离），而非定向搜索则不会。
例如，如果您知道起始和结束位置的坐标，则有向搜索是有意义的。如果起始位置在左上角，而结束位置在左下角，您更喜欢沿着向下方向搜索状态，而不是向右方向搜索状态。如果您的起始位置在棋盘中央，结束位置没有明确定义（由特征定义），可以在棋盘中的任何位置，则有向搜索并没有太大帮助。
此外，如果您的问题规模不大（例如，在一个100x100的棋盘上搜索），通常没有使用有向搜索的好理由，广度优先搜索或其他非有向搜索算法足够快速，并且使用更复杂的有向搜索获得的加速效果并不显著。
请注意，所有搜索算法都可以使用任何给定的转换函数。
因此，总之，您应该使用的算法类型取决于您的问题限制：
以下是搜索算法的简要概述：
- 搜索空间小，没有关于结束状态的已知信息：无向搜索（BFS，DFS）。 - 内存有限：DFS，迭代深度优先搜索。 - 搜索空间较大且已知结束状态的相关信息：有向搜索（A*，爬山算法）。 - 搜索空间中没有局部极值（例如没有障碍物），或内存有限且已知结束状态的相关信息：爬山算法。 - 还有许多其他限制需要考虑，搜索算法只是可能适用于这些情况的算法示例（根据额外限制可能也不适用）。
这只是搜索算法的简要概述，仅提供了一般理念。如果您不确定哪种算法最适合您的问题，请详细阅读特征和应用。
希望对您有所帮助 ;)
任何“搜索问题”都可以用以下参数描述（或定义）：
- 起始状态（位置） - 转移函数（如果给定任何状态a，则可以在一个步骤中获得的状态是什么） - 终止状态（位置）
起始状态和终止状态以及转移函数可以明确或隐含地给出，例如，在通过网格移动时（就像在您的问题中），下一个位置可以是任何邻居（上，下，左，右+可能对角线），或者在一个空间中可能包含显式信息。终止状态也可以事先知道（例如，具有坐标（x，y）的状态），或者可以根据状态的某些特征来定义（例如，如果网格中有硬币，则终止状态可以是任何具有硬币的状态）。
最常见的搜索算法包括BFS、DFS、迭代深度优先搜索（非定向）、爬山法、A*（定向）。还有许多其他算法-请看维基页面右侧的图形。其中一些是“完全的”（意思是，即使在无限搜索空间中，如果存在结束状态，也将始终找到 - BFS、A*），而有些则不是（DFS、爬山法）。另一种分类是通过算法的“最优性”。最优搜索将找到最佳解决方案或通往最佳解决方案的最佳路径（非加权图的BFS、A*），而其他搜索将找到任何可接受的解决方案或通往解决方案的任何可能路径（加权图的BFS）。通常，计算复杂度、内存要求和实现简单性之间存在折衷。定向搜索还会使用一些关于结束状态的预先已知信息来指导搜索（从任何给定状态估计结束状态的距离），而非定向搜索则不会。
例如，如果您知道起始和结束位置的坐标，则有向搜索是有意义的。如果起始位置在左上角，而结束位置在左下角，您更喜欢沿着向下方向搜索状态，而不是向右方向搜索状态。如果您的起始位置在棋盘中央，结束位置没有明确定义（由特征定义），可以在棋盘中的任何位置，则有向搜索并没有太大帮助。
此外，如果您的问题规模不大（例如，在一个100x100的棋盘上搜索），通常没有使用有向搜索的好理由，广度优先搜索或其他非有向搜索算法足够快速，并且使用更复杂的有向搜索获得的加速效果并不显著。
请注意，所有搜索算法都可以使用任何给定的转换函数。
因此，总之，您应该使用的算法类型取决于您的问题限制：
以下是搜索算法的简要概述：
- 搜索空间小，没有关于结束状态的已知信息：无向搜索（BFS，DFS）。 - 内存有限：DFS，迭代深度优先搜索。 - 搜索空间较大且已知结束状态的相关信息：有向搜索（A*，爬山算法）。 - 搜索空间中没有局部极值（例如没有障碍物），或内存有限且已知结束状态的相关信息：爬山算法。 - 还有许多其他限制需要考虑，搜索算法只是可能适用于这些情况的算法示例（根据额外限制可能也不适用）。
这只是搜索算法的简要概述，仅提供了一般理念。如果您不确定哪种算法最适合您的问题，请详细阅读特征和应用。
希望对您有所帮助 ;)
- penelope
8
“爬山算法”是一种优化搜索算法，它只寻找一个好的解决方案 - 它对结果节点没有任何保证[除了它是局部最小值/最大值]，并且特别地 - 它不是预定义目标状态的路径查找算法，因此它用于完全不同的目的，而不是A*。此外：当涉及到加权图时，BFS和DFS会失败。如果您有加权图并且未被告知，则Dijkstra/Bellman Ford比BFS/DFS更可取-以确保最佳解决方案。 - amit
我之前提到完整搜索时可能会有所误解，检查后发现是因为打字太快导致的错误 - 我已校正，现在说深度优先搜索和爬山算法（之前说的是A）不能保证找到一个（最优）解。谢谢。此外，由于广度优先搜索是一种完整*搜索方法，在带权图中它最终总能找到正确的解。它可能不适用于此类问题（有更快的算法可以解决），但不会失败。而在没有访问状态控制机制的任何无限搜索空间中，深度优先搜索可能会失败。 - penelope
以下是来自维基百科的图和树搜索算法列表（虽然不是世界上最好的来源，但仍然有用）。爬山算法绝对不是上述问题的正确解决方案（它是一种贪心的图搜索算法），但在技术概述中提到它感觉还是有必要的。深度优先搜索在许多情况下可能会失败，我们可以达成共识并不单独列出所有失败情况。你说的一切都是正确的。但是，我无法在这里编写关于所有搜索算法的完整概述 - 那需要几篇维基文章 :) - penelope
我同意你不能把所有的东西都写出来，但是我的评论是关于你在回答/评论中提到或未提到的具体观点[例如提到BFS仅适用于无权图] - 我纠正了你的错误，以便你：（1）学习，如果你之前不知道;（2）修正你的答案 - 防止其他读者在将来出现问题。 - amit
我现在要添加一段关于最优/非最优搜索算法的内容。 - penelope
显示剩余3条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接