我有一个国家的名单,我想有一个最长的国家路径,每个国家选择必须以相同的字母结束前一个元素
nations = ['albania','andorra','austria','belarus','belgium','bosnia and herzegovina',
'bulgaria','croatia','czech republic','denmark','estonia',
'finland','france','germany','greece','hungary',
'iceland','ireland','italy','latvia','liechtenstein','lithuania','luxembourg',
'macedonia','malta','moldova','monaco','montenegro','netherlands',
'norway','poland','portugal','romania','russia',
'san marino','serbia','slovakia','slovenia','spain','sweden', 'switzerland',
'ukraine','united kingdom','vatican city']
chain('spain')
>>>['spain', 'netherlands', 'slovenia', 'andorra', 'austria', 'albania']
我试过这样做,但没用
^{pr2}$有什么建议吗?在
顺便说一句,你的问题是NP完全的(这意味着它没有“快速”的多项式时间解),它对于小问题是可以解决的,但是它很快就会变得非常困难。在
你的问题可以看作是longest-path problem on a directed graph。在
w1
和w2
,如果w1
的最后一个字母与w2
的第一个字母相同,则画一条边w1 -> w2
。在w2->w1
的最后一个字母与w1
的第一个字母相同,则从w2->w1
绘制反向边缘。在下面是一个水果和蔬菜列表的示例图:
Apple, banana, eggplant, kiwifruit, orange, oregano, tangerine, zucchini
。在此图可能包含循环(例如,此图有一个循环
eggplant -> tangerine -> eggplant -> tangerine....
。The longest path problem for directed graphs containing cycles is NP-complete.因此这个问题没有多项式时间解。在这并不意味着你不能比暴力做得更好。There's a dynamic programming algorithm,它将复杂度从}(超指数,仍然不好,但比阶乘好)
O(n!)
(阶乘,非常bad)降低到{我也用递归下降法。不确定动态规划是否适合这一点,因为列表会在我们进行修改时进行修改。稍微更紧凑,不需要在调用chain之前从列表中删除start。:-)
像这样打电话。:-)
^{pr2}$以下是一些评论:
while
i.startswith(initial)
只有当我以整个初始单词开头时才是真的。你可能不想要这个nations
是一个全局变量,这是错误的编辑
您的注释中描述的bug可能是因为您的递归调用在j循环中。复健性的呼唤可以消除民族的元素,这些元素也可能存在于首字母中。因此,您试图多次删除它们,这引发了一个异常。您可能是想把
chain(j)
放在循环之外(也许还要使用它的返回值?)在相关问题 更多 >
编程相关推荐