java - 8パズルソリューションは無限に実行されます

Question

を使用して8 パズル問題の解決策を探していA* Algorithmます。このプロジェクトはインターネットで見つけました。proj1ファイルとを参照してくださいEightPuzzle。proj1 にはプログラム (関数) のエントリ ポイントが含まれておりmain()、EightPuzzle にはパズルの特定の状態が記述されています。各状態は 8 パズルのオブジェクトです。
ロジックに問題はないと思います。しかし、私が試した次の 2 つの入力に対しては永遠にループします:{8,2,7,5,1,6,3,0,4}と{3,1,6,8,4,5,7,2,0}. どちらも有効な入力状態です。コードの何が問題になっていますか?

---

ノート

• コードには多くのコメントがあるため、見やすくするために、コードを Notepad++ またはその他のテキスト エディター (Java ソース ファイルを認識する機能がある) にコピーします。
• A* はヒューリスティックを必要とするため、マンハッタン距離を使用するオプションと、間違って配置されたタイルの数を計算するヒューリスティックを提供しています。そして、最良のヒューリスティックが最初に実行されるようにするために、PriorityQueue. compareTo() 関数はEightPuzzleクラスに実装されています。
• プログラムへの入力は、クラスの関数p1d内の値を変更することで変更できます。main()proj1
• 上記の 2 つの入力に対する解決策があると言っている理由は、ここのアプレットがそれらを解決するからです。アプレットのオプションから 8 パズルを選択してください。
  
  EDIT1
  私はこの入力を与えました{0,5,7,6,8,1,2,4,3}。約26手10 secondsで結果が出ました。しかし、アプレットはin with で結果を出しました。 EDIT2 デバッグ中に、ノードが展開されると、新しいノードには、しばらくするとすべてのヒューリスティックがあることに気付きました - asまたは. それらは決して減少しているようには見えません。しばらくすると、すべての州が24 moves0.0001 secondsA*


f_n1112PriorityQueue(openset)ヒューリスティックは 11 または 12 です。そのため、どのノードに拡張するかを選択する必要はあまりありません。最小は 11 で、最大は 12 です。これは正常ですか?
  
  EDIT3これは、無限ループが発生
  するスニペット ( proj1-astar()内) です。opensetは展開されていないノードを含む PriorityQueue であり、closedset は展開されたノードを含むLinkedListです。
  

while(openset.size() > 0){

                    EightPuzzle x = openset.peek();


                    if(x.mapEquals(goal))
                    {

                             Stack<EightPuzzle> toDisplay = reconstruct(x);
                             System.out.println("Printing solution... ");
                             System.out.println(start.toString());
                             print(toDisplay);
                             return;
                             
                    }          
                    closedset.add(openset.poll());
                    LinkedList <EightPuzzle> neighbor = x.getChildren();              
                    while(neighbor.size() > 0)
                    {
                            EightPuzzle y = neighbor.removeFirst();
                            if(closedset.contains(y)){
                                    continue;
                            }          
                            if(!closedset.contains(y)){
                                    openset.add(y);
                            }              
                    }
               
            }

---

EDIT4

この無限ループの原因がわかりました。私の答えを見てください。ただし、実行には約25 ～ 30 秒かかります。これはかなり長い時間です。A* はこれよりもはるかに高速に実行する必要があります。アプレットはこれを0.003 秒で実行します。業績向上の報奨金を授与します。

---

簡単に参照できるように、コメントなしで 2 つのクラスを貼り付けました。

Eightパズル

 import java.util.*;
    
    public class EightPuzzle implements Comparable <Object> {
           
           
            int[] puzzle = new int[9];
            int h_n= 0;
            int hueristic_type = 0;
            int g_n = 0;
            int f_n = 0;
            EightPuzzle parent = null;
    
           
            public EightPuzzle(int[] p, int h_type, int cost)
            {
                    this.puzzle = p;
                    this.hueristic_type = h_type;
                    this.h_n = (h_type == 1) ?  h1(p) : h2(p);
                    this.g_n = cost;
                    this.f_n = h_n + g_n;
            }
            public int getF_n()
            {
                    return f_n;
            }
            public void setParent(EightPuzzle input)
            {
                    this.parent = input;
            }
            public EightPuzzle getParent()
            {
                    return this.parent;
            }
    
            public int inversions()
            {
                    /*
                     * Definition: For any other configuration besides the goal,
                     * whenever a tile with a greater number on it precedes a
                     * tile with a smaller number, the two tiles are said to be inverted
                     */
                    int inversion = 0;
                    for(int i = 0; i < this.puzzle.length; i++ )
                    {
                            for(int j = 0; j < i; j++)
                            {
                                    if(this.puzzle[i] != 0 && this.puzzle[j] != 0)
                                    {
                                    if(this.puzzle[i] < this.puzzle[j])
                                            inversion++;
                                    }
                            }
    
                    }
                    return inversion;
                   
            }
            public int h1(int[] list)
            // h1 = the number of misplaced tiles
            {
                    int gn = 0;
                    for(int i = 0; i < list.length; i++)
                    {
                            if(list[i] != i && list[i] != 0)
                                    gn++;
                    }
                    return gn;
            }
            public LinkedList<EightPuzzle> getChildren()
            {
                    LinkedList<EightPuzzle> children = new LinkedList<EightPuzzle>();
                    int loc = 0;
            int temparray[] = new int[this.puzzle.length];
            EightPuzzle rightP, upP, downP, leftP;
                    while(this.puzzle[loc] != 0)
                    {
                            loc++;
                    }
                    if(loc % 3 == 0){
                            temparray = this.puzzle.clone();
                            temparray[loc] = temparray[loc + 1];
                            temparray[loc + 1] = 0;
                            rightP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
                            rightP.setParent(this);
                            children.add(rightP);
    
                    }else if(loc % 3 == 1){
                    //add one child swaps with right
                            temparray = this.puzzle.clone();
                            temparray[loc] = temparray[loc + 1];
                            temparray[loc + 1] = 0;
                           
                            rightP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
                            rightP.setParent(this);
                            children.add(rightP);
                            //add one child swaps with left
                            temparray = this.puzzle.clone();
                            temparray[loc] = temparray[loc - 1];
                            temparray[loc - 1] = 0;
                           
                            leftP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
                            leftP.setParent(this);
                            children.add(leftP);
                    }else if(loc % 3 == 2){
                    // add one child swaps with left
                            temparray = this.puzzle.clone();
                            temparray[loc] = temparray[loc - 1];
                            temparray[loc - 1] = 0;
                           
                            leftP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
                            leftP.setParent(this);
                            children.add(leftP);
                    }              
                   
                    if(loc / 3 == 0){
                    //add one child swaps with lower
                            temparray = this.puzzle.clone();
                            temparray[loc] = temparray[loc + 3];
                            temparray[loc + 3] = 0;
                           
                            downP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
    
                            downP.setParent(this);
    
                            children.add(downP);
                   
                           
                    }else if(loc / 3 == 1 ){
                            //add one child, swap with upper
                            temparray = this.puzzle.clone();
                            temparray[loc] = temparray[loc - 3];
                            temparray[loc - 3] = 0;
                           
                            upP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
                            upP.setParent(this);
    
                            children.add(upP);
                            //add one child, swap with lower
                            temparray = this.puzzle.clone();
                            temparray[loc] = temparray[loc + 3];
                            temparray[loc + 3] = 0;
                           
                            downP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
                            downP.setParent(this);
    
                            children.add(downP);
                    }else if (loc / 3 == 2 ){
                            //add one child, swap with upper
                            temparray = this.puzzle.clone();
                            temparray[loc] = temparray[loc - 3];
                            temparray[loc - 3] = 0;
                           
                            upP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
                            upP.setParent(this);
    
                            children.add(upP);
                    }
    
                    return children;
            }
            public int h2(int[] list)
            // h2 = the sum of the distances of the tiles from their goal positions
            // for each item find its goal position
            // calculate how many positions it needs to move to get into that position
            {
                    int gn = 0;
                    int row = 0;
                    int col = 0;
                    for(int i = 0; i < list.length; i++)
                    {
                            if(list[i] != 0)
                            {
                                    row = list[i] / 3;
                                    col = list[i] % 3;
                                    row = Math.abs(row - (i / 3));
                                    col = Math.abs(col - (i % 3));
                                    gn += row;
                                    gn += col;
                            }
                           
                    }
                    return gn;
            }
    
            public String toString()
            {
                    String x = "";
                    for(int i = 0; i < this.puzzle.length; i++){
                            x += puzzle[i] + " ";
                            if((i + 1) % 3 == 0)
                                    x += "\n";
                    }
                    return x;
            }
            public int compareTo(Object input) {
                   
                   
                    if (this.f_n < ((EightPuzzle) input).getF_n())
                            return -1;
                    else if (this.f_n > ((EightPuzzle) input).getF_n())
                            return 1;
                    return 0;
            }
           
            public boolean equals(EightPuzzle test){
                    if(this.f_n != test.getF_n())
                            return false;
                    for(int i = 0 ; i < this.puzzle.length; i++)
                    {
                            if(this.puzzle[i] != test.puzzle[i])
                                    return false;
                    }
                    return true;
            }
            public boolean mapEquals(EightPuzzle test){
                    for(int i = 0 ; i < this.puzzle.length; i++)
                    {
                            if(this.puzzle[i] != test.puzzle[i])
                                    return false;
                    }
                    return true;
            }
    
    }

プロジェクト1

import java.util.*;

public class proj1 {

        /**
         * @param args
         */
       
        public static void main(String[] args) {
               
               
                int[] p1d = {1, 4, 2, 3, 0, 5, 6, 7, 8};
                int hueristic = 2;
                EightPuzzle start = new EightPuzzle(p1d, hueristic, 0);
                int[] win = { 0, 1, 2,
                                          3, 4, 5,
                                          6, 7, 8};
                EightPuzzle goal = new EightPuzzle(win, hueristic, 0);
               
                astar(start, goal);

               

        }
       
        public static void astar(EightPuzzle start, EightPuzzle goal)
        {
                if(start.inversions() % 2 == 1)
                {
                        System.out.println("Unsolvable");
                        return;
                }
//              function A*(start,goal)
//           closedset := the empty set                 // The set of nodes already evaluated.
                LinkedList<EightPuzzle> closedset = new LinkedList<EightPuzzle>();
//           openset := set containing the initial node // The set of tentative nodes to be evaluated. priority queue
                PriorityQueue<EightPuzzle> openset = new PriorityQueue<EightPuzzle>();

                openset.add(start);
               

                while(openset.size() > 0){
//               x := the node in openset having the lowest f_score[] value
                        EightPuzzle x = openset.peek();

//               if x = goal
                        if(x.mapEquals(goal))
                        {
//                   return reconstruct_path(came_from, came_from[goal])
                                 Stack<EightPuzzle> toDisplay = reconstruct(x);
                                 System.out.println("Printing solution... ");
                                 System.out.println(start.toString());
                                 print(toDisplay);
                                 return;
                                 
                        }
//               remove x from openset
//               add x to closedset
                        closedset.add(openset.poll());
                        LinkedList <EightPuzzle> neighbor = x.getChildren();
//               foreach y in neighbor_nodes(x)                
                        while(neighbor.size() > 0)
                        {
                                EightPuzzle y = neighbor.removeFirst();
//                   if y in closedset
                                if(closedset.contains(y)){
//                       continue
                                        continue;
                                }
//                   tentative_g_score := g_score[x] + dist_between(x,y)
//      
//                   if y not in openset
                                if(!closedset.contains(y)){
//                       add y to openset
                                        openset.add(y);
//                      
                                }
//                 
                        }
//               
                }
        }

        public static void print(Stack<EightPuzzle> x)
        {
                while(!x.isEmpty())
                {
                        EightPuzzle temp = x.pop();
                        System.out.println(temp.toString());
                }
        }

        public static Stack<EightPuzzle> reconstruct(EightPuzzle winner)
        {
                Stack<EightPuzzle> correctOutput = new Stack<EightPuzzle>();
               
                while(winner.getParent() != null)
                {
                correctOutput.add(winner);
                winner = winner.getParent();
                }

                return correctOutput;
        }
       
        }
   

Answer 1

これが提案です。あなたの例では、私のタイマーは0ミリ秒を報告します。ここで示した難しいパズルでは、完了するまでに31回の移動が必要であり、96ミリ秒かかります。

AHashSetは、リンクリストよりも閉集合の方がはるかに理にかなっています。O（1）時間挿入とメンバーシップテストがあり、リンクリストにはリストの長さに比例した時間が必要であり、これは絶えず増加しています。

プログラムを必要以上に複雑にし、遅くする余分なデータ構造とコードを使用しています。これを克服するために、もっと考え、コードを減らし、他の人の良いコードを研究してください。鉱山は完璧ではありませんが（コードはありません）、出発点です。

ヒューリスティックとして、各タイルの現在の位置からその目標までのマンハッタン距離の最大値を使用しました。ヒューリスティックの選択は、ソリューションのステップ数には影響しませんが、実行時間には大きく影響します。たとえば、h = 0は、ブルートフォース幅優先探索を生成します。

A *が最適なソリューションを提供するために、ヒューリスティックが目標までの実際の最小ステップ数を過大評価することは決してないことに注意してください。もしそうなら、解決策は、発見が可能な限り最短ではないかもしれないということです。私は、ヒューリスティックな「転回形」がこの特性を持っているとは確信していません。

package eightpuzzle;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;

public class EightPuzzle {

    // Tiles for successfully completed puzzle.
    static final byte [] goalTiles = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };

    // A* priority queue.
    final PriorityQueue <State> queue = new PriorityQueue<State>(100, new Comparator<State>() {
        @Override
        public int compare(State a, State b) { 
            return a.priority() - b.priority();
        }
    });

    // The closed state set.
    final HashSet <State> closed = new HashSet <State>();

    // State of the puzzle including its priority and chain to start state.
    class State {
        final byte [] tiles;    // Tiles left to right, top to bottom.
        final int spaceIndex;   // Index of space (zero) in tiles  
        final int g;            // Number of moves from start.
        final int h;            // Heuristic value (difference from goal)
        final State prev;       // Previous state in solution chain.

        // A* priority function (often called F in books).
        int priority() {
            return g + h;
        }

        // Build a start state.
        State(byte [] initial) {
            tiles = initial;
            spaceIndex = index(tiles, 0);
            g = 0;
            h = heuristic(tiles);
            prev = null;
        }

        // Build a successor to prev by sliding tile from given index.
        State(State prev, int slideFromIndex) {
            tiles = Arrays.copyOf(prev.tiles, prev.tiles.length);
            tiles[prev.spaceIndex] = tiles[slideFromIndex];
            tiles[slideFromIndex] = 0;
            spaceIndex = slideFromIndex;
            g = prev.g + 1;
            h = heuristic(tiles);
            this.prev = prev;
        }

        // Return true iif this is the goal state.
        boolean isGoal() {
            return Arrays.equals(tiles, goalTiles);
        }

        // Successor states due to south, north, west, and east moves.
        State moveS() { return spaceIndex > 2 ? new State(this, spaceIndex - 3) : null; }       
        State moveN() { return spaceIndex < 6 ? new State(this, spaceIndex + 3) : null; }       
        State moveE() { return spaceIndex % 3 > 0 ? new State(this, spaceIndex - 1) : null; }       
        State moveW() { return spaceIndex % 3 < 2 ? new State(this, spaceIndex + 1) : null; }

        // Print this state.
        void print() {
            System.out.println("p = " + priority() + " = g+h = " + g + "+" + h);
            for (int i = 0; i < 9; i += 3)
                System.out.println(tiles[i] + " " + tiles[i+1] + " " + tiles[i+2]);
        }

        // Print the solution chain with start state first.
        void printAll() {
            if (prev != null) prev.printAll();
            System.out.println();
            print();
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof State) {
                State other = (State)obj;
                return Arrays.equals(tiles, other.tiles);
            }
            return false;
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(tiles);
        }
    }

    // Add a valid (non-null and not closed) successor to the A* queue.
    void addSuccessor(State successor) {
        if (successor != null && !closed.contains(successor)) 
            queue.add(successor);
    }

    // Run the solver.
    void solve(byte [] initial) {

        queue.clear();
        closed.clear();

        // Click the stopwatch.
        long start = System.currentTimeMillis();

        // Add initial state to queue.
        queue.add(new State(initial));

        while (!queue.isEmpty()) {

            // Get the lowest priority state.
            State state = queue.poll();

            // If it's the goal, we're done.
            if (state.isGoal()) {
                long elapsed = System.currentTimeMillis() - start;
                state.printAll();
                System.out.println("elapsed (ms) = " + elapsed);
                return;
            }

            // Make sure we don't revisit this state.
            closed.add(state);

            // Add successors to the queue.
            addSuccessor(state.moveS());
            addSuccessor(state.moveN());
            addSuccessor(state.moveW());
            addSuccessor(state.moveE());
        }
    }

    // Return the index of val in given byte array or -1 if none found.
    static int index(byte [] a, int val) {
        for (int i = 0; i < a.length; i++)
            if (a[i] == val) return i;
        return -1;
    }

    // Return the Manhatten distance between tiles with indices a and b.
    static int manhattanDistance(int a, int b) {
        return Math.abs(a / 3 - b / 3) + Math.abs(a % 3 - b % 3);
    }

    // For our A* heuristic, we just use max of Manhatten distances of all tiles.
    static int heuristic(byte [] tiles) {
        int h = 0;
        for (int i = 0; i < tiles.length; i++)
            if (tiles[i] != 0)
                h = Math.max(h, manhattanDistance(i, tiles[i]));
        return h;
    }

    public static void main(String[] args) {

        // This is a harder puzzle than the SO example
        byte [] initial = { 8, 0, 6, 5, 4, 7, 2, 3, 1 };

        // This is taken from the SO example.
        //byte [] initial = { 1, 4, 2, 3, 0, 5, 6, 7, 8 };

        new EightPuzzle().solve(initial);
    }
}

Answer 2

問題が見つかりました。これは、ノードがclosedsetに存在するかどうかを確認するために使用される条件です

if(!closedset.contains(y))

linkedlist(closedset) は、クラス (この場合はEightPuzzle ) のequals()を呼び出して、 contains()を実行します。EightPuzzleの equals 関数は次のように定義されます。

public boolean equals(EightPuzzle test){

                if(this.f_n != ((EightPuzzle)test).getF_n())
                       return false;
            //System.out.println("in equals");
                for(int i = 0 ; i < this.puzzle.length; i++)
                {
                        if(this.puzzle[i] != ((EightPuzzle)test).puzzle[i])
                                return false;
                }
                return true;
        }

しかし、Objectクラスのequals()をオーバーライドしたい場合、正しいシグネチャは

 public boolean equals(Object test). 

もう 1 つ変更が必要です- equals() の最初の 2 行をコメント化します。

答えがわかりました。ただし、一部の入力にはまだ25 ～ 30秒かかります。これは A* では想定されていません。アプレットは0.003 秒でパズルを解きます。誰かがパフォーマンスを改善する方法を知っている場合は、教えてください。
その人に賞金を授与します。

Answer 3

別のフォーラムから最適化の答えを得ました。とをそれぞれに

変更します。リスト全体を繰り返し、リストが大きくなるにつれて、ますます時間がかかります。また 、を呼び出してxを再利用する代わりに、を変更して再利用します。openset.size()neightbor.size()

openset.isEmpty()neightbor.isEmpty()

size()EightPuzzle x = openset.peek();

EightPuzzle x = openset.poll();peek()poll()

今それは内で処理します1 second

Answer 4

コードに問題はないと思いますが、すべての 8 パズル問題が解けるわけではないことに注意してください。まず、「{8,2,7,5,1,6,3,0,4} と {3,1,6,8,4,5,7,2,0}」が解ける 8 パズルかどうかを確認してください.