1

Java を使用してグラフの色付けプロジェクトに取り組んでいます。四色定理を使用して、4 つの異なるグラフ色付けアルゴリズムを実装する必要があります。少数の隣人貪欲アルゴリズムという名前のアルゴリズムの 1 つに問題があります。

多数のポリゴン オブジェクト (arraylist に格納されている) を含むマップがあります。また、さまざまなポリゴンの隣接関係を表す 2D ブール配列があります。

私はアルゴリズムを理論的に知っています。色付けされていないポリゴンを格納するプライオリティ キューがあります。隣接数に基づくキューの順序。隣接するポリゴンが少ない場合、隣接するポリゴンが多いポリゴンよりも優れていると見なされます。いずれにせよ、アルゴリズムは優先度キューからポリゴンを繰り返し描画し、隣接関係に基づいて色付けを試みる必要があります。

残念ながら、実装部分に問題があります。隣接数に基づいてプライオリティ キューを取得しましたが、それらのポリゴンに色を割り当てる際に問題が発生しました。その種のアルゴリズムに取り組んだ人、またはアイデアを持っている人がいる場合は、私と共有してください. 実装部分を高速化するためのアイデアが必要です。

前もって感謝します。

4

2 に答える 2

2

最初に最低度のノードに色を付けようとしているように聞こえます。それは逆に思えます。最初に最高度のノードに色を付ける必要があります。たとえば、次数 3 のノードは、選択できる色が 4 つある場合、常に色付け可能です。

グラフが 4 色可能であっても、貪欲なアルゴリズムは 4 色を見つけられない可能性が非常に高いことを認識しています。

ウィキペディアのページで役立つヒントを確認してください。

于 2010-12-11T03:48:11.793 に答える
2

実装部分でどのような支援が必要かを正確に述べる必要があります。「色を割り当てるときに問題があります」どのように?

隣接関係の別の 2D ブール配列を持つ配列リストに格納された Polygon オブジェクトを含むマップが入力ですか? ポリゴンはグラフのノードであると想定しています。

おそらく、Graph データ構造を構築してナビゲートする必要があります。古典的な C スタイルのアプローチでは、ノードとエッジに配列を使用し、見た目を複雑にしています。

コンポジションを使用する OOPは自然にオブジェクトのグラフを生成するため、ここで使用するのに適したアプローチです。

グラフは基本的に、ノードとエッジの 2 つの要素で構成されます。

Node クラスから始めます。これには、色、ID、および Edge の ArrayList があります。エッジは 2 つのノード間の関係を形成し、重みと方向を持つ場合があります。

入力からノードとエッジを作成します (新しいノードが存在しない場合は作成してください)。次に、マークされていないノードを選択して最近傍アルゴリズムを実行します (これには静的メソッドが適している場合があります。または、実際に実践して戦略パターンを実装することもできます)。

ただし、サイクルに注意してください。

于 2010-12-11T03:36:57.277 に答える