實驗?zāi)康?/h3>

熟悉和掌握啟發(fā)式搜索的定義、估價函數(shù)和算法過程

實驗平臺

Python 3.7 +

實驗要求

熟練掌握A*算法的基本原理。分析不同啟發(fā)式函數(shù)對問題求解的提升效果。

1. 實現(xiàn)A*算法的求解，要求設(shè)計兩種不同的估價函數(shù)：設(shè)置相同的初始狀態(tài)和目標(biāo)狀態(tài)，針對不同估價函數(shù)，求得問題的屆，比較它們對搜索算法性能的影響，包括擴展節(jié)點數(shù)、生成節(jié)點數(shù)、運行時間等。
2. 畫出流程圖。
3. 源程序代碼

實驗結(jié)果（可以包含數(shù)據(jù)集分析、實驗過程、結(jié)果截圖、結(jié)果分析等）

• 八數(shù)碼問題

1. 不同的估價函數(shù)對搜索算法性能的影響

（1）、曼哈頓距離：曼哈頓距離是八數(shù)碼問題中常用的估價函數(shù)之一。在這個算法中，每個狀態(tài)都會計算曼哈頓距離，并將距離加入優(yōu)先隊列中。曼哈頓距離具有良好的準(zhǔn)確性和高效性，因此在這個算法中表現(xiàn)良好。

（2）、歐幾里得距離：歐幾里得距離是另一個常用的估價函數(shù)。在這個算法中，每個狀態(tài)都會計算歐幾里得距離，并將距離加入優(yōu)先隊列中。與曼哈頓距離相比，歐幾里得距離可以更好地反映狀態(tài)之間的真實距離，但是由于它需要進行平方根計算，因此計算成本更高。

（3）、切比雪夫距離：切比雪夫距離是一種更為簡單的估價函數(shù)，它只需要取兩個狀態(tài)之間橫向和縱向距離的最大值。在這個算法中，每個狀態(tài)都會計算切比雪夫距離，并將距離加入優(yōu)先隊列中。與曼哈頓距離相比，切比雪夫距離更為簡單，計算成本更低，但它可能不如曼哈頓距離那么準(zhǔn)確。

1. 流程圖

源程序代碼

from queue import PriorityQueue

# 定義狀態(tài)類
class State:
??? def __init__(self, board, moves, previous):
??????? self.board = board
??????? self.moves = moves
??????? self.previous = previous

??? # 定義狀態(tài)比較函數(shù)，用于在優(yōu)先隊列中比較狀態(tài)
??? def __lt__(self, other):
??????? return self.moves + self.manhattan_distance() < other.moves + other.manhattan_distance()

??? # 計算曼哈頓距離
??? def manhattan_distance(self):
??????? distance = 0
??????? for i in range(3):
??????????? for j in range(3):
??????????????? if self.board[i][j] == 0:
??????????????????? continue
??????????????? x, y = divmod(self.board[i][j] - 1, 3)
??????????????? distance += abs(x - i) + abs(y - j)
??????? return distance

??? # 判斷狀態(tài)是否為目標(biāo)狀態(tài)
??? def is_goal(self):
??????? return self.board == [[1, 2, 3], [4, 5, 6], [7, 8, 0]]

??? # 獲取當(dāng)前狀態(tài)的下一步狀態(tài)
??? def get_next_states(self):
??????? next_states = []
??????? i, j = next((i, j) for i in range(3) for j in range(3) if self.board[i][j] == 0)
??????? for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
??????????? if 0 <= x < 3 and 0 <= y < 3:
??????????????? board = [row[:] for row in self.board]
??????????????? board[i][j], board[x][y] = board[x][y], board[i][j]
??????????????? next_states.append(State(board, self.moves+1, self))
??????? return next_states

??? # 獲取從初始狀態(tài)到達當(dāng)前狀態(tài)的路徑
??? def get_path(self):
??????? path = []
??????? state = self
??????? while state is not None:
??????????? path.append(state)
??????????? state = state.previous
??????? return reversed(path)

# A*搜索算法
def solve(start_board):
??? start_state = State(start_board, 0, None)
??? queue = PriorityQueue()
??? queue.put(start_state)
??? visited = set()
??? while not queue.empty():
??????? state = queue.get()
??????? if state.is_goal():
??????????? return state.get_path()
??????? if tuple(map(tuple, state.board)) in visited:
??????????? continue
??????? visited.add(tuple(map(tuple, state.board)))
??????? for next_state in state.get_next_states():
??????????? queue.put(next_state)

??? return None

# 測試代碼
if __name__ == '__main__':
?? ?start_board = [[1, 2, 3], [4, 5, 6], [0, 7, 8]]
??? path = solve(start_board)
??? if path is None:
??????? print("無解")
??? else:
??????? for i, state in enumerate(path):
??????????? print(f"步驟 {i}:")
??????????? for row in state.board:
??????????????? print(row)

• 5*5迷宮尋路問題

1. 不同的估價函數(shù)對搜索算法性能的影響

（1）、切比雪夫距離估價函數(shù)：對于55迷宮的起點和目標(biāo)點，在網(wǎng)格上可視為同一正方形角落的兩個點。因此，用切比雪夫距離可以輕松快速地計算出任意兩點之間的代價。使用切比雪夫距離作為估價函數(shù)的A算法可以有效地搜索整個網(wǎng)格，直接到達目標(biāo)點，并盡可能少地探索其他節(jié)點。因此，此估價函數(shù)能夠有效地提高搜索算法性能。

（2）、曼哈頓距離估價函數(shù)：曼哈頓距離是指兩點之間橫向和縱向的距離之和。在5*5迷宮中，使用曼哈頓距離可以快速估算出兩點之間的代價，但是這種估價方式會導(dǎo)致搜索算法探索更多的區(qū)域，因此相比于切比雪夫距離估價函數(shù)，曼哈頓距離估價函數(shù)在搜索算法性能方面稍遜一籌。

（3）、歐幾里得距離估價函數(shù)：歐幾里得距離是指兩點之間的直線距離。在5*5迷宮中，使用歐幾里得距離可以準(zhǔn)確地估算出兩點之間的代價，但是此估價方式需要更多的計算資源，因此可能會導(dǎo)致搜索算法性能下降。

綜上所述，在5*5迷宮尋路問題中，估價函數(shù)的選擇對搜索算法性能具有重要影響，切比雪夫距離估價函數(shù)可以在這個問題中提高搜索算法性能。

1. 流程圖

源程序代碼

import numpy as np
import heapq


class Node:
??? def __init__(self, x: int, y: int, parent=None):
??????? self.x = x
??????? self.y = y
??????? self.parent = parent
??????? self.g = 0
??????? self.h = 0

??? def __lt__(self, other):
??????? return self.g + self.h < other.g + other.h


def heuristic(a: tuple, b: tuple) -> int:
??? return abs(b[0] - a[0]) + abs(b[1] - a[1])


def astar(maze: np.array, start: tuple, end: tuple) -> list:
??? open_set = []
??? closed_set = set()
??? start_node = Node(start[0], start[1])
??? end_node = Node(end[0], end[1])
??? heapq.heappush(open_set, start_node)

??? while len(open_set) > 0:
??????? current_node = heapq.heappop(open_set)
??????? if current_node.x == end_node.x and current_node.y == end_node.y:
??????????? path = []
??????????? while current_node is not None:
??????????????? path.append((current_node.x, current_node.y))
??????????????? current_node = current_node.parent
??????????? return path[::-1]
??????? closed_set.add((current_node.x, current_node.y))

??????? for x, y in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
??????????? node = Node(current_node.x + x, current_node.y + y, current_node)
??????????? if node.x < 0 or node.y < 0 or node.x >= maze.shape[0] or node.y >= maze.shape[1]:
???????? ???????continue
??????????? if maze[node.x][node.y] == 1:
??????????????? continue
??????????? if (node.x, node.y) in closed_set:
??????????????? continue
??????????? node.g = current_node.g + 1
??????????? node.h = heuristic((node.x, node.y), (end_node.x, end_node.y))
??????????? heapq.heappush(open_set, node)

??? return None


if __name__ == '__main__':
??? start = (0, 0)
??? end = (4, 4)
??? maze = np.array([
??????? [0, 0, 0, 0, 1],
??????? [1, 1, 1, 0, 1],
??????? [0, 0, 0, 0, 0],
??????? [1, 1, 1, 1, 0],
??????? [1, 1, 1, 1, 0]
??? ])

??? path = astar(maze, start, end)
??? print(path)

實驗總結(jié)

通過這次實驗，我掌握了如何使用A*搜索算法解決迷宮問題和八數(shù)碼問題。這是一種常用的人工智能搜索算法，可以用于尋找路徑和規(guī)劃。

在實驗中，首先學(xué)習(xí)了迷宮問題的定義和A算法的基本思路。我們使用Python編寫代碼，在55大小的迷宮中，通過A*算法計算出從起點到終點的最短路徑。其中，需要考慮迷宮的障礙物、每個節(jié)點的代價值和啟發(fā)式函數(shù)等因素，也需要用到優(yōu)先隊列來存儲待擴展的節(jié)點。最后，通過繪制迷宮地圖和標(biāo)注路徑，完成了實驗任務(wù)。

接著，學(xué)習(xí)了八數(shù)碼問題的定義和A算法的適用性。同樣利用Python編寫代碼，通過A算法計算出從初始狀態(tài)到目標(biāo)狀態(tài)的最短路徑。在實驗中，為了提高算法效率和減少搜索深度，設(shè)計了一種簡單而可行的啟發(fā)式函數(shù)，并使用優(yōu)先隊列存儲待擴展的節(jié)點，最終完成了實驗任務(wù)。

通過這次實驗，除了掌握了A*搜索算法的應(yīng)用，還進一步了解了Python的函數(shù)定義語法和相關(guān)知識，同時也加深了對算法原理和機制的理解。文章來源地址http://www.zghlxwxcb.cn/news/detail-794498.html

到了這里，關(guān)于人工智能之A*算法求解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！