A* 搜索尖峰时刻游戏？
对于学校作业，我必须为高峰时间游戏制作一个求解器。如果您不熟悉高峰时间......请检查此链接：http://www.puzzles.com/products/rushhour.htm
对于这个求解器，我必须使用 A* 搜索算法，我在互联网上查了一下，我想我很理解该算法是如何工作的..只是我真的不知道如何在求解器中实现它..也不知道如何为汽车建立网格..有人可以给我一些提示吗/帮忙吗？ 不是一个完整的解决方案..
For an assignment for school I have to make a solver for a Rush Hour game.. if you aren't familiar with Rush Hour.. check this link: http://www.puzzles.com/products/rushhour.htm
For this solver I have to use the A* search algorithm, I looked on the internet a bit, and I think I quite understood how the algorithm works.. only I don't really have an idea how to implement it in the solver.. nor how I should build up the grid for the cars.. Can someone please give me some tips/help for this?
Not a complete solution..
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
为了表示汽车网格，我只需使用一个矩形单元格数组，其中每个单元格都标有一个整数 - 0 表示“空”，并且每辆车都有一个特定的编号，因此网格中的不同汽车将显示出来它们本身是具有相同编号的连续单元格。
此时，您应该能够编写一个函数来返回给定网格的所有可能的“移动”，其中“移动”是从一个网格状态到另一个网格状态的转换 - 您可能不需要编码比这更好的表示动作。
要实现 A*，您需要一种简单的启发式方法来判断一个动作看起来有多好，这样您就知道首先要尝试哪些动作。我最初建议，任何使目标车更接近目标或使空间更靠近目标车前部的动作都可能是更好的候选动作。就像 Will A 在评论中所说，除非您正在解决 1000x1000 Rush Hour 板的问题，否则这可能不是什么大问题。
这就是我能想到的所有棘手的部分。
To represent the grid of cars, I'd just use a rectangular array of cells where each cell is marked with an integer -- 0 indicates "empty", and each car has a particular number, so the different cars in the grid will manifest themselves as consecutive cells with the same number.
At this point, you should be able to write a function to return all the possible "moves" from a given grid, where a "move" is a transition from one grid state to another grid state -- you probably don't need to encode a better representation of a move than that.
To implement A*, you'll need a naive heuristic for figuring out how good a move looks, so you know which moves to try first. I would suggest initially that any move which either moves the target car closer to the goal or makes space nearer the front of the target car might be a better candidate move. Like Will A said in the comments, unless you're solving a 1000x1000 Rush Hour board, this probably isn't a big deal.
That's all the tricky parts I can think of.
正如 mquander 或 Will 已经指出的那样，A* 算法可能有点过于适合您的问题。
我现在只是给你一些提示，你可以使用哪些其他算法来解决这个问题。
我不想解释这些算法是如何工作的，因为你可以在互联网上找到很多很好的描述。但是，如果您有疑问，请随时问我。
您可以使用一些属于“无信息搜索”类型的算法。例如，广度优先搜索、深度优先搜索、统一成本搜索、深度有限搜索或迭代加深搜索。如果您使用广度优先搜索或统一成本搜索，那么您可能必须处理可用内存空间问题，因为这些算法具有指数空间复杂度（并且您必须将整个搜索空间保留在内存中）。因此，使用深度优先搜索（空间复杂度 O(b*m)）对内存更加友好，因为如果不包含解决方案，您首先访问的树的左侧部分可以被省略。深度限制搜索和迭代加深搜索几乎相同，而在迭代加深搜索中，您迭代地增加树的搜索级别。
如果比较时间复杂度（b=树的分支因子，m=树的最大深度，l=深度级别限制，d=解决方案的深度）：
广度优先：b^(d+1)
统一成本：乙^？
深度拳头：b^m
深度限制：b^l if (l>d)
迭代加深：b^d
所以你可以看到迭代加深或广度优先搜索表现得很好。深度有限搜索的问题是，如果您的解决方案位于比您的搜索级别更深的位置，那么您将找不到解决方案。
然后就是所谓的“知情搜索”，例如最佳优先搜索、贪婪搜索、a*、爬山或模拟退火。简而言之，对于最佳优先搜索，您使用每个节点的评估函数作为“合意性”的估计。贪婪搜索的目标是扩展使您更接近目标的节点。爬山和模拟退火是非常相似。斯图尔特·拉塞尔（Stuart Russell）对爬山的解释如下（我非常喜欢......）：爬山算法就像在失忆的浓雾中攀登珠穆朗玛峰”。它只是一个不断朝着价值增加的方向移动的循环。所以你只要“走”到增加你的评估函数的方向即可。
我会使用其中一种统一搜索算法，因为它们非常容易实现（您只需要对树进行编程并正确遍历它）。如果您有良好的评估功能，知情搜索通常会表现得更好......
希望对你有帮助...
As mquander or Will have already pointed out, the A* algorithm might be a bit an overfit for your problem.
I just give you now some hints what other algorithm you can use to solve the problem.
I don't want to explain how those algorithms work since you can find many good description in the internet. However, if you have a question, don't hesitate to ask me.
You can use some algorithms which belong to the kind of "uninformed search". There you have for example breadth first search, deep-first search, uniform cost search, depth-limited search or iterative deepening search. If you use breadth-first search or uniform cost search then you might have to deal with available memory space problem since those algorithms have an exponential space complexity (and you have to keep the whole search space in memory). Therefore, using a deep-first search (space complexity O(b*m)) is more memory friendly since the left part of the tree which you visit firstly can be omitted if it does not contain the solution. Depth-limited search and iterative deepening search are almost the same, whereas in the iterative deepening search you increase the search level of your tree iteratively.
If you compare time complexity (b=branching factor of the tree, m=maximum depth of the tree, l=depth level limit, d=depth of the solution):
breadth-first: b^(d+1)
uniform cost: b^?
depth-fist:b^m
depth-limited: b^l if (l>d)
iterative deepening: b^d
So as you can see iterative deepening or breadth-first search perform quite well. The problem of the depth-limited search is if your solution is located deeper than you search level, then you will not find a solution.
Then you have the so called "informed search" such as best-first search, greedy search, a*, hill climbing or simulated annealing. In short, for the best-first search, you use an evaluation function for each node as an estimate of “desirability". The goal of the greedy search is to expand the node which brings you closer to goal. Hill climbing and simulated annealing are very similar. Stuart Russell explains hill climbing as following (which I like a lot...): the hill climbing algorithm is like climbing Everest in thick fog with amnesia". It is simply a loop that continually moves in the direction of increasing value. So you just "walk" to the direction which increases your evaluation function.
I would use one of the uniformed search algorithms since they are very easy to implement (you just need to programme tree and traverse it correctly). Informed search performs usually better if you have a good evaluation function...
Hope that helps you...