1

In [ ]:

from queue import PriorityQueue
import numpy as np

from queue import PriorityQueue import numpy as np

In [ ]:

Final = np.array([[1, 3, 5], [7, 0, 2], [6, 8, 4]], dtype=int) # 最终

Final = np.array([[1, 3, 5], [7, 0, 2], [6, 8, 4]], dtype=int) # 最终

In [ ]:

class State:
    def __init__(self, matrix, g):
        self.matrix = matrix  # 当前状态的冰雪魔方
        self.g = g  # 真实   
        self.h = self.H() # 估计
        self.f = self.g + self.h
    # 重定义_lt_比较方法,使得类实例能够相互比较,根据f值大小从小到大排序
    def __lt__(self, other):
        return self.f < other.f

    
    def H(self):
        # 曼哈顿距离
        ans = 0
        for i in self.matrix.flatten():
            x = (np.where(self.matrix == i)[0][0] - np.where(Final == i)[0][0])
            y = (np.where(self.matrix == i)[1][0] - np.where(Final == i)[1][0])
            ans += (np.abs(x)+np.abs(y))
        return ans
    '''
    def H(self):
        # 思路2
        # 表示Matrix中非零元素的位置
        non_zero_elements_in_Matrix = self.matrix != 0
        diff_elements = non_zero_elements_in_Matrix & (Final != self.matrix)
        ans = np.sum(diff_elements)
        return ans
    '''

class State: def __init__(self, matrix, g): self.matrix = matrix # 当前状态的冰雪魔方 self.g = g # 真实 self.h = self.H() # 估计 self.f = self.g + self.h # 重定义_lt_比较方法,使得类实例能够相互比较,根据f值大小从小到大排序 def __lt__(self, other): return self.f < other.f def H(self): # 曼哈顿距离 ans = 0 for i in self.matrix.flatten(): x = (np.where(self.matrix == i)[0][0] - np.where(Final == i)[0][0]) y = (np.where(self.matrix == i)[1][0] - np.where(Final == i)[1][0]) ans += (np.abs(x)+np.abs(y)) return ans ''' def H(self): # 思路2 # 表示Matrix中非零元素的位置 non_zero_elements_in_Matrix = self.matrix != 0 diff_elements = non_zero_elements_in_Matrix & (Final != self.matrix) ans = np.sum(diff_elements) return ans '''

In [ ]:

def FindNextMatrix(NowMatrix):
    NextMatrix = []
    # 把0上下左右移
    # 空格在哪里
    x = np.where(NowMatrix == 0)[0][0]
    y = np.where(NowMatrix == 0)[1][0]
    # 上
    if x-1 >= 0:
        tmp = NowMatrix.copy()
        tmp[x][y] = tmp[x-1][y]
        tmp[x-1][y] = 0
        NextMatrix.append(tmp)
    # 下
    if x+1 <= 2:
        tmp = NowMatrix.copy()
        tmp[x][y] = tmp[x + 1][y]
        tmp[x + 1][y] = 0
        NextMatrix.append(tmp)
    # 左
    if y-1 >= 0:
        tmp = NowMatrix.copy()
        tmp[x][y] = tmp[x][y-1]
        tmp[x][y-1] = 0
        NextMatrix.append(tmp)
    # 右
    if y+1 <= 2:
        tmp = NowMatrix.copy()
        tmp[x][y] = tmp[x][y+1]
        tmp[x][y+1] = 0
        NextMatrix.append(tmp)
    return NextMatrix

def FindNextMatrix(NowMatrix): NextMatrix = [] # 把0上下左右移 # 空格在哪里 x = np.where(NowMatrix == 0)[0][0] y = np.where(NowMatrix == 0)[1][0] # 上 if x-1 >= 0: tmp = NowMatrix.copy() tmp[x][y] = tmp[x-1][y] tmp[x-1][y] = 0 NextMatrix.append(tmp) # 下 if x+1 <= 2: tmp = NowMatrix.copy() tmp[x][y] = tmp[x + 1][y] tmp[x + 1][y] = 0 NextMatrix.append(tmp) # 左 if y-1 >= 0: tmp = NowMatrix.copy() tmp[x][y] = tmp[x][y-1] tmp[x][y-1] = 0 NextMatrix.append(tmp) # 右 if y+1 <= 2: tmp = NowMatrix.copy() tmp[x][y] = tmp[x][y+1] tmp[x][y+1] = 0 NextMatrix.append(tmp) return NextMatrix

In [ ]:

def Astar(start):
    pq = PriorityQueue()
    visited = []  # 已访问过
    g = 0 # 真实

    state = State(start, 0)
    pq.put(state)
    stateNow = pq.get()

    while stateNow.H() != 0: 
        # 中止条件:当估计距离为0
        visited.append(str(stateNow.matrix.flatten()))
        NextMatrix = FindNextMatrix(stateNow.matrix)
        for nextMatrix in NextMatrix:
            if str(nextMatrix.flatten()) in visited:
                continue
            g = stateNow.g + 1
            stateNext = State(nextMatrix, g)
            pq.put(stateNext)
        stateNow = pq.get()

    print(g)

def Astar(start): pq = PriorityQueue() visited = [] # 已访问过 g = 0 # 真实 state = State(start, 0) pq.put(state) stateNow = pq.get() while stateNow.H() != 0: # 中止条件:当估计距离为0 visited.append(str(stateNow.matrix.flatten())) NextMatrix = FindNextMatrix(stateNow.matrix) for nextMatrix in NextMatrix: if str(nextMatrix.flatten()) in visited: continue g = stateNow.g + 1 stateNext = State(nextMatrix, g) pq.put(stateNext) stateNow = pq.get() print(g)

In [ ]:

if __name__ == "__main__":
    InputArray= ['135720684','105732684','015732684','135782604','715032684']
    for i in InputArray:
        print("Input:",i)
        Start = np.array(list(i), dtype=int).reshape(3,3)
        Astar(Start)
    #Start = np.array(list(input()), dtype=int).reshape(3,3)
    #Astar(Start)

if __name__ == "__main__": InputArray= ['135720684','105732684','015732684','135782604','715032684'] for i in InputArray: print("Input:",i) Start = np.array(list(i), dtype=int).reshape(3,3) Astar(Start) #Start = np.array(list(input()), dtype=int).reshape(3,3) #Astar(Start)