java - 广度优先搜索实现不起作用

Question

我对广度优先搜索算法的实现有疑问，我有一个方法可以给我一个 0-8 的整数数组，顺序随机。我还有一个整数 m 告诉我哪个数字是空白的。以下是规则:

我得到一组数字，例如:

456           
782        
301

假设 8 是空白值，我可以将它与 5、7、2 和 0 交换。因为它们紧挨着它。我必须使用广度优先搜索来解决这个难题。这是我到目前为止编写的代码:

package application;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Vector;

public class Solution {

    /******************************************
     * Implementation Here
     ***************************************/

    /*
     * Implementation here: you need to implement the Breadth First Search
     * Method
     */
    /* Please refer the instruction document for this function in details */

    public static LinkedHashSet<int[]> OPEN = new LinkedHashSet<int[]>();
        public static HashSet<int[]> CLOSED = new HashSet<int[]>();
    public static boolean STATE = false;
    public static int empty;

    public static void breadthFirstSearch(int[] num, int m, Vector solution1) {
        int statesVisited = 0;
        for(int i : num) {
            if(num[i] == m) {
                empty = i;
            }
        }

        int[] start = num;
        int[] goal = {0,1,2,3,4,5,6,7,8};
        int[] X;
        int[] temp = {};

        OPEN.add(start);

        while (OPEN.isEmpty() == false && STATE == false) {

            X = OPEN.iterator().next();
            OPEN.remove(X);

            int pos = empty; // get position of ZERO or EMPTY SPACE
            if (compareArray(X,goal)) {
                System.out.println("SUCCESS");

                STATE = true;
            } else {
                // generate child nodes
                CLOSED.add(X);

                temp = up(X, pos);
                if (temp != null)
                    OPEN.add(temp);
                temp = left(X, pos);
                if (temp != null)
                    OPEN.add(temp);
                temp = down(X, pos);
                if (temp != null)
                    OPEN.add(temp);
                temp = right(X, pos);
                if (temp != null)
                    OPEN.add(temp);
                if(OPEN.isEmpty()) 
                    System.out.println("Ending loop");
            }
        }

    }
    public static boolean compareArray(int[] a, int[] b) {
        for(int i: a) 
            if(a[i] != b[i])
                return false;

        return true;

    }

    public static int[] up(int[] s, int p) {
        int[] str = s;
        if (p > 3) {
            int temp = str[p-3];
            str[p-3] = str[p];
            str[p] = temp;


        }
        // Eliminates child of X if its on OPEN or CLOSED
        if (!OPEN.contains(str) && CLOSED.contains(str) == false)
            return str;
        else
            return null;
    }


    public static int[] down(int[] s, int p) {
        int[] str = s;
        if (p < 6) {
            int temp = str[p+3];
            str[p+3] = str[p];
            str[p] = temp;

        }

        // Eliminates child of X if its on OPEN or CLOSED
        if (!OPEN.contains(str) && CLOSED.contains(str) == false)
            return str;
        else
            return null;
    }


    public static int[] left(int[] s, int p) {
        int[] str = s;
        if (p != 0 && p != 3 && p != 6) {
            int temp = str[p-1];
            str[p-1] = str[p];
            str[p] = temp;

        }
        // Eliminates child of X if its on OPEN or CLOSED
        if (!OPEN.contains(str) && CLOSED.contains(str) == false)
            return str;
        else
            return null;
    }


    public static int[] right(int[] s, int p) {
        int[] str = s;
        if (p != 2 && p != 5 && p != 8) {
            int temp = str[p+1];
            str[p+1] = str[p];
            str[p] = temp;
        }
        // Eliminates child of X if its on OPEN or CLOSED
        if (!OPEN.contains(str) && CLOSED.contains(str) == false)
            return str;
        else
            return null;
    }
    public static void print(String s) {
        System.out.println(s.substring(0, 3));
        System.out.println(s.substring(3, 6));
        System.out.println(s.substring(6, 9));
        System.out.println();
    }
}

此代码立即结束，永远找不到答案。也许我做错了什么？请帮忙。

请注意:这是我在 StackOverFlow 上的第一个问题，所以如果有人有任何批评请告诉我，我会立即解决。

Answer 1

首先，你有一个没有做任何事情的参数，Vector solution in:

public static void breadthFirstSearch(int[] num, int m, Vector solution1)

此外，您还传递了您表示为 m 的零元素的位置，然后将局部变量分配给该位置，对我来说似乎有点毫无意义如果您要去，则无需传递零位置无论如何都要搜索它。

更新广度优先搜索方法:

public static void breadthFirstSearch(int[] num) {
    for (int i : num) {
        if (num[i] == 0) {
            empty = i;
        }
    }

    int[] start = num;
    int[] goal = {1, 2, 3, 4, 5, 6, 7, 8, 0};
    int[] X;
    int[] temp = {};

    OPEN.add(start);

    while (OPEN.isEmpty() == false && STATE == false) {

        X = OPEN.iterator().next();
        OPEN.remove(X);
        int pos = empty; // get position of ZERO or EMPTY SPACE
        if (Arrays.equals(X, goal)) {
            System.out.println("SUCCESS");
            STATE = true;
        } else {
            // generate child nodes
            CLOSED.add(X);
            temp = up(X, pos);
            if (temp != null) {
                OPEN.add(temp);
            }
            temp = left(X, pos);
            if (temp != null) {
                OPEN.add(temp);
            }
            temp = down(X, pos);
            if (temp != null) {
                OPEN.add(temp);
            }
            temp = right(X, pos);
            if (temp != null) {
                OPEN.add(temp);
            }
            if (OPEN.isEmpty()) {
                System.out.println("Ending loop");
            }
        }
    }
}

您的程序的主要问题是在您的移动方法中 up()、down()、left() , 对()。您没有创建数组的完整副本，因此导致对原始数组进行修改。

因此这个任务:int[] str = s;

必须改为:

   int[] str = new int[s.length];
   System.arraycopy(s, 0, str, 0, s.length);

这是一个已完成方法的示例:

public static int[] up(int[] s, int p) {
    int[] str = new int[s.length];
    System.arraycopy(s, 0, str, 0, s.length);

    if (p > 3) {
        int temp = str[p - 3];
        str[p - 3] = str[p];
        str[p] = temp;
    }
    // Eliminates child of X if its on OPEN or CLOSED
    if (!OPEN.contains(str) && !CLOSED.contains(str)) {
        return str;
    } else {
        return null;
    }
}

边注(非必需):

数组的某些排列不会导致目标状态。这个谜题本身总共可以有 9! 个配置，但实际上只有 9!/2 个可以解决。

我写了一个算法来检查 parity这个谜题的一部分，可以作为一种预处理来完成，我用它来创建随机实例来测试数据。

public  boolean isSolvable(int[] puzzle) {
    boolean parity = true;
    int gridWidth = (int) Math.sqrt(puzzle.length);
    boolean blankRowEven = true; // the row with the blank tile

    for (int i = 0; i < puzzle.length; i++) {
        if (puzzle[i] == 0) { // the blank tile
            blankRowEven = (i / gridWidth) % 2==0;
            continue;
        }
        for (int j = i + 1; j < puzzle.length; j++) {
            if (puzzle[i] > puzzle[j] && puzzle[j] != 0) {
                parity = !parity;
            }
        }
    }

    // even grid with blank on even row; counting from top
    if (gridWidth % 2 == 0 && blankRowEven) { 
        return !parity;
    }
    return parity;
}

对于 vector

您希望能够打印出到达目标状态所经过的路径，我建议为 State 创建一个类，例如:

private State previousState;
private int[] current;

public State(int[] current, State previousState) {
    this.current = current;
    this.previousState = previousState
}

public State getPreviouState(){
    return previousState;
}
public int[] getCurrentState(){
    return currentState;
}

然后当您有了目标 State 时，您可以循环遍历所有先前的 States 以查看它所采用的路径。

State current = GOAL;
while(current != null){
    System.out.println(Arrays.toString(current));
    current = current.getPreviousState();
}