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

私も再帰下降に行きました。リストは変更されるため、動的計画法がこれに適しているかどうかはわかりません。少しコンパクトになり、チェーンを呼び出す前にリストから削除を開始する必要はありません。:-)

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 に答える
5

ここにいくつかのコメントがあります：

  • パスを返したい。注文されたコレクションですね。セットは順序付けされていないため、おそらく res にセットを使用しないでください。
  • 長さまたは返されたパスを知っていますか？いいえ、ありません。whileだからあなたはどこかが必要かもしれません
  • i.startswith(initial)i が最初の単語全体で始まる場合にのみ真です。あなたはおそらくこれを望んでいません
  • 再帰的なアプローチを使用しようとしています。ただし、結果は収集しません。再帰呼び出しは今のところ役に立たない
  • nationsグローバル変数です。これは悪いことです

編集

コメントで説明されているバグは、再帰呼び出しが j ループ内にあるために発生する可能性があります。再帰呼び出しは、イニシャルにも存在する可能性のある国の要素を削除する場合があります。したがって、それらを複数回削除しようとすると、例外が発生します。あなたはおそらくchain(j)ループの外に置くつもりです（そしておそらくその戻り値を使用しますか？）

于 2012-05-11T09:32:03.100 に答える
2

補足として、あなたの問題はNP完全です（つまり、「高速な」多項式時間の解がないことを意味します）。小さな問題サイズでは解決できますが、すぐに非常に難しくなります。

あなたの問題は、有向グラフの最長経路問題と考えることができます。

  • 各単語 (国) を頂点として有向グラフを描画します。
  • と のすべてのペアについて、 の最後の文字が の最初の文字と同じである場合、w1辺をw2描きます。w1 -> w2w1w2
  • s の最後の文字がs の最初の文字と同じw2->w1場合は、逆のエッジも描画します。w2w1
  • 最大長のパス(最も多くの頂点を含む単純なパス) を見つけます。(この場合の「シンプル」とは、「頂点を複数回含まない」ことを意味します。)

果物と野菜のリストのグラフの例を次に示しますApple, banana, eggplant, kiwifruit, orange, oregano, tangerine, zucchini。

Word 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 に答える