java - 线性冲突违反了可接受性并使我发疯

Question

当 tj 和 tk 两个瓦片发生线性冲突时，如果 tj 和 tk 在同一直线上，则 tj 和 tk 的目标位置都在该直线上，tj 在 tk 的右边，tj 的目标位置在在 tk 目标位置的左边。

线性冲突通过迫使它们相互包围，将至少两步移动到两个冲突板 block 的曼哈顿距离。因此，启发式函数将为每对冲突的图 block 增加 2 次移动的成本。

Linar Conflict Heuristic 是可接受的，但我使用的算法有时会违反可接受性，这意味着它是悲观的，不一定会找到最佳位置。

代码如下:

private int linearVerticalConflict(State s) {
    int state[] = s.getState();
    int dimension = (int) Math.sqrt(state.length);
    int linearConflict = 0;
    int count = 0;
    for (int row = 0; row < dimension; row++) {
        int max = -1;
        for (int column = 0; column < dimension; column++) {
            int cellValue = state[count];
            count++;
            //int cellValue = newState[row][column];
            //is tile in its goal row ?
            if (cellValue != 0 && (cellValue - 1) / dimension == row) {
                if (cellValue > max) {
                    max = cellValue;
                } else {
                    //linear conflict, one tile must move up or down to
                    // allow the other to pass by and then back up
                    //add two moves to the manhattan distance
                    linearConflict += 2;
                }
            }

        }

    }
    return linearConflict;
}

private int linearHorizontalConflict(State s) {
    int[] state = s.getState();
    int dimension = (int) Math.sqrt(state.length);
    int linearConflict = 0;
    int count = 0;
    for (int column = 0; column < dimension; column++) {
        int max = -1;
        for (int row = 0; row < dimension; row++) {
            int cellValue = state[count];
            count++;
            //is tile in its goal row ?
            if (cellValue != 0 && cellValue % dimension == column + 1) {
                if (cellValue > max) {
                    max = cellValue;
                } else {
                    //linear conflict, one tile must move left or right to allow the other to pass by and then back up
                    //add two moves to the manhattan distance
                    linearConflict += 2;
                }
            }

        }

    }
    return linearConflict;
}

该算法在以下情况下违反了可接受性:假设我们专注于具有配置的一行[ 3, 1, 2 ]

假设 [ 1, 2, 3 ] 是目标配置。

该问题的总曼哈顿距离为:4(3 次移动 2 次，1 次移动 1 次和 2 次移动 1 次)该行的线性冲突是:4(1 和 2 都小于 3，所以 +2+2)

这导致总体启发式估计为 8。[ 3, 1, 2 ] 可以用6步解决，

Answer 1

线性冲突启发式算法比仅仅为每对冲突的图 block 加 2 更复杂。

启发式在 "Criticizing Solutions to Relaxed ModelsYields Powerful Admissible Heuristics" by OTHAR HANSSON and ANDREW MAYER and MOTI YUNG in INFORMATION SCIENCES 63, 207-227 (1992) 中描述。

该算法在图 5 中进行了描述，涉及计算解决连续所有冲突所需的最少额外移动次数。正如您所发现的，这不等于冲突对数的两倍。

实际呈现的算法是:

Begin {Algorithm LC} 
{ s is the current state}
{ L is the size of a line (row or column) in the puzzle. L = sqrt( N + 1 )
{ C(tj, ri) is the number of tiles in row ri with which tj is in conflict} 
{ C(tj, ci) similarly}
{ lc(s, rj) is the number of tiles that must be removed from row rj to resolve the linear conflicts}
{ lc(s, cj) similarly}
{ md(s, ti) is the Manhattan Distance of tile ti} 
{ MD(s) is the sum of the Manhattan Distances of all the tiles in s} 
{ LC(s) is the minimum number of additional moves needed to resolve the linear conflicts in s} 
For each row ri in the state s 
   lc(s, ri) = 0
   For each tile tj in ri 
      determine C(tj, ri) 
   While there is a non-zero C(tj, ri) value 
       Find tk such that there is no 
          C(tj, ri) > C(tk, ri) { As tk is the tile with the most conflicts, we choose to move it out of ri }
       C(tk, ri) = 0 
       For every tile tj which had been in conflict with tk 
          C(tj, ri) = C(tj, ri) - 1 
       lc(s, ri) = lc(s, ri) + 1 
{ Check similarly for linear conflicts in each column ci, computing lc(s, cj ). }
LC(s) = 2[lc(s, r1) + . .. + lc(s, rL) + lc(s,ci) + . . . + lc(s, cL)] 
For each tile tj in s 
    determine md(s, tj) 
MD(s) = ms(s, t1) + ... + md(s, tn)
h(s) = MD(s) + LC(s) 

该算法计算启发式成本 h(s)