感谢大家回复想法和替代解决方案.总是欢迎更有效的解决问题的方法,以及提醒我质疑我的假设.也就是说,我希望你暂时忽略我试图通过算法解决的问题,并且只是帮助我分析我编写的算法的大复杂性 - 一个简单的路径在曲线图使用深度限制搜索所描述这里,和实施这里.谢谢!
编辑:这是作业,但我已经提交了这个作业,我只想知道我的答案是否正确.当涉及递归时,我对Big-O的复杂性感到有些困惑.
原始问题如下:
我试图找到这个算法给出的全路径搜索的复杂性.给定两个顶点,我使用深度优先搜索找到它们之间的所有简单路径.
我知道DFS的时间复杂度是O(V + E),它的空间复杂度是O(V),我的直觉是全路径搜索的复杂性将超过这个,但我无法确定它将是什么.
更新(回应下面的评论):
我正在努力解决凯文培根的六度问题.这通常需要找到一对演员之间的最低分离度,但我必须找到所有分离度(目前,小于6,但这可能会改变).
考虑到字母到值的映射,我正试图找到一种方法来确定可以由给定数字拼出的所有可能的单词.
我最终希望找到适用于字母的任何1位或2位数值映射的解决方案,但为了说明,假设A = 1,B = 2,... Z = 26.
例如:12322可以等于abcbb (1,2,3,2,2),lcbb (12,3,2,2),awbb (1,23,2,2),abcv (1,2,3,22),awv (1,23,22),或lcv (12,3,22).
这是我到目前为止所想到的:
我将使用数字构建一个包含所有可能单词的树.
为此,我将从一棵树开始,其中一个根节点带有虚拟数据.
我将从最低有效数字开始逐位解析数字.
在每一步,我将取数字剩余部分的最后一位,并将其插入当前节点的左子树,并从该节点的左子树的数字中删除该数字.对于同一节点,我将检查先前的两个数字是否一起形成一个有效的字母表,如果是,我将把它们放入正确的子树(并从该节点的右子树的数字中删除2位数).
然后,我将使用剩下的数字部分递归地为每个节点重复上述步骤,直到没有剩余数字为止.
为了说明,12322我的树看起来像这样:
*
/ \
/ \
2 22
/ / \
2 3 23
/ \ / \ /
3 23 2 12 1
/ \ / /
2 12 1 1
/
1
为了获得这些单词,我将遍历从叶子到节点的所有可能路径.
这似乎是一个过于复杂的解决方案,我认为这是一个相当简单的问题,我试图找到是否有一种更简单的方法来解决这个问题.