為了解決專案 euler 的問題 83，我嘗試使用 A* 演算法。該演算法適用于給定的問題，我得到了正確的結果。但是當我將演算法可視化時，我意識到演算法似乎檢查了許多可能的節點。是因為我沒有正確實作演算法還是我錯過了其他東西？我嘗試使用您可以在下面的代碼中看到的兩種不同的啟發式函式，但輸出并沒有太大變化。
如果有任何提示可以使代碼更高效，我也會很感激，因為我是一個初學者。
import heapq
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from matplotlib import animation
import numpy as np
class PriorityQueue:
def __init__(self):
self.elements = []
def empty(self):
return not self.elements
def put(self, item, priority):
heapq.heappush(self.elements, (priority, item))
def get(self):
return heapq.heappop(self.elements)[1]
class A_star:
def __init__(self, data, start, end):
self.data = data
self.start = start
self.end = end
self.a = len(self.data)
self.b = len(self.data[0])
def h_matrix(self):
elements = sorted([self.data[i][j] for j in range(self.b) for i in range(self.a)])
n = self.a self.b - 1
minimum = elements[:n]
h = []
for i in range(self.a):
h_i = []
for j in range(self.b):
h_i.append(sum(minimum[:(n-i-j-1)]))
h.append(h_i)
return h
def astar(self):
h = self.h_matrix()
open_list = PriorityQueue()
open_list.put(self.start, 0)
came_from = {}
cost_so_far = {}
came_from[self.start] = None
cost_so_far[self.start] = self.data[0][0]
checked = []
while not open_list.empty():
current = open_list.get()
checked.append(current)
if current == self.end:
break
neighbors = [(current[0] x, current[1] y) for x, y in {(-1,0), (0,-1), (1,0), (0,1)}
if 0 <= current[0] x < self.a and 0 <= current[1] y < self.b]
for next in neighbors:
new_cost = cost_so_far[current] self.data[next[0]][next[1]]
if next not in cost_so_far or new_cost < cost_so_far[next]:
cost_so_far[next] = new_cost
priority = new_cost h[next[0]][next[1]]
open_list.put(next, priority)
came_from[next] = current
return came_from, checked, cost_so_far[self.end]
def reconstruct_path(self):
paths = self.astar()[0]
best_path = [self.end]
while best_path[0] is not None:
new = paths[best_path[0]]
best_path.insert(0, new)
return best_path[1:]
def minimum(self):
return self.astar()[2]
if __name__ == "__main__":
liste = [[131, 673, 234, 103, 18], [201, 96, 342, 965, 150], [630, 803, 746, 422, 111], [537, 699, 497, 121, 956], [805, 732, 524, 37, 331]]
path = A_star(liste, (0,0), (4,4))
print(path.astar())
#print(path.reconstruct_path())
path.plot_path(speed=200)
在這里，您可以看到我對問題中給出的 80x80 矩陣的可視化。藍色是選中的所有點，紅色是最佳路徑。據我了解，矩陣中的每個點都不應該被選中，即藍色。 https://i.stack.imgur.com/LKkdh.png
我最初的猜測是我的啟發式函式不夠好。如果我選擇 h=0，這意味著 Dijkstra 演算法，我的檢查串列的長度是 6400。相反，如果我使用我的自定義 h，長度是 6455。但是如何改進任意矩陣的啟發式函式？謝謝你的幫助。
uj5u.com熱心網友回復：
讓我從你帖子的結尾開始：
將單元格標記為選中
如果我使用我的自定義 h，則長度為 6455。
您的大小不應checked超過單元格的數量。因此，讓我首先建議對此進行改進：不要使用串列，而是使用集合，并跳過從集合中已經存在的優先級佇列中彈出的任何內容。相關代碼將如下所示：
checked = set()
while not open_list.empty():
current = open_list.get()
if current in checked: # don't repeat the same search
continue
checked.add(current)
如果最終您需要 的串列版本checked，只需以這種方式回傳：
return came_from, list(checked), cost_so_far[self.end]
現在主要問題：
改進啟發式函式
據我了解，矩陣中的每個點都不應該被選中，即藍色。我最初的猜測是我的啟發式函式不夠好。
這是正確的解釋。將其與給定矩陣的路徑的總成本非常接近這一事實相結合，因此存在一個涉及矩陣大部分內容的競爭領域。
如何改進任意矩陣的啟發式函式？
一個想法是考慮以下內容。一條路徑必須包含來自每個“前向”對角線 ( /)的至少一個元素。因此，如果我們在每個這樣的對角線上使用最小值并創建運行總和（向后 - 從目標開始），我們將獲得h.
這是該想法的代碼：
def h_matrix(self):
min_diagonals = [float("inf")] * (self.a self.b - 1)
# For each diagonal get the minimum cost on that diagonal
for i, row in enumerate(self.data):
for j, cost in enumerate(row):
min_diagonals[i j] = min(min_diagonals[i j], cost)
# Create a running sum in backward direction
for i in range(len(min_diagonals) - 2, -1, -1):
min_diagonals[i] = min_diagonals[i 1]
min_diagonals.append(0) # Add an entry for allowing the next logic to work
# These sums are a lower bound for the remaining cost towards the target
h = [
[min_diagonals[i j 1] for j in range(self.b)]
for i in range(self.a)
]
return h
通過這些改進，我們得到了這些計數：
len(cost_so_far) == 6374
len(checked) == 6339
這仍然代表了矩陣的很大一部分，但至少有幾個單元格被遺漏了。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/478419.html
下一篇：實作以下結果的最佳方法是什么？