java 用 A* 算法解决 8 个难题
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4251295/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Solving The 8 Puzzle With A* Algorithm
提问by Kap
I would like to solve/implement the 8 puzzle problem using the A* algorithm in Java. Am asking if someone can help me by explaining to me the steps i must follow to solve it. I have read on the net how the A* works but i don't know how to begin the implementation in Java.
我想使用 Java 中的 A* 算法解决/实现 8 拼图问题。我在问是否有人可以通过向我解释解决它必须遵循的步骤来帮助我。我已经在网上阅读了 A* 的工作原理，但我不知道如何开始在 Java 中实现。
I will be very grateful if you guys can help me and give me the guidelines so that i can implement it myself in Java. I really want to do it to be able to understand it, so i just need the guidelines to start.
如果你们能帮助我并给我指导，我将不胜感激，这样我就可以用 Java 自己实现它。我真的很想这样做才能理解它，所以我只需要指导方针就可以开始。
I will use priority queues and will read the initial configuration from a text file which looks like for example this:
我将使用优先级队列，并从一个文本文件中读取初始配置，例如：
4 3 6
1 2 5
7 8
Pointers to other sites for more explanation/tutorials are welcome.
欢迎指向其他站点以获取更多解释/教程。
采纳答案by Peter G. McDonald
I'd begin with deciding how you want to represent the game board states, then implement the operators (eg. move (blank) tile up, move (blank) tile down, ...). Typically you will have a data structure to represent the open list (ie. those states discovered but as yet unexplored (ie. compared with goal state) and another for the closed list (ie. those states discovered and explored and found not to be the goal state). You seed the open list with the starting state, and repeatedly take the "next" state to be explored from the open list, apply the operators to it to generate new possible states and so on ...
我首先决定你想如何表示游戏板状态，然后实现操作符（例如，向上移动（空白）瓷砖，向下移动（空白）瓷砖，......）。通常，您将有一个数据结构来表示开放列表（即那些已发现但尚未探索的状态（即与目标状态相比）和另一个表示封闭列表的数据结构（即那些已发现并探索但发现不是目标状态）。你用起始状态播种开放列表，并重复从开放列表中获取要探索的“下一个”状态，将运算符应用于它以生成新的可能状态等等......
There is a tutorial I prepared many years ago at:
我多年前准备了一个教程：
http://www.cs.rmit.edu.au/AI-Search/
http://www.cs.rmit.edu.au/AI-Search/
It is far from the definitive word on state space searching though, it is simply an educational tool for those brand new to the concept.
虽然它远非状态空间搜索的明确词，但它只是对那些全新概念的人的教育工具。
回答by moinudin
Check http://olympiad.cs.uct.ac.za/presentations/camp1_2004/heuristics.pdfit describes ways of tackling this very problem.
检查http://olympiad.cs.uct.ac.za/presentations/camp1_2004/heuristics.pdf它描述了解决这个问题的方法。
回答by Tim Bender
A* is a lot like Djikstra's algorithm except it includes a heuristic. You might want to read that wikior read about single-source shortest path algorithms in general.
A* 很像 Djikstra 的算法，只是它包含启发式算法。您可能想阅读该wiki或阅读有关单源最短路径算法的一般信息。
A lot of the basic stuff is important but obvious. You'll need to represent the board and create a method for generating the possible next states.
许多基本的东西很重要但很明显。您需要代表董事会并创建一种方法来生成可能的下一个状态。
The base score for any position will obviously be the minimum number of actual moves to arrive at it. For A* to work, you need a heuristic that can help you pick the best option of possible next states. One heuristic might be the number of pieces in the correct position.
任何位置的基本分数显然是到达该位置的最少实际移动次数。为了让 A* 起作用，您需要一种启发式方法来帮助您选择可能的下一个状态的最佳选项。一种启发式方法可能是正确位置的件数。
