我試圖從距原點給定距離的圖中找到路徑的所有組合。事實上，魔獸世界（軍團）的新擴張將向遊戲引入神器系統。
這是一個你可以升級的功能，每個級別給你1個等級，你可以在樹上的每個等級上花費1點。
你可以找到WOWHEAD每個工件的計算器和我會用這個作爲例子：http://legion.wowhead.com/artifact-calc/rogue/subtlety/查找距離原點給定距離的圖形中路徑的所有組合
基本上，該計劃的目標是：
「我給一個等級，比方說7，它返回給我的圖表中的每條路徑組合，我必須花費7點才能到達那裏（即，7個唯一節點的列表）「。
當我看到計算器，我認爲這是通過將其調換到一個圖形可解，所以我做了一個幫我打通： Graph
在圖中，我不得不做出一點調整從計算器，例如每個得到3個等級的特徵必須表示爲彼此相連的3個節點。另外，對於解鎖2種方式的特徵，我不得不將它們表示爲4個節點，以「模擬」3個節點的要求來通過。 （但我們會看到後，仍然是一個問題，它並沒有真正解決問題）
然後從那裏我試圖找到一個很好的方式列出每一種可能性，所以我做了大量的研究互聯網尋找處理我的問題的最佳方式。
我首先嚐試使用廣度優先搜索來解決這個問題，但是距離每個節點的起點並沒有多大幫助。 然後我試圖使用窮舉搜索。
我目前使用的代碼的適應貼有「尋找從給定圖的所有路徑」上的代碼審查@ StackEchange（不能發佈超過2個鏈接）
def paths(graph, v, lmax):
"""Generate the maximal cycle-free paths with a given maximum length lmax in
graph starting at v. Graph must be a mapping from vertices to collections of
neighbouring vertices.
>>> g = {1: [2, 3], 2: [3, 4], 3: [1], 4: []}
>>> sorted(paths(g, 1, 3))
[[1, 2, 3], [1, 2, 4], [1, 3]]
>>> sorted(paths(g, 3, 4))
[[3, 1, 2, 4]]
Credit to Gareth Rees from StackExchange for the original code.
"""
path = [v] # path traversed so far
seen = {v} # set of vertices in path
def search():
dead_end = True
if len(seen) < lmax:
for neighbour in graph[path[-1]]:
if neighbour not in seen:
dead_end = False
seen.add(neighbour)
path.append(neighbour)
yield from search()
path.pop()
seen.remove(neighbour)
if dead_end:
yield list(path)
yield from search()
然後我做一個函數對結果進行排序並僅顯示具有所需長度的結果。
def artifact(graph, maxrank, start):
for i in range(1, maxrank+1):
print("---------")
print("Rank: " + str(i))
print("---------")
# Get all the Paths at "i" Rank
RawPaths = sorted(paths(g, start, i), key=len)
# Remove paths that doesn't satisfact our rank requirement and sort it
ValidPaths = [sorted(j) for j in RawPaths if len(j) == i]
# Remove duplicates
UniquePaths = sorted([list(j) for j in set(map(tuple, ValidPaths))])
# Display the Paths
for j in range(len(UniquePaths)):
PathString = "";
for k in range(len(UniquePaths[j])):
PathString += str(UniquePaths[j][k]) + " "
print(PathString)
print("")
從那裏，我從圖中建立了一部分節點的相鄰節點（鄰居）列表。我不能發佈超過2個鏈接，但子圖從前面鏈接的圖中的8/7/32/31節點結束。
g = {
1: [2, 38],
2: [1, 3],
3: [2, 4],
4: [3, 5],
5: [4, 6],
6: [5, 7, 8],
7: [6],
8: [6],
31: [33],
32: [33],
33: [31, 32, 34],
34: [33, 35],
35: [34, 36],
36: [35, 37],
37: [36, 38],
38: [1, 37]
}
然後，我打電話給我的功能：
artifact(g, 8, 1)
但是使用這個列表中，我面臨的一個重大課題。事實上，該算法直到最後，但它沒有做任何回溯達到想要的等級（即在經過1-38 - 37 - 36 - 35 - 34 - 33 - 31之後，它不會回到2 - 3 - ...如果我有10分的話）。
我能夠通過將38,37，...分支添加爲鄰居2或將2,3分支添加爲38來解決此子圖問題。
所以我的名單變成了：
g = {
1: [2, 38],
2: [1, 3, 38],
3: [2, 4, 38],
4: [3, 5, 38],
5: [4, 6, 38],
6: [5, 7, 8, 38],
7: [6, 38],
8: [6, 38],
31: [2, 33],
32: [2, 33],
33: [2, 31, 32, 34],
34: [2, 33, 35],
35: [2, 34, 36],
36: [2, 35, 37],
37: [2, 36, 38],
38: [1, 2, 37]
}
然後，我能得到我想要的一切對圖形的這一部分。 現在我試圖將我的推理擴展到整個圖表。但由於主要的兩個問題，我正在努力工作：
- 當我朝着一個方向前進時，用4個節點來表示具有3個等級的特徵，但是如果我填滿了整個分支，然後嘗試去回來，我計算第四個節點。 （我仍然可以在artifact函數中刪除第4個節點，但我認爲這不是一個好方法來處理它，並且應該找到一個聰明的方法來處理它。
- 我用來鏈接前兩個分支並不直接適用於整個圖表，例如，按照我所做的，我會向29個鄰居添加32，因爲當我來自35時，32可以從29開始訪問。但是，如果我來自28和沒有添加27到路徑，那麼32通常不能從29到達。 然後我的路徑變得無效。
我不確定如果我可以這樣解決它，我希望你能夠幫助我也有這樣的感覺，我的回溯搜索方式並不完美。我也認爲：
當我在一個分支結束時，我會回到之前的分離狀態並從那裏探索。但是，由於節點已經被探索，它不會走向另一個方向並停留在那裏。
最後，我可以用任何其他方式來處理我的問題，我不想特別使用圖來解決它。
也許還有另一種方法可以有效地解決它（比如一步一步地構建圖形，並且有多個隊伍可以花費並逐漸消耗它們，而節點則可以解鎖）。
預先感謝您的幫助和抱歉，我的英語水平的錯誤，我是法國人:)
是不是固定最大步驟的BFS解決您的問題？ – shole