您如何使用 A-Star 或 Dijkstra 算法解决 15 难题? [英] How do you solve the 15-puzzle with A-Star or Dijkstra's Algorithm?

问题描述

我在我的一本 AI 书籍中读到，在模拟或游戏中用于寻路的流行算法(A-Star、Dijkstra)也用于解决众所周知的15 拼图".

I've read in one of my AI books that popular algorithms (A-Star, Dijkstra) for path-finding in simulation or games is also used to solve the well-known "15-puzzle".

谁能给我一些关于如何将 15 拼图简化为节点和边图以便我可以应用其中一种算法的指示?

Can anyone give me some pointers on how I would reduce the 15-puzzle to a graph of nodes and edges so that I could apply one of these algorithms?

如果我将图中的每个节点都视为一个游戏状态，那这棵树会不会变得很大?或者这只是这样做的方式?

If I were to treat each node in the graph as a game state then wouldn't that tree become quite large? Or is that just the way to do it?

推荐答案

对于 A-Star 的 15 谜题来说，一个很好的启发式方法是计算错误位置的方块数.因为每个格子至少需要走 1 步棋，所以格子错位的数量保证小于或等于解决谜题所需的步数，使其成为 A-Star 的适当启发式.

A good heuristic for A-Star with the 15 puzzle is the number of squares that are in the wrong location. Because you need at least 1 move per square that is out of place, the number of squares out of place is guaranteed to be less than or equal to the number of moves required to solve the puzzle, making it an appropriate heuristic for A-Star.

这篇关于您如何使用 A-Star 或 Dijkstra 算法解决 15 难题?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！