所有组合树算法

Question

我有一个与树有关的问题。我对“汽车”这个主题有大约100个句子。这些句子基本上讲的是一辆汽车。如果用户提交查询：“查找单词之间的单词链接的所有组合”engine“和”oil“。”我想找到所有可能的单词链接，以便“引擎”和“油”通过一个句子中的任意数量的相似单词连接起来。

例如，

1. 发动机运转时发热。
2. 汽车有一个引擎。
3. 汽车使用油。

在这种情况下，答案将是：engine-> car-> oil（三字组合）。我想找到所有可能的组合，以便最终“引擎”和“油”彼此连接。它不是最短的路径，也不是最长的路径，而是所有可能的路径都沿着各个方向和词汇。当然，只要路径不相似，甚至可以有1000个字组合来达到“引擎”和“机油”。

有没有办法做到这一点。我尝试使用面包先，但它有点棘手。例如组合可以。

1. 发动机 - >小车 - >运行 - >停止 - >油
2. 发动机 - >小车 - >油
3. 发动机 - >快> brake->油

任何人都可以请帮我解决一下这个。这里的逻辑和想法是什么。我不能忽视我已经访问过的一个词，因为这会停止算法，并且不会给我所有的链接。

请帮助和见解。

谢谢。

fa323

Answer 1

你的问题是这样得以确认...也就是说，即使是在你的榜样，为什么答案不包括engine->an->oil目前还不清楚。

此外，它实际上与树木没有任何关系，它处理图形。

您需要做的第一件事就是确定如何构建图形。这样做的合理方法是在两个单词之间出现边界，如果它们都出现在特定的句子中。

然后你必须决定你想输出什么。我非常怀疑你想要所有的路径。为什么？那么，如果你构建了我描述的图表，那么即使只使用第一句话，从引擎到油的路径也有24条，不包括循环路径。然而，如果这就是你想要的，你可以通过深度优先搜索找到图中所有的非循环路径，当你将它推入堆栈时标记访问的节点，并在关闭时取消标记。