3

我已经实现了一个能够用 A*解决n 谜题的程序。由于状态空间太大，我无法预编译它，我必须在运行时计算可能的状态。以这种方式，A* 对于 3 拼图工作正常，但对于 4 拼图可能需要太长时间。使用通过线性冲突调整的曼哈顿距离，如果最优解需要大约 25 次移动仍然很快，大约 35 需要 10 秒，对于 40 需要 180 秒。我还没有尝试更多。
我认为那是因为我必须保留所有访问过的状态，因为我使用的函数是可接受的，但（我认为）不一致（我也尝试了 Hamming 和 Gaschnig 距离等等）。由于解决方案的空间是一个图，因此启发式也必须是一致的，否则算法可能会循环或不是最优的。这就是为什么我保留所有访问过的节点（它也写在“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;
}
4

2 回答 2

3

旧东西下移了。

更改以便 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;
}

原始答案

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

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

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

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

第一次改变

通过对比代码，你会发现这个函数

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

基本上是你在这里的功能

public static State limitedSearch(State current, int limit)

Julien Dramaix 的实现没有：

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

所以把这两条线拿出来测试一下。

第二次改变

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

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

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

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

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

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

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

于 2012-08-20T07:26:00.583 回答
0

一个小问题：您说“缓慢的是保持要访问的节点队列有序。”。在这种情况下，您可以使用“优先堆”。这是一个偏序队列，它总是返回 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
}

希望这可以帮助...

于 2012-10-15T21:07:20.850 回答