具有未知最终状态的类 Astar 算法
A-star 用于查找图中起始节点和结束节点之间的最短路径。 如果目标状态不是特别已知，而我们只有目标状态的标准，则使用什么算法来解决问题？
例如，数独谜题可以用类似 Astar 的算法来解决吗？ 我们不知道最终状态会是什么样子（哪个数字在哪里），但我们确实知道数独的规则，这是获胜状态的标准。 因此我有一个起始节点和一个结束节点的标准，要使用哪种算法？
A-star is used to find the shortest path between a startnode and an endnode in a graph. What algorithm is used to solve something were the target state isn't specifically known and we instead only have a criteria for the target state?
For example, can a sudoku puzzle be solved with an Astar-like algorithm? We dont know how the endstate will look like (which number is where) but we do know the rules of sudoku, a criteria for a winning state. Therefore I have a startnode and just a criteria for the endnode, which algorithm to use?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
A* 需要一个图、遍历该图的成本函数、关于图中的一个节点是否比另一个节点更接近目标的启发式方法，以及测试是否达到目标。
搜索数独解决方案空间实际上并没有最小化的遍历成本，只有全局成本（未解决的方块的数量），因此所有遍历的成本都是相等的，因此 A* 并没有真正的帮助 - 您可以分配的任何单元格花费一步，让你离目标更近一步，所以 A* 并不比随机选择下一步更好。
可以根据在每个点应用不同技术的估计/测量成本来应用 A* 搜索，然后尝试以最少的计算成本找到通过解决方案空间的路径。 在这种情况下，图表将不仅仅是谜题的解决方案状态，而且您还可以在此时应用的技术之间进行选择 - 您会知道转换成本的估计，但不知道转换的位置'成功了，就离目标又近了一步。
A* requires a graph, a cost function for traversal of that graph, a heuristic as to whether a node in the graph is closer to the goal than another, and a test whether the goal is reached.
Searching a Sudoku solution space doesn't really have a traversal cost to minimize, only a global cost ( the number of unsolved squares ), so all traversals would be equal cost, so A* doesn't really help - any cell you could assign costs one move and moves you one closer to the goal, so A* would be no better than choosing the next step at random.
It might be possible to apply an A* search based on the estimated/measured cost of applying the different techniques at each point, which would then try to find a path through the solution space with the least computational cost. In that case the graph would not just be the solution states of the puzzle, but you'd be choosing between the techniques to apply at that point - you'd know an estimate of the cost of a transition, but not where that transition 'goes', except that if successful, it's one step closer to the goal.
是的，当无法识别特定目标状态时可以使用 A*。 （Pete Kirkham 的回答暗示了这一点，但没有强调 当无法识别特定的目标状态时，
有时很难针对完成部分解决方案所需的剩余成本提出有用的启发式下限，并且 A* 的效率取决于选择有效的启发式。 但这并不意味着它不能应用。 任何可以在计算机上解决的问题都可以使用广度优先搜索来解决，再加上一组标志来指示某个状态之前是否已经见过； 这与 A* 相同，启发式下界始终为零。 （当然，这并不是解决许多问题的最有效的算法。）
Yes, A* can be used when a specific goal state cannot be identified. (Pete Kirkham's answer implies this, but doesn't emphasise it much.)
When a specific goal state can't be identified, it's sometimes harder to come up with a useful heuristic lower bound on the remaining cost needed to complete a partial solution -- and the efficiency of A* depends on choosing an effective heuristic. But it doesn't mean it can't be applied. Any problem that can be solved on a computer can be solved using a breadth-first search, plus an array of flags indicating whether a state has been seen before; which is the same as A* with a heuristic lower bound that is always zero. (Of course, this is not the most efficient algorithm for solving many problems.)
您不必知道确切的目标最终状态。 这一切都归结为启发式函数，当它返回 0 时，您可以假设已经找到（至少）有效的最终状态之一。
因此，在 a* 期间，不要检查 current_node == target_node，而是检查 current_node.h() 是否返回 0。如果是这样，它应该无限接近和/或重叠目标/最终状态。
You dont have to know the exact target endstate. It all comes down to the heuristic function, when it returns 0 you could assume to have found (at least) one of the valid endstates.
So during the a*, instead of checking if current_node == target_node, check if current_node.h() returns 0. If so, it should be infinitely close and/or overlapping the goal/endstate.