将一个单词转换为另一个单词的最短路径
https://stackoverflow.com/questions/1521958
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
对于数据结构项目，我必须找到两个单词之间的最短路径（例如 "cat" 和 "dog"），一次只更改一个字母。为我们提供了一个拼字游戏列表，可用于查找我们的路径。例如：
cat -> bat -> bet -> bot -> bog -> dog
我已经使用广度第一次搜索解决了问题，但是正在寻找更好的东西（我用trie代表字典）。
请给我一些想法，以实现更有效的方法（就速度和内存而言）。首选荒谬和/或具有挑战性的东西。
我问我的一个朋友（他是大三），他说 不 有效解决此问题。他说我会学到为什么我参加算法课程时。对此有任何评论吗？
我们必须从单词转到单词。我们不能走 cat -> dat -> dag -> dog. 。我们还必须打印出遍历。
解决方案
新答案
鉴于最近的更新，您可以尝试以锤子距离作为启发式距离尝试。这是一种可接受的启发式，因为它不会高估距离
旧答案
您可以修改用于计算的动态程序 Levenshtein距离 获得操作顺序。
编辑：如果存在恒定数量的字符串，则可以在多项式时间内解决问题。否则，这是NP-HARD（Wikipedia中的一切）。假设您的朋友在谈论问题是NP-Hard。
编辑：如果您的字符串长度相等，则可以使用 锤距.
其他提示
使用字典，BFS是最佳的，但是所需的运行时间与其大小成正比（V+E）成正比。使用n个字母，字典可能具有〜A^n的整体，其中一个是字母大小。如果字典包含除链末端的所有单词，那么您将穿越所有可能的单词，但不会找到任何单词。这是图形遍历，但大小可能呈指数较大。
您可能想知道是否可以更快地进行操作 - “智能”浏览结构，然后在多项式时间内进行。我认为答案是不。
问题：
您给了您一种快速（线性）检查单词是否在字典中，两个单词u，v，并且要检查是否有序列1 - > a2 - > ... - > an - > v。
是NP-HARD。
证明：以3sat实例为例
（p或q或q或r）和（p或q或r）
您将从0 000 00开始，并将检查是否可以转到2 222 22。
第一个字符将是“我们完成了”，下一个下一个位将控制P，Q，R和两个下一个将控制子句。
允许的话是：
- 任何以0开头的东西，仅包含0和1
- 任何以2开始且合法的东西。这意味着它由0和1组成（除了第一个字符为2，所有条款位均根据变量位正确设置，它们设置为1（因此，这表明该公式可以满足）。
- 任何以至少两个2开头的东西，然后由0和1组成（正则表达式：222*（0+1）*，例如22221101，而不是2212001
要从0 000 00生产2 222 22，您必须以这种方式进行：
（1）翻转适当的位 - 例如0 100 111分四步。这需要找到3SAT解决方案。
（2）将第一个位更改为2：2 100111。在这里您将被验证，这确实是3SAT解决方案。
（3）更改2 100 111-> 2 200 111-> 2 220 111-> 2 222 111-> 2 222 211-> 2 222 221-> 2 222 222 222。
这些规则强制执行您不能作弊（检查）。只有在满足公式并检查NP-HARD的情况下，才能达到2 222 22。我觉得这可能更难（#P或FNP），但是NP硬度足以满足我的目的。
编辑: ：您可能对 分离设置数据结构. 。这将使您的字典和可以彼此触及的单词。您还可以存储从每个顶点到根或其他顶点的路径。这将为您提供一条路径，而不是最短的道路。
有不同效率的方法 发现 链接 - 您可以为每个单词长度构造一个完整的图形，也可以构造一个 bk-tree, ，例如，但是您的朋友是正确的-BFS是最有效的算法。
但是，有一种显着提高运行时的方法：与其从源节点进行单个BF，而是进行两个广度的首次搜索，从图表的任一端开始，并在您的边界集中找到一个共同的节点时终止。如果您仅从一端搜索，您要做的工作量大约是一半。
首先，您可以删除不是正确长度的单词来更快的。更多的有限字典将适合CPU的缓存。大概是所有的。
另外，所有的strnCMP比较（假设您使所有内容都可以进行）是memcmp比较，甚至可以是展开的比较，这可能是速度。
您可以使用一些预处理器魔术并为该单词长度进行硬编译，或者针对常见单词长度进行一些优化的任务变体。所有这些额外的比较都可以“消失”，以获得纯粹的展开乐趣。
这是一个典型的 动态编程 问题。检查编辑距离问题。
您要寻找的称为编辑距离。有许多不同的类型。
从 （http://en.wikipedia.org/wiki/edit_distance）：“在信息理论和计算机科学中，两个字符字符串之间的编辑距离是将其中一个转换为另一个操作所需的操作数量。”
这篇有关Jazzy（Java Spell Check API）的文章对这些比较有很好的概述（这是一个类似的问题 - 提供建议的更正） http://www.ibm.com/developerworks/java/library/j-jazzy/
您可以找到最长的常见子序列，因此找到必须更改的字母。
我的直觉是，您的朋友是正确的，因为没有更有效的解决方案，但这是您每次都在重新加载词典。如果您要保留一个公共过渡的运行数据库，那么肯定会有一种更有效的方法来找到解决方案，但是您需要事先生成过渡，并且发现哪些过渡是有用的（因为您无法生成生成他们全部！）可能是它自己的艺术。
bool isadjacent(string& a, string& b)
{
int count = 0; // to store count of differences
int n = a.length();
// Iterate through all characters and return false
// if there are more than one mismatching characters
for (int i = 0; i < n; i++)
{
if (a[i] != b[i]) count++;
if (count > 1) return false;
}
return count == 1 ? true : false;
}
//一个队列项目以存储单词和最小链长度//到达单词。
struct QItem
{
string word;
int len;
};
//使用最小数量的相邻动作从“开始”返回最短链的长度，以达到“目标” //。 D是字典
int shortestChainLen(string& start, string& target, set<string> &D)
{
// Create a queue for BFS and insert 'start' as source vertex
queue<QItem> Q;
QItem item = {start, 1}; // Chain length for start word is 1
Q.push(item);
// While queue is not empty
while (!Q.empty())
{
// Take the front word
QItem curr = Q.front();
Q.pop();
// Go through all words of dictionary
for (set<string>::iterator it = D.begin(); it != D.end(); it++)
{
// Process a dictionary word if it is adjacent to current
// word (or vertex) of BFS
string temp = *it;
if (isadjacent(curr.word, temp))
{
// Add the dictionary word to Q
item.word = temp;
item.len = curr.len + 1;
Q.push(item);
// Remove from dictionary so that this word is not
// processed again. This is like marking visited
D.erase(temp);
// If we reached target
if (temp == target)
return item.len;
}
}
}
return 0;
}
// Driver program
int main()
{
// make dictionary
set<string> D;
D.insert("poon");
D.insert("plee");
D.insert("same");
D.insert("poie");
D.insert("plie");
D.insert("poin");
D.insert("plea");
string start = "toon";
string target = "plea";
cout << "Length of shortest chain is: "
<< shortestChainLen(start, target, D);
return 0;
}
