Почему эта головоломка с восьмью решаема?

Итак, я пишу программу для решения 8 головоломок, используя BFS, A * и UCS. Состояние цели фиксировано в соответствии с назначением, которое задается следующим образом:

Goal State:
|1 2 3|
|8   4|
|7 6 5|   

My Initial State:
|  1 2| 
|8 4 3| 
|7 6 5|

Однако при написании метода getInvCount(int [] a):

public static boolean getInvCount(int [] a)
{
    int [] arr = a;
    int inv_count = 0;
    for(int i = 0;i<arr.length-1;i++){
        for(int j = i + 1; j < arr.length;j++){
            if(arr[i]>arr[j]){
                inv_count++;
                
            }
        }
        
    }
    System.out.println(inv_count);

Я понимаю, что исходная головоломка имеет 9 инверсий, что является нечетным числом. Тем не менее, программа успешно находит решение. Есть ли что-то, что я упустил в требованиях, чтобы головоломка считалась решаемой?


artificial-intelligence a-star breadth-first-search inversion sliding-tile-puzzle
person Jaime Garcia    schedule 21.10.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Ваша функция getInvCount действительна только для целевого состояния 1 2 3 4 5 6 7 8. Инверсия — это когда две плитки находятся в другом порядке, чем в целевом состоянии. Сравнение arr[i] > arr[j] является правильной проверкой инверсии только в том случае, если целевое состояние строго возрастает.

person hobbs    schedule 21.10.2020
comment
Итак, в этом случае, как лучше всего проверить количество инверсий, поскольку arr[i] › arr[j] не сработает? - person Jaime Garcia; 21.10.2020