class State(object):
    def __init__(self, gn=0, hn=0, state=None, hash_value=None, par=None):
        self.gn = gn
        self.hn = hn
        self.fn = self.gn + self.hn
        self.child = []
        self.par = par
        self.state = state
        self.hash_value = hash_value

    def __lt__(self, other):
        return self.fn < other.fn

    def __eq__(self, other):
        return self.hash_value == other.hash_value

    def __ne__(self, other):
        return not self.__eq__(other)

def manhattan_dis(cur_node, end_node):  # 定義一個名為manhattan_dis的函數(shù)，接受兩個參數(shù)cur_node（當(dāng)前結(jié)點(diǎn)）和end_node（目標(biāo)結(jié)點(diǎn)）
    # 獲取當(dāng)前結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)的狀態(tài)矩陣
    cur_state = cur_node.state
    end_state = end_node.state
    dist = 0
    N = len(cur_state)  # 獲取狀態(tài)矩陣的大小，假設(shè)為N
    # 遍歷狀態(tài)矩陣中的每個位置
    for i in range(N):
        for j in range(N):
            # 如果當(dāng)前結(jié)點(diǎn)的值與目標(biāo)結(jié)點(diǎn)的值相等，則跳過當(dāng)前位置，因?yàn)檫@個位置已經(jīng)在目標(biāo)狀態(tài)中
            if cur_state[i][j] == end_state[i][j]:
                continue
            num = cur_state[i][j]  # 獲取當(dāng)前結(jié)點(diǎn)在狀態(tài)矩陣中的值
            # 如果當(dāng)前結(jié)點(diǎn)的值為0（空白格），則將目標(biāo)位置設(shè)置為狀態(tài)矩陣的右下角
            if num == 0:
                x = N - 1
                y = N - 1
            # 如果當(dāng)前結(jié)點(diǎn)的值不為0，則根據(jù)當(dāng)前結(jié)點(diǎn)的值計(jì)算其目標(biāo)位置，假設(shè)目標(biāo)位置為（x,y）
            else:
                x = num / N
                y = num - N * x - 1
            # 計(jì)算當(dāng)前結(jié)點(diǎn)與目標(biāo)位置之間的曼哈頓距離，并累加到總距離中
            dist += (abs(x - i) + abs(y - j))
    # 返回計(jì)算得到的曼哈頓距離作為當(dāng)前結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的估計(jì)代價
    return dist

def test_fn(cur_node, end_node):
    return 0

def generate_child(cur_node, end_node, hash_set, open_table, dis_fn):
    # 如果當(dāng)前結(jié)點(diǎn)就是目標(biāo)結(jié)點(diǎn)，則直接將目標(biāo)結(jié)點(diǎn)假如OPEN表，并返回，表示已經(jīng)找到了解
    if cur_node == end_node:
        heapq.heappush(open_table, end_node)
        return
    # 獲取當(dāng)前結(jié)點(diǎn)狀態(tài)矩陣的大小
    num = len(cur_node.state)
    # 遍歷當(dāng)前結(jié)點(diǎn)狀態(tài)矩陣的每一個位置
    for i in range(0, num):
        for j in range(0, num):
            # 如果當(dāng)前位置不是空格，則跳過，因?yàn)榭崭袷强梢砸苿拥奈恢?
            if cur_node.state[i][j] != 0:
                continue
            # 遍歷當(dāng)前位置的四個鄰居位置，即上下左右四個方向
            for d in direction:
                x = i + d[0]
                y = j + d[1]
                if x < 0 or x >= num or y < 0 or y >=num:
                    continue
                # 記錄生成的結(jié)點(diǎn)數(shù)量
                global SUM_NODE_NUM
                SUM_NODE_NUM += 1
                # 交換空格和鄰居位置的數(shù)字，生成一個新的狀態(tài)矩陣
                state = copy.deepcopy(cur_node.state)
                state[i][j], state[x][y] = state[x][y], state[i][j]
                # 計(jì)算新狀態(tài)矩陣的哈希值，并檢查是否已經(jīng)在哈希集合中存在，如果存在則表示已經(jīng)生成過相同的狀態(tài)，跳過
                h = hash(str(state))
                if h in hash_set:
                    continue
                # 將新狀態(tài)的哈希值添加到哈希集合中，計(jì)算新狀態(tài)結(jié)點(diǎn)的gn（從起始結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的代價）和hn（當(dāng)前結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的估計(jì)代價）
                hash_set.add(h)
                gn = cur_node.gn + 1
                hn = dis_fn(cur_node, end_node)
                # 創(chuàng)建新的狀態(tài)結(jié)點(diǎn)對象，并將其加入到當(dāng)前結(jié)點(diǎn)的子結(jié)點(diǎn)列表中，并將其加入到OPEN表中。
                node = State(gn, hn, state, h, cur_node)
                cur_node.child.append(node)
                heapq.heappush(open_table, node)

def print_path(node):
    # 獲取從起始結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的路徑長度，即目標(biāo)結(jié)點(diǎn)的實(shí)際代價
    num = node.gn
    
    # 定義了一個內(nèi)部函數(shù)show_block，用于打印狀態(tài)矩陣
    def show_block(block):
        print("---------------")
        for b in block:
            print(b)
    # 創(chuàng)建一個棧，用于存儲路徑中經(jīng)過的結(jié)點(diǎn)
    stack = []
    # 從目標(biāo)結(jié)點(diǎn)開始，沿著父結(jié)點(diǎn)指針一直回溯到起始結(jié)點(diǎn)，并將沿途經(jīng)過的狀態(tài)矩陣入棧
    while node.par is not None:
        stack.append(node.state)
        node = node.par
    stack.append(node.state)
    # 從棧中依次取出狀態(tài)矩陣，并打印出來
    while len(stack) != 0:
        t = stack.pop()
        show_block(t)
    # 返回路徑長度
    return num

def A_start(start, end, distance_fn, generate_child_fn, time_limit=10):
    # 創(chuàng)建起始狀態(tài)結(jié)點(diǎn)和目標(biāo)狀態(tài)結(jié)點(diǎn)對象，并分別計(jì)算其哈希值
    root = State(0, 0, start, hash(str(BLOCK)), None)
    end_state = State(0, 0, end, hash(str(GOAL)), None)
    # 檢查起始狀態(tài)是否就是目標(biāo)狀態(tài)，如果是，則直接輸出提示信息
    if root == end_state:
        print("start == end !")
    # 將起始狀態(tài)結(jié)點(diǎn)加入到OPEN表中，并對OPEN表進(jìn)行堆化操作
    OPEN.append(root)
    heapq.heapify(OPEN)
    # 創(chuàng)建一個哈希集合，用于存儲已經(jīng)生成的狀態(tài)結(jié)點(diǎn)的哈希值，并將起始狀態(tài)結(jié)點(diǎn)的哈希值添加到集合中
    node_hash_set = set()
    node_hash_set.add(root.hash_value)
    # 記錄算法開始的時間
    start_time = datetime.datetime.now()
    # 進(jìn)入主循環(huán)，直到OPEN表為空（搜索完成）或達(dá)到時間限制
    while len(OPEN) != 0:
        top = heapq.heappop(OPEN)
        # 如果當(dāng)前結(jié)點(diǎn)就是目標(biāo)狀態(tài)結(jié)點(diǎn)，則直接輸出路徑
        if top == end_state:
            return print_path(top)
        # 產(chǎn)生孩子節(jié)點(diǎn)，孩子節(jié)點(diǎn)加入OPEN表
        generate_child_fn(cur_node=top, end_node=end_state, hash_set=node_hash_set,
                          open_table=OPEN, dis_fn=distance_fn)
        # 記錄當(dāng)前時間
        cur_time = datetime.datetime.now()
        # 超時處理，如果運(yùn)行時間超過了設(shè)定的時間限制，則輸出超時提示信息并返回
        if (cur_time - start_time).seconds > time_limit:
            print("Time running out, break !")
            print("Number of nodes:", SUM_NODE_NUM)
            return -1
    # 如果循環(huán)結(jié)束時OPEN表為空，則表示沒有找到路徑，輸出提示信息并返回-1
    print("No road !")  # 沒有路徑
    return -1

def read_block(block, line, N):
    # 使用正則表達(dá)式提取輸入行中的數(shù)字?jǐn)?shù)據(jù)，并存儲在列表res中
    pattern = re.compile(r'\d+')  # 正則表達(dá)式提取數(shù)據(jù)
    res = re.findall(pattern, line)
    # 初始化計(jì)數(shù)變量t和臨時列表tmp
    t = 0
    tmp = []
    # 遍歷提取的數(shù)字?jǐn)?shù)據(jù)，將其轉(zhuǎn)換為整數(shù)，并添加到臨時列表tmp中
    for i in res:
        t += 1
        tmp.append(int(i))
        # 當(dāng)計(jì)數(shù)變量t達(dá)到狀態(tài)矩陣的大小N時，表示當(dāng)前行數(shù)據(jù)處理完畢，將臨時表添加到狀態(tài)矩陣列表中，并清空臨時表
        if t == N:
            t = 0
            block.append(tmp)
            tmp = []

if __name__ == '__main__':
    # 嘗試打開infile.txt文件，如果文件打開失敗，則輸出錯誤信息并退出程序
    try:
        file = open('infile.txt', "r")
    except IOError:
        print("can not open file infile.txt !")
        exit(1)
    # 打開名為infile.txt文件，并將文件對象賦值給變量f
    f = open("infile.txt")
    # 讀取文件的第一行，獲取棋盤的大小NUMBER
    NUMBER = int(f.readline()[-2])
    # 根據(jù)棋盤大小生成目標(biāo)狀態(tài)，并將目標(biāo)狀態(tài)存儲在列表GOAL中
    n = 1
    for i in range(NUMBER):
        l = []
        for j in range(NUMBER):
            l.append(n)
            n += 1
        GOAL.append(l)
    GOAL[NUMBER - 1][NUMBER - 1] = 0
    # 逐行讀取文件中的數(shù)據(jù)
    for line in f:  # 讀取每一行數(shù)據(jù)
        # 在每次處理新的輸入數(shù)據(jù)之前，需要清空OPEN表和BLOCK表
        OPEN = []
        BLOCK = []
        # 調(diào)用讀取數(shù)據(jù)的函數(shù)，將當(dāng)前行的數(shù)據(jù)解析并存儲為狀態(tài)矩陣
        read_block(BLOCK, line, NUMBER)
        # 初始化生成的結(jié)點(diǎn)數(shù)量為0
        SUM_NODE_NUM = 0
        # 記錄算法開始的時間
        start_t = datetime.datetime.now()
        # 這里添加5秒超時處理，可以根據(jù)實(shí)際情況選擇啟發(fā)函數(shù)
        # 將求解路徑長度存儲在length中
        length = A_start(BLOCK, GOAL, manhattan_dis, generate_child, time_limit=10)
        # 記錄算法結(jié)束時間
        end_t = datetime.datetime.now()
        # 如果找到了路徑，則輸出路徑長度、算法執(zhí)行時間和生成的結(jié)點(diǎn)數(shù)量
        if length != -1:
            print("length =", length)
            print("time =", (end_t - start_t).total_seconds(), "s")
            print("Nodes =", SUM_NODE_NUM)

---------------
[7, 2, 6]
[8, 1, 4]
[3, 5, 0]
---------------
[7, 2, 6]
[8, 1, 0]
[3, 5, 4]
---------------
[7, 2, 0]
[8, 1, 6]
[3, 5, 4]
---------------
[7, 0, 2]
[8, 1, 6]
[3, 5, 4]
---------------
[7, 1, 2]
[8, 0, 6]
[3, 5, 4]
---------------
[7, 1, 2]
[8, 5, 6]
[3, 0, 4]
---------------
[7, 1, 2]
[8, 5, 6]
[0, 3, 4]
---------------
[7, 1, 2]
[0, 5, 6]
[8, 3, 4]
---------------
[0, 1, 2]
[7, 5, 6]
[8, 3, 4]
---------------
[1, 0, 2]
[7, 5, 6]
[8, 3, 4]
---------------
[1, 5, 2]
[7, 0, 6]
[8, 3, 4]
---------------
[1, 5, 2]
[7, 3, 6]
[8, 0, 4]
---------------
[1, 5, 2]
[7, 3, 6]
[8, 4, 0]
---------------
[1, 5, 2]
[7, 3, 0]
[8, 4, 6]
---------------
[1, 5, 2]
[7, 0, 3]
[8, 4, 6]
---------------
[1, 5, 2]
[7, 4, 3]
[8, 0, 6]
---------------
[1, 5, 2]
[7, 4, 3]
[0, 8, 6]
---------------
[1, 5, 2]
[0, 4, 3]
[7, 8, 6]
---------------
[1, 5, 2]
[4, 0, 3]
[7, 8, 6]
---------------
[1, 0, 2]
[4, 5, 3]
[7, 8, 6]
---------------
[1, 2, 0]
[4, 5, 3]
[7, 8, 6]
---------------
[1, 2, 3]
[4, 5, 0]
[7, 8, 6]
---------------
[1, 2, 3]
[4, 5, 6]
[7, 8, 0]
length = 22
time = 0.09839 s
Nodes = 8274

進(jìn)程已結(jié)束，退出代碼為 0

import heapq
import copy
import re
import datetime

BLOCK = []
GOAL = []
direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
OPEN = []
SUM_NODE_NUM = 0

class State(object):
    def __init__(self, gn=0, hn=0, state=None, hash_value=None, par=None):
        self.gn = gn
        self.hn = hn
        self.fn = self.gn + self.hn
        self.child = []
        self.par = par
        self.state = state
        self.hash_value = hash_value

    def __lt__(self, other):
        return self.fn < other.fn

    def __eq__(self, other):
        return self.hash_value == other.hash_value

    def __ne__(self, other):
        return not self.__eq__(other)


def manhattan_dis(cur_node, end_node):
    cur_state = cur_node.state
    end_state = end_node.state
    dist = 0
    N = len(cur_state)
    for i in range(N):
        for j in range(N):
            if cur_state[i][j] == end_state[i][j]:
                continue
            num = cur_state[i][j]
            if num == 0:
                x = N - 1
                y = N - 1
            else:
                x = num / N
                y = num - N * x - 1
            dist += (abs(x - i) + abs(y - j))
    return dist


def test_fn(cur_node, end_node):
    return 0


def generate_child(cur_node, end_node, hash_set, open_table, dis_fn):
    if cur_node == end_node:
        heapq.heappush(open_table, end_node)
        return
    num = len(cur_node.state)
    for i in range(0, num):
        for j in range(0, num):
            if cur_node.state[i][j] != 0:
                continue
            for d in direction:
                x = i + d[0]
                y = j + d[1]
                if x < 0 or x >= num or y < 0 or y >= num:
                    continue
                global SUM_NODE_NUM
                SUM_NODE_NUM += 1
                state = copy.deepcopy(cur_node.state)
                state[i][j], state[x][y] = state[x][y], state[i][j]
                h = hash(str(state))
                if h in hash_set:
                    continue
                hash_set.add(h)
                gn = cur_node.gn + 1
                hn = dis_fn(cur_node, end_node)
                node = State(gn, hn, state, h, cur_node)
                cur_node.child.append(node)
                heapq.heappush(open_table, node)


def print_path(node):
    num = node.gn

    def show_block(block):
        print("---------------")
        for b in block:
            print(b)

    stack = []
    while node.par is not None:
        stack.append(node.state)
        node = node.par
    stack.append(node.state)
    while len(stack) != 0:
        t = stack.pop()
        show_block(t)
    return num

def A_start(start, end, distance_fn, generate_child_fn, time_limit=10):
    root = State(0, 0, start, hash(str(BLOCK)), None)
    end_state = State(0, 0, end, hash(str(GOAL)), None)
    if root == end_state:
        print("start == end !")
    OPEN.append(root)
    heapq.heapify(OPEN)
    node_hash_set = set()
    node_hash_set.add(root.hash_value)
    start_time = datetime.datetime.now()
    while len(OPEN) != 0:
        top = heapq.heappop(OPEN)
        if top == end_state:
            return print_path(top)
        generate_child_fn(cur_node=top, end_node=end_state, hash_set=node_hash_set,
                          open_table=OPEN, dis_fn=distance_fn)
        cur_time = datetime.datetime.now()
        if (cur_time - start_time).seconds > time_limit:
            print("Time running out, break !")
            print("Number of nodes:", SUM_NODE_NUM)
            return -1
    print("No road !")
    return -1


def read_block(block, line, N):
    pattern = re.compile(r'\d+')
    res = re.findall(pattern, line)
    t = 0
    tmp = []
    for i in res:
        t += 1
        tmp.append(int(i))
        if t == N:
            t = 0
            block.append(tmp)
            tmp = []


if __name__ == '__main__':
    try:
        file = open('infile.txt', "r")
    except IOError:
        print("can not open file infile.txt !")
        exit(1)
    f = open("infile.txt")
    NUMBER = int(f.readline()[-2])
    n = 1
    for i in range(NUMBER):
        l = []
        for j in range(NUMBER):
            l.append(n)
            n += 1
        GOAL.append(l)
    GOAL[NUMBER - 1][NUMBER - 1] = 0
    for line in f:
        OPEN = []
        BLOCK = []
        read_block(BLOCK, line, NUMBER)
        SUM_NODE_NUM = 0
        start_t = datetime.datetime.now()
        length = A_start(BLOCK, GOAL, manhattan_dis, generate_child, time_limit=10)
        end_t = datetime.datetime.now()
        if length != -1:
            print("length =", length)
            print("time =", (end_t - start_t).total_seconds(), "s")
            print("Nodes =", SUM_NODE_NUM)