1

正方形シフト パズル (解決されるまで正方形を空のスペースに移動するパズル) を解決するために、幅優先検索を実行しようとしています。私の幅優先アルゴリズムはキューを使用します。残念ながら、それは UP と DOWN のケースでのみ機能しているようで、LEFT や RIGHT のケースでは機能していないようです:

                if (up)
            {
                int[][] current = copy(v.state);
                current[x][y] = current[x - 1][y];
                current[x - 1][y] = 0;

                State w = new State(current);
                w.distance = v.distance + 1;
                w.path = v;
                System.out.println(q.insert(w));
            }

            if (down)
            {
                int[][] current = copy(v.state);
                current[x][y] = current[x + 1][y];
                current[x + 1][y] = 0;

                State w = new State(current);
                w.distance = v.distance + 1;
                w.path = v;
                System.out.println(q.insert(w));
            }

            if (left)
            {
                int[][] current = copy(v.state);
                current[x][y] = current[x][y - 1];
                current[x][y - 1] = 0;

                State w = new State(current);
                w.distance = v.distance + 1;
                w.path = v;
                System.out.println(q.insert(w));
            }

            if (right)
            {
                int[][] current = copy(v.state);
                current[x][y] = current[x][y + 1];
                current[x][y + 1] = 0;

                State w = new State(current);
                w.distance = v.distance + 1;
                w.path = v;
                System.out.println(q.insert(w));
            }

私のキューに問題があると思います。その実装は以下のとおりです。キューに何か問題がありますか、それとも別の問題ですか? Java API には、使用できるキュー クラスがありますか?

public class ArrayQueue {
State[] items;
int maxSize;
int front;
int rear;
int numItems;

public ArrayQueue(int max)
{
    items = new State[max];
    maxSize = max;
    front = 0;
    rear = -1;
    numItems = 0;
}

public boolean insert(State item)
{
    if (isFull()) return false;
    rear = (rear + 1) % items.length;
    items[rear] = item;
    return true;
}

public State remove()
{
    if (isEmpty()) return null;
    State removed = items[front];
    front = (front + 1) % items.length;
    return removed;
}

public boolean isFull()
{
    if ((front + 1) % maxSize == rear)
        return true;
    else
        return false;
}

public boolean isEmpty()
{
    if ((rear + 1) % maxSize == front)
            return true;
    else
        return false;
}
}

コピー方法は次のとおりです。

public static int[][] copy(int[][] input)       //This method is necessary because we are trying to clone a multi-dimensional array.
{                                               //Just using clone() will copy the outer arrays but they will be arrays of references to the original inner arrays.
int[][] output = new int[input.length][];
for (int i = 0; i < input.length; i++)
    output[i] = input[i].clone();
return output;
}
4

2 に答える 2

2

JDK は、ドキュメントの「すべての既知の実装クラス」セクションにあるインターフェイスQueueと多数の実装を提供します。Queue

あなたの目的には、LinkedListおそらく a で十分です。

于 2011-11-29T01:19:28.500 に答える
0

問題は「フロント」と「リア」にあると思います。最初は同じ位置 0 を指している必要があるため、それらが等しい場合、キューは空になります。'Rear' は書き込み位置 (書き込み、次にシフト) を指し、'front' は読み取り位置 (読み取り、次にシフト) を指します。キューがいっぱいになると、「リア」の方が速く進むようです。最後まで行くと、物乞いに戻ります。したがって、新しいアイテムを安全に挿入できるかどうかを確認するには、 (rear + 1) % max == front を実行する必要があります。

また、Siddiqui 氏が提案したように、いくつかの標準的な実装を使用することを検討してください。

于 2011-11-29T01:43:16.737 に答える