在 Java 中使用迭代加深 A Star (IDA*) 解决 n 型拼图（滑动拼图）

Iterative Deepening A Star (IDA*) to solve n-puzzle (sliding puzzle) in Java

提问by Simon

I've implemented a program able to solve the n-puzzle problemwith A*. Since the space of the states is too big I cannot precompile it and I have to calculate the possible states at runtime. In this way A* works fine for a 3-puzzle, but for a 4-puzzle can take too long. Using Manhattan distance adjusted with linear conflicts, if the optimal solution requires around 25 moves is still fast, around 35 takes 10 seconds, for 40 takes 180 seconds. I haven't tried more yet.
I think that's because I must keep all visited states, since I'm using functions admissible but (I think) not consistent (i tried also with Hamming and Gaschnig distances and a few more). Since the space of the solution is a graph the heuristic must also be consistent, otherwise the algorithm can loop or be not optimal. That's why I keep all visited nodes (it's also written in the book "AI: A modern approach"). But anyway, this storage does not slow at all. What slows is keeping the queue of nodes to be visited ordered.
So I decided to try IDA* that, as I saw, does not require this storage (but still I have to keep all visited states to avoid loops). It's faster for solutions that require 35 or less moves, but for 40 it's much slower.
Here is my code. Am I doing something wrong?

我已经实现了一个能够用 A*解决n-puzzle 问题的程序。由于状态空间太大，我无法预编译它，我必须在运行时计算可能的状态。通过这种方式，A* 对于 3 拼图工作正常，但对于 4 拼图可能需要太长时间。使用经过线性冲突调整的曼哈顿距离，如果最优解需要大约 25 次移动仍然很快，大约 35 需要 10 秒，40 需要 180 秒。我还没有尝试更多。
我认为这是因为我必须保留所有访问过的状态，因为我使用的函数是可接受的，但（我认为）不一致（我也尝试过使用汉明距离和加施尼格距离等等）。由于解的空间是一个图，启发式也必须是一致的，否则算法可能会循环或不是最优的。这就是为什么我保留所有访问过的节点（这也写在“AI：一种现代方法”一书中）。但无论如何，这种存储一点也不慢。缓慢的是保持要访问的节点队列有序。
所以我决定尝试 IDA*，正如我所见，它不需要这种存储（但我仍然必须保留所有访问过的状态以避免循环）。对于需要 35 次或更少移动的解决方案，它更快，但对于 40 次，它要慢得多。
这是我的代码。难道我做错了什么？

public static State solveIDAStar(State initialState) {
    int limit = initialState.getManhattanDistance() + 2 * initialState.getLinearConflicts();
    State result = null;
    while(result == null) {
        visitedStates.add(initialState); // It's a global variable
        result = limitedSearch(initialState, limit);
        limit = newLimit;
        visitedStates.clear();
    }
    return result;
}

public static State limitedSearch(State current, int limit) {
    for(State s : current.findNext()) {
        if(s.equals(GOAL)) {
            s.setParent(current);
            return s;
        }
        if(!visitedStates.contains(s)) {
            s.setPathCost(current.getPathCost() + 1);
            s.setParent(current);
            int currentCost = s.getManhattanDistance() + 2 * s.getLinearConflicts() + s.getPathCost();
            if(currentCost <= limit) {
                visitedStates.add(s);
                State solution = limitedSearch(s, limit);
                if(solution != null)
                    return solution;
            } else {
                if(currentCost < newLimit)
                    newLimit = currentCost;
            }
        }
    }
    return null;
}

采纳答案by ronalchn

Old stuff moved down.

旧东西搬下来了。

Changes so that newLimit can skip steps (the bestSolution stuff):

更改以便 newLimit 可以跳过步骤（最好的解决方案）：

State bestSolution; // add this global

public static State solveIDAStar(State initialState) {
    int limit = initialState.getManhattanDistance() + 2 * initialState.getLinearConflicts();
    bestSolution = null; // reset global to null
    State result = null;
    while(result == null) {
        visitedStates.add(initialState); // It's a global variable
        newLimit = INFINITY;
        result = limitedSearch(initialState, limit);
        limit = newLimit;
        visitedStates.clear();
    }
    return result;
}

public static State limitedSearch(State current, int limit) {
    for(State s : current.findNext()) {
        if(s.equals(GOAL)) {
            s.setParent(current);
            return s;
        }
        if(!visitedStates.contains(s)) {
            s.setPathCost(current.getPathCost() + 1);
            s.setParent(current);
            int currentCost = s.getManhattanDistance() + 2 * s.getLinearConflicts() + s.getPathCost();
            if(currentCost <= limit) {
                visitedStates.add(s);
                State solution = limitedSearch(s, limit);
                if(solution != null &&
                   (bestSolution == null || solution.getPathCost() < bestSolution.getPathCost()))
                        bestSolution = solution; // cache solution so far
            } else {
                if(currentCost < newLimit)
                    newLimit = currentCost;
            }
        }
    }
    return null;
}

---

---

Original answer

原答案

So I found an open source implementation. Miraculously, it is also in java.

所以我找到了一个开源实现。神奇的是，它也在java中。

The application can be tested here: http://n-puzzle-solver.appspot.com/

该应用程序可以在这里测试：http: //n-puzzle-solver.appspot.com/

And the source code specifically relevant is: http://code.google.com/p/julien-labs/source/browse/trunk/SlidingPuzzle/src/be/dramaix/ai/slidingpuzzle/server/search/IDAStar.java

特别相关的源代码是：http: //code.google.com/p/julien-labs/source/browse/trunk/SlidingPuzzle/src/be/dramaix/ai/slidingpuzzle/server/search/IDAStar.java

Not sure how much the 1st change suggested below might change the time taken, but I am quite sure that you need to make the 2nd change.

不确定下面建议的第一次更改可能会改变花费的时间，但我很确定您需要进行第二次更改。

---

---

First change

第一次改变

By comparing the code, you will find that this function

通过对比代码，你会发现这个功能

private Node depthFirstSearch(Node current, int currentCostBound, State goal)

is basically your function here

基本上是你在这里的功能

public static State limitedSearch(State current, int limit)

and Julien Dramaix's implementation doesn't have:

和 Julien Dramaix 的实现没有：

if(!visitedStates.contains(s)) {
    ...
    visitedStates.add(s);

So take those two lines out to test.

所以把这两行拿出来测试。

---

---

2nd change

第二次改变

Your function public static State solveIDAStar(State initialState)does something weird in the while loop.

你的函数public static State solveIDAStar(State initialState)在 while 循环中做了一些奇怪的事情。

After you fail once, you set the maximum depth (limit) to infinity. Basically, 1st iteration, you try find a solution as good as your heuristic. Then you try to find any solution. This is not iterative deepening.

失败一次后，将最大深度（限制）设置为无穷大。基本上，在第一次迭代中，您尝试找到与启发式一样好的解决方案。然后你尝试找到任何解决方案。这不是迭代深化。

Iterative deepening means every time you try, go a little bit deeper.

迭代深化意味着每次尝试时，都要深入一点。

Indeed, looking at the while loop in public PuzzleSolution resolve(State start, State goal), you will find nextCostBound+=2;. That means, every time you try, try find solutions with up to 2 more moves.

确实，查看 中的 while 循环public PuzzleSolution resolve(State start, State goal)，您会发现nextCostBound+=2;. 这意味着，每次尝试时，请尝试通过最多 2 个动作找到解决方案。

---

---

Otherwise, everything else looks similar (although your exact implementation of the State class might be slightly different).

否则，其他一切看起来都相似（尽管您对 State 类的确切实现可能略有不同）。

If it works better, you might also want to try some of the other heuristics at http://code.google.com/p/julien-labs/source/browse/#svn%2Ftrunk%2FSlidingPuzzle%2Fsrc%2Fbe%2Fdramaix%2Fai%2Fslidingpuzzle%2Fclient.

如果效果更好，您可能还想在http://code.google.com/p/julien-labs/source/browse/#svn%2Ftrunk%2FSlidingPuzzle%2Fsrc%2Fbe%2Fdramaix%尝试其他一些启发式方法2Fai%2Fslidingpuzzle%2Fclient。

The heuristics are found in the server/search/heuristic folder.

启发式位于 server/search/heuristic 文件夹中。

回答by Raúl Ota?o

A small issue: you said "What slows is keeping the queue of nodes to be visited ordered.". In this case you can use a "Priority Heap". This is a partial ordered queue that always return the min (or max) item in e queue, insertions, retrieves - removes are O(log n), so this can make a bit fast your initial A* algorithm. Here a send you a simple implementation, but is made in C#, you need to translate it to Java...

一个小问题：你说“缓慢的是保持要访问的节点队列有序。”。在这种情况下，您可以使用“优先堆”。这是一个部分有序的队列，它总是返回 e 队列中的最小（或最大）项，插入，检索 - 删除是 O(log n)，所以这可以使你的初始 A* 算法有点快。这里向您发送一个简单的实现，但它是用 C# 制作的，您需要将其转换为 Java...

public class PriorityHeap<T>
{
    private int count;
    private int defaultLength = 10;
    private PriorityHeapNode[] array;
    private bool isMin;

    /// <summary>
    /// 
    /// </summary>
    /// <param name="isMin">true si quiere que la ColaHeap devuelva el elemento de menor Priority, falso si quiere que devuelva el de mayor</param>
    public PriorityHeap(bool isMin)
    {
        this.count = 0;
        this.isMin = isMin;
        this.array = new PriorityHeapNode[defaultLength];
    }
    public PriorityHeap(bool isMin, int iniLength)
    {
        this.count = 0;
        this.isMin = isMin;
        this.defaultLength = iniLength;
        this.array = new PriorityHeapNode[defaultLength];
    }

    public class PriorityHeapNode
    {
        T valor;
        int _priority;

        public PriorityHeapNode(T valor, int _priority)
        {
            this.valor = valor;
            this._priority = _priority;
        }

        public T Valor
        {
            get
            { return this.valor; }
        }
        public double Priority
        {
            get
            { return this._priority; }
        }

    }
    public int Count
    { get { return this.count; } }

    /// <summary>
    /// Devuelve true si la cola devuelve el valor de menor Priority, falso si el de mayor
    /// </summary>
    public bool IsMin
    { get { return isMin; } }

    /// <summary>
    /// Devuelve y quita el Valor Minimo si la cola lo permite,si no, retorna null
    /// </summary>
    /// <returns></returns>
    public PriorityHeapNode GetTopAndDelete()
    {
        PriorityHeapNode toRet;
        if (count > 0)
        {
            if (count == 1)
            {
                toRet = array[0];
                array[0] = null;
                count--;
                return toRet;
            }
            else
            {
                toRet = array[0];
                array[0] = array[count - 1];
                array[count - 1] = null;
                HeapyfiToDown(0);
                count--;
                return toRet;
            }
        }
        else return null;

    }

    /// <summary>
    /// Devuelve el tope pero no lo borra
    /// </summary>
    /// <returns></returns>
    public PriorityHeapNode GetTop()
    {
        return array[0];
    }
    public void Insert(PriorityHeapNode p)
    {
        if (array.Length == count)
            Add(p);
        else array[count] = p;
        count++;
        HeapyfiToUp(count - 1);
    }

    public void Clear()
    {
        count = 0;
    }

    #region Private Functions
    private int GetFather(int i)
    {
        return ((i + 1) / 2) - 1;
    }
    private int GetRightSon(int i)
    { return 2 * i + 2; }
    private int GetLeftSon(int i)
    { return 2 * i + 1; }

    private void Add(PriorityHeapNode p)
    {
        if (array.Length == count)
        {
            PriorityHeapNode[] t = new PriorityHeapNode[array.Length * 2];
            for (int i = 0; i < array.Length; i++)
            {
                t[i] = array[i];
            }
            t[count] = p;
            array = t;
        }
    }

    private void HeapyfiToUp(int i)
    {
        if (isMin)
        {
            int father = GetFather(i);
            if (father > -1 && array[father].Priority > array[i].Priority)
            {
                PriorityHeapNode t = array[father];
                array[father] = array[i];
                array[i] = t;
                HeapyfiToUp(father);
            }
        }
        else
        {
            int father = GetFather(i);
            if (father > -1 && array[father].Priority < array[i].Priority)
            {
                PriorityHeapNode t = array[father];
                array[father] = array[i];
                array[i] = t;
                HeapyfiToUp(father);
            }
        }
    }
    private void HeapyfiToDown(int i)
    {
        if (isMin)
        {
            #region HeapyFi To down Min
            int l = GetLeftSon(i);
            int r = GetRightSon(i);

            if (r < count)
            {
                PriorityHeapNode right = array[r];
                PriorityHeapNode left = array[l];
                int t;
                if (right != null && left != null)
                {
                    t = left.Priority < right.Priority ? l : r;
                }
                else if (right != null)
                    t = r;

                else if (left != null)
                    t = l;
                else return;

                if (array[t].Priority < array[i].Priority)
                {
                    PriorityHeapNode temp = array[t];
                    array[t] = array[i];
                    array[i] = temp;
                    HeapyfiToDown(t);
                }
            }
            else if (l < count)
            {
                PriorityHeapNode left = array[l];
                int t;
                if (left != null)
                    t = l;
                else return;
                if (array[t].Priority < array[i].Priority)
                {
                    PriorityHeapNode temp = array[t];
                    array[t] = array[i];
                    array[i] = temp;
                    HeapyfiToDown(t);
                }
            }
            #endregion
        }
        else
        {
            #region HeapyFi To down NOT Min
            int l = GetLeftSon(i);
            int r = GetRightSon(i);

            if (r < count)
            {
                PriorityHeapNode right = array[r];
                PriorityHeapNode left = array[l];
                int t;
                if (right != null && left != null)
                {
                    t = left.Priority > right.Priority ? l : r;
                }
                else if (right != null)
                    t = r;

                else if (left != null)
                    t = l;
                else return;

                if (array[t].Priority > array[i].Priority)
                {
                    PriorityHeapNode temp = array[t];
                    array[t] = array[i];
                    array[i] = temp;
                    HeapyfiToDown(t);
                }
            }
            else if (l < count)
            {
                PriorityHeapNode left = array[l];
                int t;
                if (left != null)
                    t = l;
                else return;
                if (array[t].Priority > array[i].Priority)
                {
                    PriorityHeapNode temp = array[t];
                    array[t] = array[i];
                    array[i] = temp;
                    HeapyfiToDown(t);
                }
            }
            #endregion
        }
    }
    #endregion
}      

Hope this helps...

希望这可以帮助...