您如何用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屋！