マッチングアルゴリズム

Question

ここで奇妙な質問は本当にコードではありませんが、ロジックは、ここに投稿するようにしてください。

私はグラフと考えることができるデータ構造を持っています。 各ノードは多数のリンクをサポートできますが、各ノードの値に制限されています。 すべてのリンクは双方向です。各リンクにはコストがあります。コストは各ノードの2つのパラメータの最小値であるノード間の真理値の差に依存する。グローバルモディファイア。

私はグラフの最大コストを求めています。

このような一致を見つけるための巧妙な方法があれば、ブルートフォースではなく...醜い...と私はどのように私は700万を費やすことなくそれを行うだろうか分からないそれを実行する年。明確にするため

：因子を連結

ノードの平均値40~50であるが（20..600）の範囲とすることができる

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. 

平均ノードは3範囲0-10です。

Answer 1

私が問題を正しく理解していれば、おそらく多項式の解はありません。したがって、私は次のアルゴリズムを実装します：

1. は貪欲をベンことで、いくつかの解決策を探します。これを行うには、すべてのエッジをコスト別に並べ替え、可能な限りエッジをグラフに追加し、ノードがより多くのエッジを受け入れることができない場合はスキップします。
2. ヒューリスティックを使用してエッジを見て、より高いコストをアーカイブするように変更してください。あなたの現在のグラフにAB、CD、AC、BDの方が良いならば、あなたは変更を行います。
3. 任意に6タプル、または遺伝的アルゴリズム（これらは突然変異によって機能するため、そのように呼ばれます）と同じものです。

Answer 2

任意の開始ポイント（訪問先ノードへのジャンプを省略）から次の最も高価なオプションを貪欲に選択し、すべてのノードにアクセスしたら停止することは可能ですか？もしあなたが行き止まりに戻って、あなたが行き詰まっていない前の場所に戻って、貪欲に選択したら、あなたのパスを維持するためには、何らかの仕事や多分スタックのようなものが必要になるでしょう。コストが整っていて負ではないとすれば、これはかなり効果的です。

Answer 3

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

Answer 4

この記事を見て誰のための完全を期すために、私はあなたのグラフ理論のアルゴリズムを見直すことをお勧めは：

• ダイクストラ
• ASTAR
• 貪欲深さ/幅優先
• 動的プログラミング（場合によっては）
• ect。 ect。

あなたの問題の解決策があります。まず、ダイクストラを見ることをお勧めします。

私はこれが誰かを助けてくれることを願っています。

Answer 5

これは、この問題を効率的に解決できれば、各コストをその逆数で置き換えるだけでTSPを解くことができるので、トラベルセールスマンの問題（したがってNP-Complete）に相当します。

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

Answer 6

私にはmax flow problemのようです。