中间有必填词的字梯问题

Question

中间有必填点的单词天梯

Answer 1

这可以在与 Dijkstra 算法完全相同的时间复杂度下使用小的增强来完成。我们将原始图中的每个顶点 v 替换为两个顶点 (v, 0) 和 (v, 1)，表示我们是否绕过弯路。我们现在正在搜索从 (start, x) 到 (end, 1) 的最短路径，其中 x 分别是 1 或 0 如果开始是绕行或不是绕行。

优先级队列 Q 在 0 的 priority/distance 仅使用 (start, x) 初始化。 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| 个边，新的渐近运行time 和 space 复杂性与 Dijkstra 的原始实现相同。确保使用 set 或基于 hashmap 的数据结构在 O(1).

中实现 is_detour()

有关完整的 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，因此理论上的运行time 不是最优的。当然，大多数实际实现也是如此。如果有问题，请随意使用 Fibonacci-Heap 或类似工具。

中间有必填词的字梯问题

Word Ladder Problem with mandatory words in the middle

python

algorithm

graph

shortest-path

dijkstra