在 8 拼图游戏中用 Python 计算曼哈顿距离 [英] Calculating Manhattan Distance in Python in an 8-Puzzle game

问题描述

我正在尝试用 Python 编写一个简单的 A* 求解器，用于一个简单的 8-Puzzle 游戏.我以这种方式代表了我的比赛目标:

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]]

我的问题是我不知道如何为我的目标编写一个简单的曼哈顿距离启发式方法.我知道它应该被定义为通用状态和我的目标状态之间距离的总和.我想我应该编写如下代码:

My problem is that I don't know how to write a simple Manhattan Distance heuristic for my goal. I know it should be defined as the sum of the distances between a generic state and my goal state. I think I should code something like:

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"木板.我正在尝试使用除法和模块操作来完成它，但很困难.

My problem is that I don't have an explicit representation of the coordinates of the pieces in the goal state, so I don't know how to define 'x_goal' and 'y_goal' for the 'value' piece of the board. I am trying to do it using division and module operations, but it's difficult.

你能给我一些提示来定义我的x_goal"和y_goal"变量吗?

Can you give me some hints to define my 'x_goal' and 'y_goal' variables?

谢谢

推荐答案

您可以找到的大多数 Python 实现.

Most pythonic implementation you can find.

假设，

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

I don't know how else to explain this. It just works. Enjoy ! :D

这篇关于在 8 拼图游戏中用 Python 计算曼哈顿距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！