グラフと制約の一致

Question

私はこの問題を抱えていますが、私は効果的な解決策を見ていませんが、強引なアプローチをとっています。誰も私に手を貸してもらえますか？

この問題は、グラフG =（V、E）が方向付けられ、重み付けされ、非周期的であることからなる。エッジは重みw（u、v）を有する。 （u、x）と（u、y）が存在する場合、w（u、v）の値は原点（w（u、x）= w（u、y）にのみ依存します。もともと、各頂点は、複数の着信エッジおよび/または発信エッジを有することができる。目標は、残りの合計重量が最大になるように、最大​​で頂点ごとに1つの出て行くエッジを維持することです。出て行くエッジがある頂点には、入って来るものがにありません。たとえば、図1を考えてみましょう。左側のグラフは元のグラフです。最大1つの出側エッジを維持すると、右側のグラフは、最大総重量の解を表す。01

しかし、この問題にはもう一つの制約がある。各頂点には2つの値（capacityとload）が割り当てられます。容量は、どれくらいの負荷がかかるかを示します。最大総重量構成を見いだす際には、容量も考慮する必要があります。図2は図1と同じグラフを示していますが、容量の制約が決定的な役割を果たします。この状況では、最大総重量設定が異なることを確認してください（右側のグラフ、図2）。要約する

、最大総重量得るために3つの制限がある：

1. オベイ容量制限は、
2. 出力エッジのある頂点には入力エッジがありません。
3. 頂点は最大で1つの出力エッジを持ちます。

私が思いついた唯一の解決策は、すべての可能な構成をテストし、有効であり、最大値を追跡しているかどうかを確認することです。誰もがこの問題に取り組むためのより良いアプローチを持っていますか？

Answer 1

あなたの問題は、私にはknapsack問題のようになります。利益を最大化するために、エッジのセットを拾います。

確かにできることは、constraint satisfactionアプローチを使用していることです。たとえば、ナップザックの問題を解決するthis codeをチェックします。あなたのニーズに合わせることは、むしろ単純な作業でなければなりません。

このアプローチでは、一致するアルゴリズムは必要ありません。解決手順を使用すると、可能な限り最良のソリューションが直接作成されます。しかし、大きなグラフ（数千のエッジ/ノード）では時間/メモリに時間がかかることがあります。