2

ここでの奇妙な質問は、実際にはコードではなくロジックです。ここに投稿しても大丈夫です。

グラフと考えられるデータ構造を持っています。各ノードは多くのリンクをサポートできますが、各ノードの値に制限されます。すべてのリンクは双方向です。各リンクにはコストがかかります。コストは、ノード間のユークリッド差に依存します。各ノードの2つのパラメーターの最小値。およびグローバル修飾子。

グラフの最大コストを見つけたいです。

総当たり攻撃ではなく、そのような一致を見つけるための賢い方法があるかどうか疑問に思います...これは醜いです...そして私はそれを実行するのに700万年を費やさずにそれをどのように行うかさえわかりません。

明確にするために：

Global variable = T
many nodes N each have E,X,Y,L
L is the max number of links each node can have.
cost of link A,B = Sqrt(  min([a].e | [b].e)  ) x 
     ( 1 + Sqrt( sqrt(sqr([a].x-[b].x)+sqr([a].y-[b].y)))/75 + Sqrt(t)/10 )


total cost =sum all links.....and we wish to maximize this.

ノードの平均値は40〜50の範囲で、（20..600）平均ノードリンク係数は3の範囲0〜10です。

4

6 に答える 6

2

この記事を見る他の人のために完全を期すために、私はあなたのグラフ理論アルゴリズムを再考することを提案します：

  • ダイクストラ
  • 星
  • よく深い
  • 深さ/幅優先
  • 動的計画法でさえ（状況によっては）
  • 電気ショック療法。電気ショック療法。

どこかにあなたの問題の正しい解決策があります。最初にダイクストラを見ることをお勧めします。

これが誰かに役立つことを願っています。

于 2009-06-14T22:03:01.113 に答える
1

問題を正しく理解していれば、多項式の解はない可能性があります。したがって、次のアルゴリズムを実装します。

  1. benggreedyによる解決策を見つけてください。これを行うには、すべてのエッジをコストで並べ替えてから、最も高いものから始めて、可能な限りグラフにエッジを追加し、ノードがそれ以上のエッジを受け入れることができない場合はスキップします。
  2. エッジを見て、ヒューリスティックを使用してより高いコストをアーカイブするようにエッジを変更してみてください。最初に頭に浮かぶのは、ノードの4タプルすべて（A、B、C、D）を循環し、現在のグラフにエッジAB、CDがあり、AC、BDの方が良い場合は、変更を加えることです。
  3. オプションで、6タプル、または他の遺伝的アルゴリズムと同じもの（突然変異によって機能するため、そのように呼ばれます）。
于 2009-06-14T22:06:20.297 に答える
1

これは巡回セールスマン問題（したがってNP完全）と同等です。この問題を効率的に解決できれば、各コストをその逆数に置き換えるだけでTSPを解決できるからです。

これは、正確に解決できないことを意味します。一方、これは、私が言ったとおりに（各コストをその逆数に置き換えて）実行し、この問題に対して既知のTSP近似法のいずれかを使用できることを意味します。

于 2009-06-14T22:42:39.693 に答える
1

私には最大フロー問題のように思えます。

于 2009-06-14T22:45:41.747 に答える
0

任意の開始点から次に高価なオプションを貪欲に選択し（訪問したノードへのジャンプを省略）、すべてのノードが訪問されたら停止することは可能ですか？行き止まりになったら、行き止まりになっていない前の場所に戻り、貪欲に選択します。パスを維持するには、ある程度の作業とおそらくスタックのようなものが必要になります。コストが適切に整理され、マイナスでない場合、これは非常に効果的に機能すると思います。

于 2009-06-14T19:29:50.313 に答える
0

遺伝的アルゴリズムを使用します。それらは、あなたが述べた問題を迅速に解決し、時間の複雑さを軽減するように設計されています。選択した言語のAIライブラリを確認してください。

于 2009-06-14T19:34:00.053 に答える