n谜题python中的曼哈顿距离启发式算法

Question

我的函数在python中计算8字谜的曼哈顿距离时遇到了一个问题。我的代码有一个问题，特别是在一个特定的状态：[4,3,7,5,8,6,1,0,2]，（在其他一些状态下，我尝试了它，它工作了…）我的代码运行，但没有停止运行，也没有打印结果，然后我不知道问题在我的函数中

我运行的代码是：

def search(n):
    s=[[4,3,7,5,8,6,1,0,2],""]
    print(s)
    f=frontier.create(s)
    while not frontier.is_empty(f):
        s=frontier.remove(f)
        if state.is_target(s):
            return [s, f[1], f[3]]
        ns=state.get_next(s)
        for i in ns:
            frontier.insert(f,i)
    return 0


print(search(3))

我的计算曼哈顿距离的函数：

def hdistance(s):
    # the heuristic value of s
    i = 0 #represent the row number
    j = 0 #represent the column number
    sum = 0 #the manhattan distance
    n = math.sqrt(len(s[0])) #calculate the size of the n puzzle
    for k in s[0]: #run through the list
        if k != 0:
            row = int(k / n)
            column = int(k % n)
            sum = sum + abs(i - row) + abs(j - column)
            j += 1 #increment the column
            if j == n: #if I get to the end of the line
                i += 1 #increment the row
                j = 0
    return sum #return the manhattan distance

边界文件：

def create(s):
    return [[s], 0, 0 ,0]


def is_empty(f):
    return f[0]==[]

def val(s):
    return state.hdistance(s)+state.path_len(s)

# Uniform Cost: return state.path_len(s)
# Greedy Best First: return state.hdistance(s)

def insert(h, s):
    #inserts state s to the frontier
    f=h[0]
    h[1]+=1
    h[2]+=1
    if h[2]>h[3]:
        h[3]=h[2]
    f.append(s)
    i=len(f)-1
    while i>0 and val(f[i])<val(f[(i-1)//2]):
        t=f[i]
        f[i]=f[(i-1)//2]
        f[(i-1)//2]=t
        i=(i-1)//2

def remove(h):
    if is_empty(h):
        return 0
    h[2]-=1
    f=h[0]
    s=f[0]
    f[0]=f[len(f)-1]
    del f[-1]
    heapify(f,0)
    return s

def heapify(f,i):
    minSon=i
    if 2*i+1<len(f) and val(f[2*i+1])<val(f[minSon]):
        minSon=2*i+1
    if 2*i+2<len(f) and val(f[2*i+2])<val(f[minSon]):
        minSon=2*i+2
    if minSon!=i:
        t=f[minSon]
        f[minSon]=f[i]
        f[i]=t
        heapify(f, minSon)

州档案：

def get_next(x):            # returns a list of the children states of x
    ns=[]                   # the next state list
    for i in "<>v^":
        s=x[0][:]           # [:] - copies the board in x[0]
        if_legal(s,i)       # try to move in direction i
        # checks if the move was legal and...
        if s.index(0)!=x[0].index(0) and \
           (x[1]=="" or x[1][-1]!="><^v"["<>v^".index(i)]): # check if it's the first move or it's a reverse move
            ns.append([s,x[1]+i])   # appends the new state to ns
    return ns


def path_len(x):
    return len(x[1])

def is_target(x):
    n=len(x[0])                     # the size of the board
    return x[0]==list(range(n))     # list(range(n)) is the target state

#############################
def if_legal(x,m):                  # gets a board and a move and makes the move if it's legal
    n=int(math.sqrt(len(x)))        # the size of the board is nXn
    z=x.index(0)                    # z is the place of the empty tile (0)
    if z%n>0 and m=="<":            # checks if the empty tile is not in the first col and the move is to the left
        x[z]=x[z-1]                 # swap x[z] and x[z-1]...
        x[z-1]=0                    # ...and move the empty tile to the left
    elif z%n<n-1 and m==">":        # check if the empty tile is not in the n's col and the move is to the right
        x[z]=x[z+1]
        x[z+1]=0
    elif z>=n and m=="^":           # check if the empty tile is not in the first row and the move is up
        x[z]=x[z-n]
        x[z-n]=0
    elif z<n*n-n and m=="v":        # check if the empty tile is not in the n's row and the move is down
        x[z]=x[z+n]
        x[z+n]=0

其余的代码（所有其他函数）都在我的作业中给出，那么问题肯定出在我的hdistance函数中。 如果你能在我的函数中找到问题所在，也许有一个无限循环。。。 谢谢你