用Java实现限制每个状态的扩展不超过一次的权值递减迭代的Anytime repair Astar算法

限制每个状态的扩展不超过一次的权值递减迭代的Anytime repair Astar算法需要结合A*算法和Anytime repair A*算法进行实现。

首先，我们需要定义一个状态类来表示搜索状态，并且在状态类中增加以下字段：

- `g`：从起始状态到当前状态的实际代价。
- `h`：从当前状态到目标状态的估计代价。
- `f`：`g` 和 `h` 的和，即从起始状态到目标状态的估计代价。

然后，我们需要定义一个Open表和一个Closed表来存储已经探索过的状态和待探索的状态。在这个算法中，我们采用双向搜索，因此需要分别定义两个Open表和两个Closed表。

接下来，我们开始实现算法的主体部分。首先，我们从起始状态开始搜索，将起始状态加入Open表中。然后，我们开始循环处理Open表中的状态，直到找到目标状态或者Open表为空。

在每一次循环中，我们选取Open表中f值最小的状态进行扩展，得到其所有邻居状态。然后，我们对每个邻居状态进行如下处理：

- 如果邻居状态已经在Closed表中，则跳过不处理。
- 如果邻居状态已经在Open表中，则更新邻居状态的f值为更小的值，并将邻居状态的父状态设置为当前状态。
- 如果邻居状态不在Open表和Closed表中，则将邻居状态加入Open表中，并将其父状态设置为当前状态。

在对邻居状态进行处理后，我们将当前状态加入Closed表中，并更新当前状态的f值。如果当前状态是目标状态，则搜索结束，返回解路径；否则，继续循环处理Open表中的状态。

对于限制每个状态的扩展不超过一次的权值递减迭代的Anytime repair Astar算法，我们需要在上述算法的基础上进行修改。具体来说，我们需要增加一个阈值参数`w`，用于控制搜索的代价上限。在搜索过程中，如果当前状态的f值大于阈值`w`，则将当前状态加入Open表的备选列表中，而不是加入Closed表中。当搜索完成后，我们从备选列表中选取f值最小的状态作为新的起始状态，将阈值`w`减小为该状态的f值，并重新执行搜索。

实现代码如下：

public class State {
    private int[] board;
    private int g;
    private int h;
    private int f;
    private State parent;

    public State(int[] board, int g, int h, State parent) {
        this.board = board;
        this.g = g;
        this.h = h;
        this.f = g + h;
        this.parent = parent;
    }

    // getters and setters
}

public class AStar {
    private PriorityQueue<State> open;
    private PriorityQueue<State> open2;
    private Set<State> closed;
    private Set<State> closed2;
    private int[] goal;
    private int n;
    private int w;  // threshold

    public AStar(int[] start, int[] goal, int n) {
        this.open = new PriorityQueue<>(Comparator.comparingInt(State::getF));
        this.open2 = new PriorityQueue<>(Comparator.comparingInt(State::getF));
        this.closed = new HashSet<>();
        this.closed2 = new HashSet<>();
        this.goal = goal;
        this.n = n;
        this.w = n * n;  // initial threshold
        this.open.add(new State(start, 0, heuristic(start), null));
        this.open2.add(new State(goal, 0, heuristic(goal), null));
    }

    public List<int[]> search() {
        while (!open.isEmpty() && !open2.isEmpty()) {
            State current = open.poll();
            if (current.getF() > w) {
                open2.add(current);
                continue;
            }
            if (closed2.contains(current)) {
                return getPath(current).reversed().collect(Collectors.toList());
            }
            closed.add(current);
            for (State neighbor : getNeighbors(current)) {
                if (closed.contains(neighbor)) {
                    continue;
                }
                if (open.contains(neighbor)) {
                    neighbor = updateState(neighbor, current);
                } else {
                    neighbor.setParent(current);
                    open.add(neighbor);
                }
            }
            current = open2.poll();
            if (current.getF() > w) {
                open.add(current);
                continue;
            }
            if (closed.contains(current)) {
                return getPath(current).collect(Collectors.toList());
            }
            closed2.add(current);
            for (State neighbor : getNeighbors(current)) {
                if (closed2.contains(neighbor)) {
                    continue;
                }
                if (open2.contains(neighbor)) {
                    neighbor = updateState(neighbor, current);
                } else {
                    neighbor.setParent(current);
                    open2.add(neighbor);
                }
            }
            w--;  // decrease threshold
        }
        return null;  // no solution found
    }

    private int heuristic(int[] board) {
        int cost = 0;
        for (int i = 0; i < n * n; i++) {
            if (board[i] != 0) {
                int x = i / n;
                int y = i % n;
                int gx = (board[i] - 1) / n;
                int gy = (board[i] - 1) % n;
                cost += Math.abs(x - gx) + Math.abs(y - gy);
            }
        }
        return cost;
    }

    private List<State> getNeighbors(State state) {
        List<State> neighbors = new ArrayList<>();
        int i = 0;
        while (state.getBoard()[i] != 0) {
            i++;
        }
        int x = i / n;
        int y = i % n;
        if (x > 0) {
            int[] board = Arrays.copyOf(state.getBoard(), n * n);
            swap(board, i, i - n);
            neighbors.add(new State(board, state.getG() + 1, heuristic(board), null));
        }
        if (x < n - 1) {
            int[] board = Arrays.copyOf(state.getBoard(), n * n);
            swap(board, i, i + n);
            neighbors.add(new State(board, state.getG() + 1, heuristic(board), null));
        }
        if (y > 0) {
            int[] board = Arrays.copyOf(state.getBoard(), n * n);
            swap(board, i, i - 1);
            neighbors.add(new State(board, state.getG() + 1, heuristic(board), null));
        }
        if (y < n - 1) {
            int[] board = Arrays.copyOf(state.getBoard(), n * n);
            swap(board, i, i + 1);
            neighbors.add(new State(board, state.getG() + 1, heuristic(board), null));
        }
        return neighbors;
    }

    private State updateState(State neighbor, State current) {
        if (neighbor.getG() > current.getG() + 1) {
            neighbor.setG(current.getG() + 1);
            neighbor.setF(neighbor.getG() + neighbor.getH());
            neighbor.setParent(current);
        }
        return neighbor;
    }

    private void swap(int[] board, int i, int j) {
        int temp = board[i];
        board[i] = board[j];
        board[j] = temp;
    }

    private Stream<int[]> getPath(State state) {
        List<int[]> path = new ArrayList<>();
        while (state != null) {
            path.add(state.getBoard());
            state = state.getParent();
        }
        Collections.reverse(path);
        return path.stream();
    }
}

其中，`State`类表示搜索状态，包含了一个整数数组`board`、三个整数`g`、`h`和`f`，以及一个`parent`指向父状态。`AStar`类表示搜索算法，包含了两个优先队列`open`和`open2`、两个集合`closed`和`closed2`、一个整数数组`goal`、一个整数`n`和一个整数`w`，以及若干方法用于搜索。在构造函数中，我们将起始状态加入`open`中，将目标状态加入`open2`中，并初始化阈值`w`为`n * n`。`search`方法是算法的主体部分，其中的循环处理Open表的代码与标准A*算法类似，但增加了阈值判断和备选列表的处理。`heuristic`方法计算估价函数的值，`getNeighbors`方法获取邻居状态列表，`updateState`方法更新邻居状态的f值和父状态，`swap`方法交换数组中的两个元素，`getPath`方法获取解路径。

需要注意的是，由于本算法使用的是双向搜索，因此解路径可能是从起始状态到目标状态或从目标状态到起始状态，因此在对解路径进行输出时，需要判断一下解路径的方向，并进行翻转。

完整的Java代码如下：