python - 中间强制单词的单词阶梯问题

Question

我正在研究一个关于单词阶梯的问题，有一些额外的限制(给出了单词列表，并且阶梯仅由这些单词构建，而不是整个英语)。除了传统的字梯问题外，还有 2 个约束:

1. minimize the alphabetic distance of the word ladder.

例如，“aab”和“aaa”的距离为 1，因为“b”是字母表中的第二个字母，而“a”是第一个字母。 “bbb”和“bwb”的距离为 21，因为“b”是字母表中的第二个字母，而“w”是第二十三个字母。

2. we need to use one of a set of particular words in the ladder, say "detour".

这意味着，给定原始单词的单词列表 (>= 1)，这些单词中至少有一个必须出现在单词梯中。

这道题有一个复杂度约束，为 O(Elog(W) + Wlog(W)))，其中

E is the number of pairs of words which differ by exactly one letter

W is the total number of words

请注意，这种复杂性不涉及任何与“绕行”字的大小相关的术语。

# 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))，针对从起始词到“绕行”词之一的每个组合，以及从该绕行单词到最终目标单词。计算所有并找到字母距离最小的一个。

我认为这不好，我不确定它是否超出了时间复杂度。同时，我不明白为什么复杂性不涉及“绕道”词的大小。如何保证路径最短，同时至少包含一个“绕行”词(并满足复杂度)？

有没有人有更好的主意来解决这个问题？非常感谢。

Answer 1

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

优先级队列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 的数据结构在 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，因此理论上的运行时间不是最优的。当然，大多数实际实现也是如此。如果您担心的话，请随意使用斐波那契堆或类似的方法。