3

8 パズルを解くための独自のプログラムを Python で開発しました。最初は、「ブラインド」または情報に基づいていない検索 (基本的に総当たり) を使用して、すべての可能な後継者を生成および探索し、幅優先検索を使用しました。「目標」状態を見つけると、基本的に初期状態に戻り、それを解決するための最も最適化された手順を提供します (私が信じていること)。もちろん、検索に時間がかかり、目標を見つけるまでに 100,000 を超える状態が生成される初期状態もありました。

次に、ヒューリスティック - マンハッタン距離を追加しました。解決策は指数関数的に急速に現れ始め、調査された状態ははるかに少なくなりました。しかし、私の混乱は、生成された最適化されたシーケンスが、盲目的または情報に基づいていない検索を使用して到達したシーケンスよりも長い場合があることです。

私がやっていることは基本的にこれです：

  1. 状態ごとに、可能なすべての動き (上、下、左、右) を探し、後続の状態を生成します。
  2. 状態が繰り返しかどうかを確認します。はいの場合は、無視してください。
  3. 州のマンハッタンを計算します。
  4. マンハッタンが最も低い後継者を選び出し、リストの最後に追加します。
  5. 目標状態かどうかを確認します。もしそうなら、ループを壊してください。

これが貪欲優先または A* と見なされるかどうかはわかりません。

私の質問は、これはマンハッタン距離ヒューリスティックに固有の欠陥であり、最適なソリューションが得られない場合があるのか​​、それとも何か間違っているのかということです。

以下はコードです。非常にきれいなコードではないことをお詫びしますが、ほとんどがシーケンシャルであるため、理解しやすいはずです。また、コードが長くなってしまったことをお詫び申し上げます。コードを最適化する必要があることは承知しています。また、コードをクリーンアップするための提案/ガイダンスをいただければ幸いです。それが何であるかは次のとおりです。

import numpy as np
from copy import deepcopy
import sys

# calculate Manhattan distance for each digit as per goal
def mhd(s, g):
    m = abs(s // 3 - g // 3) + abs(s % 3 - g % 3)
    return sum(m[1:])

# assign each digit the coordinate to calculate Manhattan distance
def coor(s):
    c = np.array(range(9))
    for x, y in enumerate(s):
        c[y] = x
    return c

#################################################
def main():
    goal    =  np.array( [1, 2, 3, 4, 5, 6, 7, 8, 0] )
    rel     = np.array([-1])
    mov     = np.array([' '])
    string = '102468735'
    inf = 'B'
    pos = 0
    yes = 0
    goalc = coor(goal)
    puzzle = np.array([int(k) for k in string]).reshape(1, 9)
    rnk = np.array([mhd(coor(puzzle[0]), goalc)])
    while True:
        loc = np.where(puzzle[pos] == 0)        # locate '0' (blank) on the board
        loc = int(loc[0])
        child = np.array([], int).reshape(-1, 9)
        cmove = []
        crank = []
        # generate successors on possible moves - new states no repeats
        if loc > 2:         # if 'up' move is possible
            succ = deepcopy(puzzle[pos])
            succ[loc], succ[loc - 3] = succ[loc - 3], succ[loc]
            if ~(np.all(puzzle == succ, 1)).any():  # repeat state?
                child = np.append(child, [succ], 0)
                cmove.append('up')
                crank.append(mhd(coor(succ), goalc)) # manhattan distance
        if loc < 6:         # if 'down' move is possible
            succ = deepcopy(puzzle[pos])
            succ[loc], succ[loc + 3] = succ[loc + 3], succ[loc]
            if ~(np.all(puzzle == succ, 1)).any():  # repeat state?
                child = np.append(child, [succ], 0)
                cmove.append('down')
                crank.append(mhd(coor(succ), goalc))
        if loc % 3 != 0:    # if 'left' move is possible
            succ = deepcopy(puzzle[pos])
            succ[loc], succ[loc - 1] = succ[loc - 1], succ[loc]
            if ~(np.all(puzzle == succ, 1)).any():  # repeat state?
                child = np.append(child, [succ], 0)
                cmove.append('left')
                crank.append(mhd(coor(succ), goalc))
        if loc % 3 != 2:    # if 'right' move is possible
            succ = deepcopy(puzzle[pos])
            succ[loc], succ[loc + 1] = succ[loc + 1], succ[loc]
            if ~(np.all(puzzle == succ, 1)).any():  # repeat state?
                child = np.append(child, [succ], 0)
                cmove.append('right')
                crank.append(mhd(coor(succ), goalc))
        for s in range(len(child)):
            if (inf in 'Ii' and crank[s] == min(crank)) \
            or (inf in 'Bb'):
                puzzle = np.append(puzzle, [child[s]], 0)
                rel = np.append(rel, pos)
                mov = np.append(mov, cmove[s])
                rnk = np.append(rnk, crank[s])
                if np.array_equal(child[s], goal):
                    print()
                    print('Goal achieved!. Successors generated:', len(puzzle) - 1)
                    yes = 1
                    break
        if yes == 1:
            break
        pos += 1
    # generate optimized steps by back-tracking the steps to the initial state
    optimal = np.array([], int).reshape(-1, 9)
    last = len(puzzle) - 1
    optmov = []
    rank = []
    while last != -1:
        optimal = np.insert(optimal, 0, puzzle[last], 0)
        optmov.insert(0, mov[last])
        rank.insert(0, rnk[last])
        last = int(rel[last])

    # show optimized steps
    optimal = optimal.reshape(-1, 3, 3)
    print('Total optimized steps:', len(optimal) - 1)
    print()
    for s in range(len(optimal)):
        print('Move:', optmov[s])
        print(optimal[s])
        print('Manhattan Distance:', rank[s])
        print()
    print()

################################################################
# Main Program

if __name__ == '__main__':
    main()

初期状態の一部と、確認したい場合に計算された最適化されたステップを次に示します (上記のコードでは、ブラインド検索とインフォームド検索のどちらかを選択するオプションが提供されます)

初期状態
- 283164507 ブラインド: 19 マンハッタン: 21
- 243780615 ブラインド: 15 マンハッタン: 21
- 102468735 ブラインド: 11 マンハッタン: 17
- 481520763 ブラインド: 13 マンハッタン: 23
- 723156480 ブラインド: 16 マンハッタン: 20

結果がすぐに得られる例 (数秒または数分以内) を意図的に選択しました。

皆様のご支援とご指導を賜りますようお願い申し上げます。

編集: いくつかの簡単な変更を行い、30 行以上を削減することができました。残念ながら、現時点では多くのことを行うことはできません。
注: 初期状態と、ブラインド vs インフォームド チョイスをハードコーディングしました。初期状態は変数「string」、Informed/Blindは変数「inf」[I/B]の値を変更してください。ありがとう！

4

0 に答える 0