改造一个字的最短路径到另一个 [英] Shortest path to transform one word into another

问题描述

对于数据结构的项目，我必须找到两个单词（之间的最短路径类似猫和狗），只改变一次一个字母。我们有一个拼字单词列表中找到我们的道路使用。例如：

For a Data Structures project, I must find the shortest path between two words (like "cat" and "dog"), changing only one letter at a time. We are given a Scrabble word list to use in finding our path. For example:

cat -> bat -> bet -> bot -> bog -> dog

我已经解决了使用广度优先搜索这个问题，但我追求更好的东西（我重新presented有线索的字典）。

I've solved the problem using a breadth first search, but am seeking something better (I represented the dictionary with a trie).

请给我一些想法，更有效的方法（在速度和内存方面）。可笑的东西和/或具有挑战性的是preferred。

Please give me some ideas for a more efficient method (in terms of speed and memory). Something ridiculous and/or challenging is preferred.

我问我的朋友（他是一名大三学生）之一，他说，是的没有的有效的解决了这个问题。他说我知道为什么，当我把算法过程。上任何意见？

I asked one of my friends (he's a junior) and he said that there is no efficient solution to this problem. He said I would learn why when I took the algorithms course. Any comments on that?

我们必须从字到词。我们不能猫 - ＆GT; DAT - ＆GT; DAG - ＆GT;狗。我们还打印出遍历

We must move from word to word. We cannot go cat -> dat -> dag -> dog. We also have to print out the traversal.

推荐答案

新的答案

鉴于近期更新，你可以尝试用汉明距离作为启发式A *。它是因为它可容许的启发式不是要高估的距离

Given the recent update, you could try A* with the Hamming distance as a heuristic. It's an admissible heuristic since it's not going to overestimate the distance

OLD答案

您可以修改用于计算 Levenshtein距离的动态程序来获得操作顺序。

You can modify the dynamic-program used to compute the Levenshtein distance to obtain the sequence of operations.

编辑：如果有一个字符串常量数字，问题是在多项式时间。否则，它是NP难（这一切都没有在维基百科）..假设你的朋友都在谈论这个问题是NP难。

If there are a constant number of strings, the problem is solvable in polynomial time. Else, it's NP-hard (it's all there in wikipedia) .. assuming your friend is talking about the problem being NP-hard.

编辑：如果你的字符串长度相等，则可以使用汉明距离

If your strings are of equal length, you can use Hamming distance.

这篇关于改造一个字的最短路径到另一个的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！