1

私はこれに数日間取り組んできましたが、成功しませんでした。基本的に、2D マトリックスに配置された多数のノードがあります。各ノードには、それぞれ 3 つと 2 つの隣接ノードがある行列の側面とコーナーのノードを除いて、4 つの隣接ノードがあります。長方形の領域に並べて配置された正方形のカードの束を想像してみてください。このプロジェクトは、実際には一種のカード/ボード ゲームをシミュレートしています。

各ノードは、その周囲のノードに接続されている場合と接続されていない場合があります。各ノードには関数 (get_connections()) があり、接続されているノードのすぐ周囲のノードを返します (つまり、0 ～ 4 個のノードが返されます)。各ノードには、ボード マトリックス上の位置を含む "index" プロパティもあります (例: '1, 4' -> 行 1、列 4)。私がやろうとしているのは、特定の「開始」ノードを指定して、接続されたノードの最長の非反復パスを見つけることです。

私がやろうとしていることの良いアイデアを与えるはずのいくつかの画像をアップロードしました：

www.necessarygames.com/junk/10-days-problem-01.jpg
(ソース: requiredgames.com )

www.necessarygames.com/junk/10-days-problem-02.jpg
(ソース: requiredgames.com )

両方の画像で、強調表示された赤いカードは、おそらく左上のカードを含む接続されたカードの最長パスです。ただし、両方の画像で、パスにあるはずのカードがいくつか除外されていることがわかります (最初の画像ではルーマニアとマルドバ、2 番目の画像ではギリシャとトルコ)。

開始ノード/カードを指定して、最長パスを見つけるために現在使用している再帰関数を次に示します。

def get_longest_trip(self, board, processed_connections = list(), 
                     processed_countries = list()):
    #Append this country to the processed countries list,
    #so we don't re-double over it
    processed_countries.append(self)
    possible_trips = dict()
    if self.get_connections(board):
        for i, card in enumerate(self.get_connections(board)):
            if card not in processed_countries:
                processed_connections.append((self, card))
                possible_trips[i] = card.get_longest_trip(board, 
                                                          processed_connections, 
                                                          processed_countries)
        if possible_trips:       
            longest_trip = []
            for i, trip in possible_trips.iteritems(): 
                trip_length = len(trip)
                if trip_length > len(longest_trip):
                    longest_trip = trip
            longest_trip.append(self)         
            return longest_trip
        else:
            print
            card_list = []
            card_list.append(self)
            return card_list
    else:
        #If no connections from start_card, just return the start card 
        #as the longest trip
        card_list = []
        card_list.append(board.start_card)
        return card_list

ここでの問題は、processed_countries リストと関係があります。私の最初のスクリーンショットを見ると、何が起こったかがわかります。ウクライナがやってきたとき、最長経路 (マルドバ-ルーマニア、またはトルコ) の 2 つの可能な選択肢を調べたことです。 、ブルガリア) は、両者が同等であることを確認し、無差別に一方を選択しました。ハンガリーがやってきたとき、ウクライナによってルーマニアがprocessed_countriesリストに追加されているため、ルーマニアを通るパスを作成しようとすることはできません（実際には最長のパスがあります）.

これに関するヘルプは非常に高く評価されています。再帰的であろうとなかろうと、これに対する解決策を見つけていただければ、喜んで $$ を寄付させていただきます。

完全なソース コード (Python 2.6、Pygame 1.9 が必要) を次の場所にアップロードしました。

http://www.necessarygames.com/junk/planes_trains.zip

関連するコードは src/main.py にあり、すべて実行するように設定されています。

4

3 に答える 3

6

サイクルを含むグラフの最長経路問題が NP 困難であることをご存知ですか?

于 2010-03-22T20:26:09.607 に答える
2

...ウクライナによって、ルーマニアがprocessed_countriesリストに追加されました。

グラフ パスごとに個別のprocessed_countriesリストを使用します。彼らは、1 つのコード例は千の言葉に値すると言うので、コードを少し変更しました (未テスト):

def get_longest_trip(self, board, processed_countries = list()):
    # see https://stackoverflow.com/questions/576988/python-specific-antipatterns-and-bad-practices/577198#577198
    processed_countries = list(processed_countries)
    processed_countries.append(self)

    longest_trip = list()
    if self.get_connections(board):
        possible_trips = list()
        for card in self.get_connections(board):
            if card not in processed_countries:
                possible_trips.append(card.get_longest_trip(board, 
                                                            processed_countries))
        if possible_trips:
            longest_trip = max(possible_trips, key=len)
            longest_trip.append(self)

    if not longest_trip:
        longest_trip.append(self)
    return longest_trip

無関係な事項:

Traceback (most recent call last):
  File "main.py", line 1171, in <module>
    main()
  File "main.py", line 1162, in main
    interface = Interface(continent, screen, ev_manager)    
  File "main.py", line 72, in __init__
    self.deck = Deck(ev_manager, continent)
  File "main.py", line 125, in __init__
    self.rebuild(continent)  
  File "main.py", line 148, in rebuild
    self.stack.append(CountryCard(country, self.ev_manager))
  File "main.py", line 1093, in __init__
    Card.__init__(self, COUNTRY, country.name, country.image, country.color, ev_manager)  
  File "main.py", line 693, in __init__
    self.set_text(text)
  File "main.py", line 721, in set_text
    self.rendered_text = self.render_text_rec(text)  
  File "main.py", line 817, in render_text_rec
    return render_textrect(text, self.font, text_rect, self.text_color, self.text_bgcolor, 1)       
  File "/home/vasi/Desktop/Planes and Trains/src/textrect.py", line 47, in render_textrect
    raise TextRectException, "The word " + word + " is too long to fit in the rect passed."
textrect.TextRectException: The word Montenegro is too long to fit in the rect passed.

ソース パッケージには 16 個の異なるbakファイルがあります。16。十六。それについて考えて、バージョン管理を使い始めてください。

于 2010-03-22T21:27:17.700 に答える
0

力ずくの方法:

  1. 深さ優先連結リストを作成します。リスト L とその長さ T を格納します。

  2. このリストの各接続について:

    • ダイアグラム全体をプッシュ
    • 接続を削除します。
    • 深さ優先連結リストを作成します。
    • list が T よりも長い場合: T を length に設定し、list を L に設定してから、再帰呼び出し 2 を実行します。
    • 図全体をポップします。
    • 戻る

これにより、これらのノードを接続するすべての可能な方法のフラッド フィル スタイル ソリューションが作成されます。

于 2010-03-22T20:16:24.663 に答える