我被困在想出一個演算法，我現在不知道該怎么做。
我需要從a到d但只能通過滾動瀏覽這些串列：
[e, d]
[a, b, c]
[d, a]
[a, b]
[a, e, b]
這當然是一個簡單的例子，解決方案是：
[a → d] // 3rd line
[a → e → d] // 5th line 1st line
[a → b → e → d] // 2nd 5th 1st line
但我必須在Python 中解決它。我想出了兩種方法來解決這個問題，第一種是使用 for 回圈，但是回圈開始重復并且非常耗時，所以我采用了想法 2。我正在考慮創建一個所有可能的變體串列用a與結束d。然后在我們指定的串列中檢查這是否可能。
from itertools import permutations
lst = ['a', 'b', 'c', 'd', 'e']
x = 'a'
y = 'd'
for i in range(1, len(lst)):
perm = permutations(lst, i 1)
for j in list(perm):
if (j[0] == x) and (j[-1] == y):
print(j)
但后來不知何故我被卡住了，我現在不知道該怎么辦。有人可以給我一個提示嗎？還是我在做這一切都錯了？
編輯：
我正在嘗試找到所有路徑并列印它們。
uj5u.com熱心網友回復：
這是一個圖問題，其中串列是節點之間的無向邊。例如：
[a, b, c]
意味著從ato band c、 from bto aandc和 from cto aand存在無向邊b。當然，a-- b，也意味著b-- a。為了清楚起見，我重復了上面的邊緣。
因此，您想要做的是創建一個表示所有這些邊的鄰接串列并應用回溯，因為您需要從源到目標的所有可能路徑。
這是一些向您展示這個想法的代碼：
adj_list = collections.defaultdict(set)
for row in rows:
for i, el in enumerate(row):
for j in range(i 1, len(row):
adj_list[el].add(row[j])
adj_list[row[j]].add(el)
def backtrack(node, adj_list, seen, partial_res, res):
if node == target:
res.append(partial_res[:])
for neighbor in adj_list[node]:
if neighbor in seen: continue
seen.add(neighbor)
partial_res.append(neighbor)
backtrack(neighbor, adj_list, seen, partial_res, res)
partial_res.pop()
seen.remove(neighbor)
res = []
backtrack(start, adj_list, set(), [], res)
print(res)
我沒有運行這個。但是代碼應該給出回溯如何作業的概念。這是一個 dfs，您可以在其中檢查每條可能的路徑并跟蹤您走過的邊緣。如果它通向目的地，則在最終結果中保存它的副本。
請注意，該演算法在每條路徑中僅訪問每個節點一次。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/387609.html