2
두 개의 타일 tj와 tk가 tj와 tk가 같은 라인에있는 경우 선형 충돌이 발생하면 tj와 tk의 목표 위치는 모두 해당 라인에 있고 tj는 오른쪽입니다 tk의 목표 위치와 tj의 목표 위치는 tk의 목표 위치의 왼쪽에있다.선형 충돌이 허용을 위반하고 나를 미치게 함
선형 충돌로 인해 서로 충돌하는 두 타일의 맨하탄 거리가 서로를 둘러싸도록하여 두 개 이상의 움직임을 추가합니다. 따라서 휴리스틱 함수는 충돌하는 각 쌍의 타일에 대해 2 개의 이동 비용을 추가합니다.
Linar 충돌 휴리스틱 스는 허용되지만, 때때로 사용하고있는 알고리즘이 허용 가능성을 위반하여 비관적이며 반드시 최적의 위치를 찾지는 못합니다. 가 [3, 1, 2]
의 [1을 가정 해 봅시다 우리가 구성이 하나의 행에 초점을 맞추고있다 말 : 때
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;
}
알고리즘은 적격성을 위반 : 여기
코드입니다 , 2, 3]은 목표 구성입니다.문제의 총 맨하탄 거리 : 4 (3 동작 2 번, 1 동작 1 시간 및 2 동작 1 시간) 행에 대한 선형 충돌은 4입니다 (1과 2는 둘 다 3보다 작습니다. + 2 + 2)
(8)의 전체 휴리스틱 추정 결과[3, 1, 2]