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文档的“所有已知的实现类”部分找到。

出于您的目的， aLinkedList应该足够好。

于 2011-11-29T01:19:28.500 回答
0

我想，问题在于“前”和“后”。它们一开始需要指向同一个位置0，所以当它们相等时，队列为空。'Rear' 将指向要写入的位置（写入，然后向前移动），'front' 将指向要读取的位置（读取然后移动）。队列填满时，“后方”似乎前进得更快。当它走到尽头时，它会回到乞讨。因此，您需要执行 (rear + 1) % max == front 来检查是否可以安全地插入新项目。

此外，请考虑使用一些标准实现，正如 Siddiqui 先生所建议的那样。

于 2011-11-29T01:43:16.737 回答