如果两个块tj和tk处于线性冲突中(如果tj和tk在同一行中),则tj和tk的目标位置都在该行中,tj在tk的右侧,而tj的目标位置在左侧tk的目标位置.
线性冲突通过迫使它们彼此包围,从而使两个冲突的图块的“曼哈顿距离”至少增加了两个移动.因此,启发式函数将为每对冲突的磁贴增加2个移动的成本.
Linar冲突启发法是可以接受的,但是我使用的算法有时会违反可接纳性,这意味着它是悲观的,不一定会找到最佳位置.
这是代码：
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个动作解决
解决方法:
线性冲突启发法比仅对每对冲突的瓦片加2更为复杂.
该算法在图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)