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

Question

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

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

线性冲突启发式是可以接受的，但我使用的算法有时会违反可接受性，这意味着它是悲观的，不一定会找到最佳位置。

代码如下：

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

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

启发式在“批评松弛模型的解决方案”中有所描述 Yields Powerful Admissible Heuristics"，作者：OTHAR HANSSON、ANDREW MAYER 和 MOTI YUNG，信息科学 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)

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

Linear Conflict violating admissibility and driving me insane

java

algorithm

heuristics