使用A*算法解决8数码难题

Question

使用A*算法解决8数码难题

11

我想使用Java中的A*算法解决/实现8数码问题。想请教有没有人可以帮我解释一下解题步骤。我在网上读到了A*算法的工作原理，但不知道如何开始在Java中进行实现。

如果有人能给我指导并提供指南，让我能够自己在Java中实现它，我将非常感激。我真的很想做到这一点以便能够理解它，所以我只需要开始的指南。

我将使用优先队列，并从类似于以下内容的文本文件中读取初始配置：

4  3  6
1  2  5
7  8

欢迎提供指向其他网站的指针以获取更多说明和教程。

- Kap

3个回答

3

请查看http://olympiad.cs.uct.ac.za/presentations/camp1_2004/heuristics.pdf，它描述了解决这个问题的方法。

- moinudin

1

A*算法与Djikstra算法非常相似，但它包含了一种启发式方法。你可能想要阅读维基百科或者了解单源最短路径算法的一般知识。

很多基础知识都很重要，但也很显而易见。你需要表示棋盘并创建一种生成可能下一步状态的方法。

任何位置的基本分数显然是到达该位置所需的最小实际移动次数。为了使A*算法正常工作，你需要一种启发式方法来帮助你选择可能下一步状态中的最佳选项。一种启发式方法可能是正确位置上的棋子数量。

- Tim Bender

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter G. McDonald · Accepted Answer

我会开始决定如何表示游戏板状态，然后实现运算符（例如，将（空）瓷砖向上移动，将（空）瓷砖向下移动，...）。通常您会有一个数据结构来表示开放列表（即已发现但尚未探索的状态（即与目标状态进行比较）），另一个用于封闭列表（即已发现并已探索且未找到目标状态的状态）。您使用起始状态填充开放列表，然后重复从开放列表中获取“下一个”要探索的状态，对其应用运算符以生成新的可能状态等等...

这里有一篇我多年前准备的教程：

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

虽然它远非状态空间搜索的决定性方法，但对于那些全新接触概念的人来说，它只是一种教育工具。