python的A*算法怎么使用

這篇文章主要介紹“python的A*算法怎么使用”，在日常操作中，相信很多人在python的A*算法怎么使用問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”python的A*算法怎么使用”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

說明

1、A*算法是靜態(tài)路網(wǎng)中解決最短路徑最有效的直接搜索方法。

2、A*算法是啟發(fā)式算法，采用最佳優(yōu)先搜索策略(Best-first)，基于評估函數(shù)對每個搜索位置的評估結(jié)果，猜測最佳優(yōu)先搜索位置。

A*算法大大降低了低質(zhì)量的搜索路徑，因此搜索效率高，比傳統(tǒng)的路徑規(guī)劃算法更實(shí)時、更靈活。但A*算法找到的是相對最優(yōu)的路徑，而不是絕對最短的路徑，適合大規(guī)模、實(shí)時性高的問題。

實(shí)例

import heapq
import copy
import re
import datetime
 
BLOCK = []  # 給定狀態(tài)
GOAL = []  # 目標(biāo)狀態(tài)
 
# 4個方向
direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
 
# OPEN表
OPEN = []
 
# 節(jié)點(diǎn)的總數(shù)
SUM_NODE_NUM = 0
 
 
# 狀態(tài)節(jié)點(diǎn)
class State(object):
    def __init__(self, gn=0, hn=0, state=None, hash_value=None, par=None):
        '''
        初始化
        :param gn: gn是初始化到現(xiàn)在的距離
        :param hn: 啟發(fā)距離
        :param state: 節(jié)點(diǎn)存儲的狀態(tài)
        :param hash_value: 哈希值，用于判重
        :param par: 父節(jié)點(diǎn)指針
        '''
        self.gn = gn
        self.hn = hn
        self.fn = self.gn + self.hn
        self.child = []  # 孩子節(jié)點(diǎn)
        self.par = par  # 父節(jié)點(diǎn)
        self.state = state  # 局面狀態(tài)
        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):
    '''
    計(jì)算曼哈頓距離
    :param cur_state: 當(dāng)前狀態(tài)
    :return: 到目的狀態(tài)的曼哈頓距離
    '''
    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  # 理論橫坐標(biāo)
                y = num - N * x - 1  # 理論的縱坐標(biāo)
            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):
    '''
    生成子節(jié)點(diǎn)函數(shù)
    :param cur_node:  當(dāng)前節(jié)點(diǎn)
    :param end_node:  最終狀態(tài)節(jié)點(diǎn)
    :param hash_set:  哈希表，用于判重
    :param open_table: OPEN表
    :param dis_fn: 距離函數(shù)
    :return: None
    '''
    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
                # 記錄擴(kuò)展節(jié)點(diǎn)的個數(shù)
                global SUM_NODE_NUM
                SUM_NODE_NUM += 1
 
                state = copy.deepcopy(cur_node.state)  # 復(fù)制父節(jié)點(diǎn)的狀態(tài)
                state[i][j], state[x][y] = state[x][y], state[i][j]  # 交換位置
                h = hash(str(state))  # 哈希時要先轉(zhuǎn)換成字符串
                if h in hash_set:  # 重復(fù)了
                    continue
                hash_set.add(h)  # 加入哈希表
                gn = cur_node.gn + 1  # 已經(jīng)走的距離函數(shù)
                hn = dis_fn(cur_node, end_node)  # 啟發(fā)的距離函數(shù)
                node = State(gn, hn, state, h, cur_node)  # 新建節(jié)點(diǎn)
                cur_node.child.append(node)  # 加入到孩子隊(duì)列
                heapq.heappush(open_table, node)  # 加入到堆中
 
 
def print_path(node):
    '''
    輸出路徑
    :param node: 最終的節(jié)點(diǎn)
    :return: None
    '''
    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):
    '''
    A*算法
    :param start: 起始狀態(tài)
    :param end: 終止?fàn)顟B(tài)
    :param distance_fn: 距離函數(shù)，可以使用自定義的
    :param generate_child_fn: 產(chǎn)生孩子節(jié)點(diǎn)的函數(shù)
    :param time_limit: 時間限制，默認(rèn)10秒
    :return: None
    '''
    root = State(0, 0, start, hash(str(BLOCK)), None)  # 根節(jié)點(diǎn)
    end_state = State(0, 0, end, hash(str(GOAL)), None)  # 最后的節(jié)點(diǎn)
    if root == end_state:
        print("start == end !")
 
    OPEN.append(root)
    heapq.heapify(OPEN)
 
    node_hash_set = set()  # 存儲節(jié)點(diǎn)的哈希值
    node_hash_set.add(root.hash_value)
    start_time = datetime.datetime.now()
    while len(OPEN) != 0:
        top = heapq.heappop(OPEN)
        if top == end_state:  # 結(jié)束后直接輸出路徑
            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)
        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):
    '''
    讀取一行數(shù)據(jù)作為原始狀態(tài)
    :param block: 原始狀態(tài)
    :param line: 一行數(shù)據(jù)
    :param N: 數(shù)據(jù)的總數(shù)
    :return: None
    '''
    pattern = re.compile(r'\d+')  # 正則表達(dá)式提取數(shù)據(jù)
    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:  # 讀取每一行數(shù)據(jù)
        OPEN = []  # 這里別忘了清空
        BLOCK = []
        read_block(BLOCK, line, NUMBER)
        SUM_NODE_NUM = 0
        start_t = datetime.datetime.now()
        # 這里添加5秒超時處理，可以根據(jù)實(shí)際情況選擇啟發(fā)函數(shù)
        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)

到此，關(guān)于“python的A*算法怎么使用”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！