8

I am trying to code a simple A* solver in Python for a simple 8-Puzzle game. I have represented the goal of my game in this way:

goal = [[1, 2, 3],
        [8, 0, 4], 
        [7, 6, 5]]

私の問題は、目標のために単純な Manhattan Distance ヒューリスティックを作成する方法がわからないことです。一般的な状態と目標状態の間の距離の合計として定義する必要があることはわかっています。次のようにコーディングする必要があると思います。

def manhattan_distance(state):
    distance = 0
    for x in xrange(3):
        for y in xrange(3):
            value = state[x][y]
            x_value = x
            y_value = y
            x_goal = ...?
            y_goal = ...?
            distance += abs(x_value - x_goal) + abs(y_value - y_goal)
    return distance

私の問題は、ゴール状態のピースの座標を明示的に表現していないため、ボードの「値」ピースに対して「x_goal」と「y_goal」を定義する方法がわからないことです。割り算とモジュール演算でやってみましたが難しいです。

「x_goal」変数と「y_goal」変数を定義するヒントを教えてください。

ありがとうございました

4

4 に答える 4

1

あなたが見つけることができるほとんどのpythonic実装。

仮定して、

0 1 2

3 4 5

6 7 8

は目標状態です...そして、

1 5 3

4 2 6

7 8 9

最終状態です。

initial_state = [1,5,3,4,2,6,7,8,0]
goal_state = [0,1,2,3,4,5,6,7,8]
def calculateManhattan(initial_state):
    initial_config = initial_state
    manDict = 0
    for i,item in enumerate(initial_config):
        prev_row,prev_col = int(i/ 3) , i % 3
        goal_row,goal_col = int(item /3),item % 3
        manDict += abs(prev_row-goal_row) + abs(prev_col - goal_col)
    return manDict

これを他にどのように説明すればよいかわかりません。それだけで機能します。楽しみ ！:D

于 2018-10-25T19:13:50.007 に答える
0

私はあなたが持っていたのとまったく同じ質問をしました。私はあなたが持っている表現を取り、それをあなたが決めた表現（値/座標ペアの辞書）に変換する別の関数を書くことで解決しました。 

def make_dict(state):
    coordinate_dict = {}
    for x, row in enumerate(state):
        for y, value in enumerate(row):
            coordinate_dict[value] = (x, y)
    return coordinate_dict

そうすれば、両方の長所を活かすことができます。グリッドをグリッドとして扱いたいときはいつでも、元のリストのリスト形式を使用できますが、マンハッタン距離関数の値がどこにあるかをすばやく検索するだけでよい場合は、新しい辞書を使用できます。作成しました。

于 2013-11-24T23:24:04.490 に答える