Cha*_*t1c 2 python algorithm graph dijkstra shortest-path
我正在研究一个关于单词阶梯的问题，带有一些额外的约束（给出了单词列表，并且阶梯仅由这些单词构建，而不是整个英语）。\n除了传统的Word Ladder问题：
\n\n\n\n
\n- 最小化单词阶梯的字母距离。
\n
例如，“aab”和“aaa”的距离为 1，因为“b”是字母表中的第二个字母，而“a”是第一个字母。“bbb”和“bwb”的距离为 21，因为“b”是字母表中的第二个字母，而“w”是第二十三个字母。
\n\n\n\n
\n- 我们需要在梯子中使用一组特定单词中的一个，例如“绕行”。
\n
这意味着，给定原始单词的单词列表 (>= 1)，这些单词中至少有一个必须出现在单词梯中。
\n该问题有一个复杂度约束，即 O(Elog(W) + Wlog(W)))，其中
\n\n\nE是仅相差一个字母的单词对的数量
\nW是单词总数
\n
请注意，这种复杂性不涉及任何与“绕行”字的大小相关的术语。
\n# One example is (we denote the word as indices in the list):\nwords = [\xe2\x80\x99aaa\xe2\x80\x99,\xe2\x80\x99bbb\xe2\x80\x99,\xe2\x80\x99bab\xe2\x80\x99,\xe2\x80\x99aaf\xe2\x80\x99,\xe2\x80\x99aaz\xe2\x80\x99,\xe2\x80\x99baz\xe2\x80\x99,\xe2\x80\x99caa\xe2\x80\x99,\xe2\x80\x99cac\xe2\x80\x99,\xe2\x80\x99dac\xe2\x80\x99,\xe2\x80\x99dad\xe2\x80\x99,\xe2\x80\x99ead\xe2\x80\x99,\xe2\x80\x99eae\xe2\x80\x99,\xe2\x80\x99bae\xe2\x80\x99,\xe2\x80\x99abf\xe2\x80\x99,\xe2\x80\x99bbf\xe2\x80\x99]\nstart word = 0 # ("aaa")\nend word = 1 # ("bbb")\ndetour = [12] # ("bae")\n# The result path is: [0, 6, 7, 8, 9, 10, 11, 12, 2, 1]\n# corresponding to the list of the words: [\xe2\x80\x99aaa\xe2\x80\x99, \xe2\x80\x99caa\xe2\x80\x99, \xe2\x80\x99cac\xe2\x80\x99, \xe2\x80\x99dac\xe2\x80\x99, \xe2\x80\x99dad\xe2\x80\x99, \xe2\x80\x99ead\xe2\x80\x99, \xe2\x80\x99eae\xe2\x80\x99, \xe2\x80\x99bae\xe2\x80\x99, \xe2\x80\x99bab\xe2\x80\x99, \xe2\x80\x99bbb\xe2\x80\x99]\n现在我的实现只是运行Dijkstra\xe2\x80\x99s 算法，其复杂度为 O(Elog(W))，对从起始词到“绕行”词之一，以及从绕行词到最终目标词。计算所有并找到字母距离最小的一个。
\n我认为这不好，我不确定它是否超出了时间复杂度。同时，我不明白为什么复杂性不涉及“绕道”词的大小。如何确保路径最短，同时至少包含一个“绕道”词（并满足复杂度）？
\n有没有人有更好的主意来解决这个问题？\n非常感谢。
\n这可以通过使用小幅增强以与 Dijkstra 算法完全相同的时间复杂度来完成。我们用两个顶点和替换v原始图中的每个顶点，表示我们是否已经访问了绕道。我们现在正在搜索从到 的最短路径，其中 x 分别是或如果 start 是或不是绕道。(v, 0)(v, 1)(start, x)(end, 1)10
优先级队列仅在优先级/距离为 时Q初始化。Dijkstra 算法中邻居的主循环转换成这样（伪代码）：(start, x)0
while Q is not empty:\n (v, has_detour) <- extract_min_heap(Q)\n\n for neighbor, edge_cost in neighbors[v]:\n detour_status <- has_detour | is_detour(neighbor)\n alt_cost = dist[v, has_detour] + edge_cost\n\n if alt_cost < dist[neigh, detour_status]:\n dist[neigh, detour_status] = alt_cost\n predecessor[neigh, detour_status] = (v, has_detour)\n add (neigh, detour_status) to Q with priority == alt_cost\n请注意，我们没有通过原始边集显式构造增强图 G*，仅通过 Dijkstra 的辅助数据结构隐式构造。当然，您实际上可以存储新图，其定义如下：
\nGiven a directed graph G = (V, E),\nDefine a new directed graph G* = (V*, E*):\n\nVertex set V* := V x {0,1}\n\nEdge set E* := {((v,1), (w,1)) | (v,w) \xe2\x88\x88 E} \n \xe2\x88\xaa {((v,0), (w,0)) | (v,w) \xe2\x88\x88 E and w \xe2\x88\x89 detours} \n \xe2\x88\xaa {((v,0), (w,1)) | (v,w) \xe2\x88\x88 E and w \xe2\x88\x88 detours}\n由于我们的新图（我们实际运行 Dijkstra 的图）具有2|V|顶点和2|E|边，因此新的渐近运行时和空间复杂度与 Dijkstra 的原始实现中的相同。确保使用set基于 hashmap 的数据结构来is_detour()实现O(1)。
有关完整的 Python 实现，请参阅下文。与弯路相关的代码更改几乎都在该主循环中：大部分代码正在构建标准字梯图。构建图表可以采用|V|^2 * word_len或|V|*(word_len^2) + |E|，具体取决于您的操作方式。我在这里选择了第二种方法。
Given a directed graph G = (V, E),\nDefine a new directed graph G* = (V*, E*):\n\nVertex set V* := V x {0,1}\n\nEdge set E* := {((v,1), (w,1)) | (v,w) \xe2\x88\x88 E} \n \xe2\x88\xaa {((v,0), (w,0)) | (v,w) \xe2\x88\x88 E and w \xe2\x88\x89 detours} \n \xe2\x88\xaa {((v,0), (w,1)) | (v,w) \xe2\x88\x88 E and w \xe2\x88\x88 detours}\n根据您的输入，可以像这样使用：
\nwords = [\'aaa\', \'bbb\', \'bab\', \'aaf\', \'aaz\', \'baz\', \'caa\', \'cac\', \'dac\', \'dad\', \'ead\', \'eae\', \'bae\', \'abf\', \'bbf\']\nstart = 0\nend = 1\ndetours = [12]\n\nprint(word_ladder(words=words, start_word_idx=start,\n end_word_idx=end, detour_idxs=detours))\n[0, 6, 7, 8, 9, 10, 11, 12, 2, 1]\n请注意，Dijkstra 的此实现不使用 Decrease-Key，因此理论上的运行时间不是最优的。当然，大多数实际实现也是如此；如果您担心的话，请随意使用斐波那契堆或类似的方法。
\n