6

我有一个国家列表，我想拥有最长的国家路径，其中每个选择的国家必须以结束前一个元素的相同字母开头

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']

我试过这种方式，但它不起作用

def chain(naz):
    initial = naz[-1]
    initials=[]
    res = set()
    res.add(naz)
    for i in nations:
        if i.startswith(initial):
            initials.append(i)
    for j in initials:
        nations.remove(j)
        res.add(j)
        chain(j)
    return res

有什么建议吗？

4

4 回答 4

5

以下是一些评论：

  • 您希望返回路径。所以这是一个有序的集合，不是吗？您可能不应该将集合用于 res，因为集合是无序的
  • 你知道 la 长度或返回的路径吗？不，你没有。所以你可能需要一个while地方
  • i.startswith(initial)仅当 i 以整个初始单词开头时才为真。你可能不想要这个
  • 您尝试使用递归方法。但是，您不收集结果。递归调用暂时没用
  • nations是一个全局变量，这很糟糕

编辑

您的评论中描述的错误可能会发生，因为您的递归调用在 j 循环内。递归调用可能会删除国家的元素，这些元素也可能存在于首字母中。因此，您尝试多次删除它们，这会引发异常。您可能的意思是放在chain(j)循环之外（也许使用它的返回值？）

于 2012-05-11T09:32:03.100 回答
5

我也进行了递归下降。不确定动态编程是否适合这个，因为我们会修改列表。稍微紧凑，在调用链之前不需要从列表中删除开始。:-)

def chain(start, countries):
    remaining = list(countries)
    del remaining[remaining.index(start)]
    possibles = [x for x in remaining if x[:1] == start[-1:]]
    maxchain = []
    for c in possibles:
        l = chain(c, remaining)
        if len(l) > len(maxchain):
            maxchain = l
    return [start] + maxchain

像这样打电话。:-)

>>> chain('spain', nations)
['spain', 'netherlands', 'serbia', 'albania', 'andorra', 'austria']
于 2012-05-11T10:25:42.280 回答
2

作为旁注，您的问题是 NP 完全的（这意味着它没有“快速”多项式时间解决方案。）它可以解决小问题，但很快就会变得非常困难。

您的问题可以被认为是有向图上的最长路径问题。

  • 绘制一个有向图，每个单词（国家）表示为一个顶点。
  • 对于每对单词w1和，如果 的最后一个字母与的第一个字母相同，则w2画一条边。w1 -> w2w1w2
  • w2->w1如果w2s 的最后一个字母与 s 的第一个字母相同，则还要绘制反向边缘w1。
  • 找到最大长度路径- 包含最多顶点数的简单路径。（在这种情况下，“简单”表示“不包括任何顶点不止一次。”）

这是水果和蔬菜列表的示例图：Apple, banana, eggplant, kiwifruit, orange, oregano, tangerine, zucchini。

词 DAG 示例

此图可能包含循环（例如，此图有一个循环eggplant -> tangerine -> eggplant -> tangerine....。包含循环的有向图的最长路径问题是 NP 完全的。因此，此问题没有多项式时间解决方案。

这并不意味着你不能比蛮力做得更好。有一种动态规划算法可以将复杂性从O(n!)（阶乘，非常糟糕）降低到O(n^2 * 2^n)（超指数，仍然很糟糕，但比阶乘更好。）

于 2012-05-14T01:34:47.367 回答
1

这是一种天真的递归方法......我觉得你可以使用动态编程，它会更好

def chain(start,options):
    #start is the starting word
    #options are the words left

    next_options = [country for country in options if country[0] == start[-1]]

    #if theres no options, return the single
    if not next_options:
        return [start]

    #otherwise, return best chain out of the next option
    best_chain = None
    longest_chain = 0

    for option in next_options:

        new_options = options[:]
        new_options.remove(option)

        possible_chain = chain(option,new_options)

        if len(possible_chain) > longest_chain:
            best_chain = possible_chain
            longest_chain = len(possible_chain)

    return [start] + best_chain
于 2012-05-11T10:07:18.783 回答