用A*算法求解8道难题

Question

我想用Java中的A*算法来解决/实现8道难题。我问是否有人能帮助我，向我解释我必须遵循的步骤来解决这个问题。我在网上读过A*是如何工作的，但我不知道如何开始使用Java实现。

如果你们能帮助我，给我指导方针，让我自己用Java实现它，我将非常感激。我真的很想去理解它，所以我只是需要指南来开始。

我将使用优先级队列，并从文本文件中读取初始配置，例如：

4  3  6
1  2  5
7  8  

欢迎指向其他站点以获得更多解释/教程。

Answer 1

我将从决定你想如何代表游戏的棋盘状态开始，然后实现运营商(例如。移动(空白)瓷砖向上，移动(空白)瓷砖向下，.)。通常，您将有一个数据结构来表示打开的列表(即。那些州发现了，但还没有被发现。与目标状态相比)和另一个用于封闭列表(即。这些州发现，探索，发现不是目标状态)。您用起始状态为打开的列表添加种子，并反复从打开的列表中获取要探索的"next“状态，将运算符应用到它以生成新的可能状态，等等。

许多年前，我在以下网站上编写了一篇教程：

http://www.cs.rmit.edu.au/AI-Search/

然而，它远不是关于状态空间搜索的决定性词汇，它只是一个全新概念的教育工具。

Answer 2

查看2004/启发式.2004，它描述了解决这个问题的方法。

Answer 3

A*很像Djikstra的算法，但它包含了一个启发式算法。您可能希望阅读该维基或阅读一般的单源最短路径算法。

很多基本的东西都很重要，但很明显。您将需要表示板并创建生成可能的下一个状态的方法。

任何位置的基本得分显然都是实际移动的最小数目。要使A*工作，您需要一个启发式，它可以帮助您选择可能的下一个状态的最佳选项。一种启发式方法可能是正确位置上的片段数。