我正在研究一個關于 Word Ladder 的問題，有一些額外的限制（給出了一個單詞串列，并且梯子僅由這些單詞構成，而不是整個英語）。除了傳統的 Word Ladder 問題之外，還有 2 個約束條件：
- 最小化單詞階梯的字母距離。
例如，“aab”和“aaa”的距離為 1，因為“b”是字母表的第二個字母，而“a”是第一個字母。"bbb" 和 "bwb" 的距離是 21，因為 "b" 是字母表的第二個字母，而 "w" 是第二個字母。
- 我們需要在梯子中使用一組特定詞中的一個，比如“繞道”。
這意味著，給定來自原始單詞的單詞串列 (>=1) ，這些單詞中至少有一個必須出現在單詞階梯中。
這個問題有一個復雜性約束，即 O(Elog(W) Wlog(W)))，其中
E是相差一個字母的單詞對的數量
W是單詞總數
請注意，這種復雜性不涉及任何與“繞行”字的大小相關的術語。
# One example is (we denote the word as indices in the list):
words = [’aaa’,’bbb’,’bab’,’aaf’,’aaz’,’baz’,’caa’,’cac’,’dac’,’dad’,’ead’,’eae’,’bae’,’abf’,’bbf’]
start word = 0 # ("aaa")
end word = 1 # ("bbb")
detour = [12] # ("bae")
# The result path is: [0, 6, 7, 8, 9, 10, 11, 12, 2, 1]
# corresponding to the list of the words: [’aaa’, ’caa’, ’cac’, ’dac’, ’dad’, ’ead’, ’eae’, ’bae’, ’bab’, ’bbb’]
現在我的實作只是運行Dijkstra 演算法，它的復雜度為 O(Elog(W))，在從起始詞到“繞行”詞之一，以及從該繞道詞到最終目標詞的每個組合上。計算所有并找到具有最小字母距離的一個。
我認為這不好，我不確定它是否超過了時間復雜度。同時，我不明白為什么復雜性不涉及“繞道”字樣的大小。如何確保路徑最短同時包含至少一個“繞道”詞（并滿足復雜性）？
有沒有人有更好的主意來解決這個問題？非常感謝。
uj5u.com熱心網友回復：
這可以在與 Dijkstra 演算法使用小的增強完全相同的時間復雜度下完成。我們v用兩個頂點(v, 0)和替換原始圖中的每個頂點(v, 1)，表示我們是否已經繞道而行。我們現在正在搜索從(start, x)to的最短路徑(end, 1)，其中 x 是1或0如果 start 是或不是繞道，分別。
優先級佇列Q僅(start, x)在優先級/距離為 時初始化0。Dijkstra 演算法中鄰居的主回圈轉換為（偽代碼）：
while Q is not empty:
(v, has_detour) <- extract_min_heap(Q)
for neighbor, edge_cost in neighbors[v]:
detour_status <- has_detour | is_detour(neighbor)
alt_cost = dist[v, has_detour] edge_cost
if alt_cost < dist[neigh, detour_status]:
dist[neigh, detour_status] = alt_cost
predecessor[neigh, detour_status] = (v, has_detour)
add (neigh, detour_status) to Q with priority == alt_cost
請注意，我們沒有通過原始邊集顯式構建增強圖 G*，而是通過 Dijkstra 的輔助資料結構隱式構建。當然，您實際上可以存盤新圖，其定義如下：
Given a directed graph G = (V, E),
Define a new directed graph G* = (V*, E*):
Vertex set V* := V x {0,1}
Edge set E* := {((v,1), (w,1)) | (v,w) ∈ E}
∪ {((v,0), (w,0)) | (v,w) ∈ E and w ? detours}
∪ {((v,0), (w,1)) | (v,w) ∈ E and w ∈ detours}
由于我們的新圖（我們實際在其上運行 Dijkstra 的）具有2|V|頂點和2|E|邊，因此新的漸近運行時和空間復雜度與 Dijkstra 的原始實作中的相同。確保使用基于set或 hashmap 的資料結構is_detour()在O(1).
有關完整的 Python 實作，請參見下文。與繞道相關的代碼更改幾乎都在該主回圈中：大部分代碼正在構建標準的單詞階梯圖。構建圖形可能需要|V|^2 * word_len或|V|*(word_len^2) |E|，具體取決于您的操作方式。我在這里選擇了第二種方法。
def word_ladder(words: List[str],
start_word_idx: int,
end_word_idx: int,
detour_idxs: List[int]) -> Optional[List[int]]:
"""Given a list of distinct equal length lowercase words,
find a word ladder of minimum pairwise alphabetic distance
from start to end if one exists, or return None otherwise"""
def letter_dist(letter1: str, letter2: str) -> int:
return abs(ord(letter1) - ord(letter2))
detour_idx_set = set(detour_idxs)
word_bases = collections.defaultdict(list)
graph = collections.defaultdict(list)
word_len = len(words[0])
for i, word in enumerate(words):
as_list = list(word)
for j in range(word_len):
old = as_list[j]
as_list[j] = '0'
word_base = ''.join(as_list)
for other_word_idx in word_bases[word_base]:
dist = letter_dist(old, words[other_word_idx][j])
graph[i].append((other_word_idx, dist))
graph[other_word_idx].append((i, dist))
word_bases[word_base].append(i)
as_list[j] = old
distances = collections.defaultdict(lambda: math.inf)
queue = []
start_is_detour = 1 if start_word_idx in detour_idx_set else 0
queue.append((0, start_word_idx, start_is_detour))
distances[start_word_idx, start_is_detour] = 0
parent = {}
def reconstruct_ladder() -> List[int]:
vert, detour_status = end_word_idx, 1
path = []
while (vert, detour_status) in parent:
path.append(vert)
vert, detour_status = parent[vert, detour_status]
path.append(vert)
path.reverse()
return path
while len(queue) != 0:
distance, index, has_detour = heapq.heappop(queue)
if distances[index, has_detour] != distance:
continue
for neighbor_idx, edge_cost in graph[index]:
detour_status = has_detour | (neighbor_idx in detour_idx_set)
if distance edge_cost < distances[neighbor_idx, detour_status]:
distances[neighbor_idx, detour_status] = distance edge_cost
parent[neighbor_idx, detour_status] = (index, has_detour)
heapq.heappush(queue,
(distances[neighbor_idx, detour_status],
neighbor_idx, detour_status))
if (end_word_idx, 1) not in parent:
return None
return reconstruct_ladder()
根據您的輸入，可以像這樣使用：
words = ['aaa', 'bbb', 'bab', 'aaf', 'aaz', 'baz', 'caa', 'cac', 'dac', 'dad', 'ead', 'eae', 'bae', 'abf', 'bbf']
start = 0
end = 1
detours = [12]
print(word_ladder(words=words, start_word_idx=start,
end_word_idx=end, detour_idxs=detours))
[0, 6, 7, 8, 9, 10, 11, 12, 2, 1]
請注意，Dijkstra 的這種實作不使用 Decrease-Key，因此理論上的運行時間是次優的。當然，大多數實際實作也是如此。如果有問題，請隨意使用斐波那契堆或類似物。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313558.html
下一篇：生成以前不存在于串列中的亂數