Пъзел 8: Разрешимост и най-кратко решение

Ще се позова само на проблема с разрешимостта. Необходим е известен опит в пермутациите.

Пермутацията е пренареждане на подреден набор. Например 2134 е пренареждане на списък 1234, където 1 и 2 си разменят местата. Пермутацията има свойство за паритет; то се отнася до паритета на броя на инверсиите. Например, в следната пермутация можете да видите, че съществуват точно 3 инверсии (23,24,34):

1234
1432

Това означава, че пермутацията има нечетен паритет. Следната пермутация има четен паритет (12, 34):

1234
2143

Естествено, пермутацията на идентичност (която поддържа реда на елементите) има четен паритет.

Всяко състояние в пъзела 15 (или пъзела 8) може да се разглежда като пермутация на крайното състояние, ако го разглеждаме като конкатенация на редовете, започвайки от първия ред. Обърнете внимание, че всеки законен ход променя паритета на пермутацията (защото разменяме два елемента и броят на инверсиите, включващи елементи между тях, трябва да е четен). Следователно, ако знаете, че празният квадрат трябва да измине четен брой стъпки, за да достигне крайното си състояние, тогава пермутацията също трябва да е четна. В противен случай ще завършите със странна пермутация на крайното състояние, което е задължително различно от него. Същото с нечетен брой стъпки за празния квадрат.

Според предоставената от вас връзка към Wikipedia критериите по-горе са достатъчни и необходими, за да може даден пъзел да бъде разрешим.

Алгоритъмът A* е гарантиран за намиране на (едно, ако има повече от едно еднакви къси) най-краткото решение, ако вашата евристична винаги подценява реалните разходи (Във вашия случай реалният брой необходими ходове към решението).

Но в движение не мога да измисля добра евристика за вашия проблем. Това изисква известно мислене, за да се намери такава евристика.

Истинското изкуство при използване на A* е да се намери евристика, която винаги подценява реалните разходи, но възможно най-малко, за да ускори търсенето.

Първи идеи за такава евристика:

1. Доста безпроблемна, но валидна евристика, която изникна в съзнанието ми, е разстоянието Манхатън на празния файл до крайната му дестинация.
2. Сумата от разстоянието Манхатън на всяко поле до крайната му дестинация, разделена на максималния брой полета, които могат да променят позицията си в рамките на едно движение. (Мисля, че това е доста добра евристика)

За всеки, който идва, ще се опитам да обясня как OP е получил двойките стойности, както и как той определя маркираните, т.е. инверсии, тъй като ми отне няколко часа, за да го разбера. Първо двойките. Първо вземете целевото състояние и си го представете като 1D масив (A например) [1,2,3,8,0,4,7,5]. Всяка стойност в този масив има своя собствена колона в таблицата (стигайки докрай, което е първата стойност на двойката.) След това преместете над 1 стойност вдясно в масива (i + 1) и отидете докрай отново надолу, втора стойност на чифта. например (състояние A): първата колона, втората стойност ще започне [2,3,8,0,4,7,5] надолу. втората колона ще започне [3,8,0,4,7,5] и т.н.

добре сега за инверсиите. за всяка от 2-те двойки стойности намерете местоположението им INDEX в началното състояние. ако ляв INDEX > десен INDEX, тогава това е инверсия (маркирана). първите четири двойки състояние А са: (1,2),(1,3),(1,8),(1,0)
1 е на индекс 3
2 е на индекс 0
3 > 0, така че инверсия.

1 е 3
3 е 2
3 > 2, така че инверсия

1 е 3
8 е 1
3 > 2, така че инверсия

1 е 3
0 е 7
3 ‹ 7, така че Без инверсия

Направете това за всяка двойка и пребройте общите инверсии. Ако и двете четни или и двете нечетни (Манхатън разстояние на празно петно ​​и общи инверсии), тогава е разрешимо. Надявам се това да помогне!