アポイントメントスケジューリングアルゴリズム（N人の空き時間スロットを持つN人、制約充足）に似た何かをしたいです。しかし、私の追加の要件は、2 番目の最適解、3 番目の最適解などを与えることができることです。パフォーマンスに悪影響を与えることなくこれを達成することは可能ですか?
1 に答える
1
ほとんどの場合、可能な限り効率的なソリューションを見つけることに関心があるだけなので、最も最適なものから順番にソリューションを見つけるための多くの研究は (私の知る限り) ありません。というわけで、これ以上の解決策が出てこないことを前提に、この解決策を提示します。
最も効率的な解決策を見つけるには、リンクされた質問で承認された回答を使用してください。便宜上、ここにコピーします。
2 部グラフで最大一致を見つけます (頂点の 1 つのセットは人のセットであり、もう 1 つはスロットのセットです。その人がこのスロットに利用できる場合、人とスロットの間にエッジがあります)。
この問題は Hopcroft-Karp アルゴリズムで解決できます。
最悪の場合の複雑さ、グラフがまばらな場合はより良い。
O(n5/2)
次に、入力グラフから出力の各エッジを削除して、アルゴリズムを再度実行してみてください。
これらの実行の 1 つにより、2 番目に最適な結果が得られるはずです。
今度は、2 番目に最適なグラフから出力の各エッジを削除して、アルゴリズムを再度実行してみてください。
これで、生成されたセットの中で 3 番目に最適なものになるはずです。
同様に、3 番目に最適なグラフのエッジを削除してみてください。
等々。
複雑：
O(n5/2)最悪の場合の最適解。
O(n7/2)( ) 生成される次のソリューションごとに最悪の場合。O(n.n5/2)
例：
エッジがあるとしますa,b,c,d,e,f,g。
最大一致が であるとしましょうa,b,c。
aここで、入力グラフから削除して を取得しb,c,d,e,f,gます。
このグラフの最大一致が であるとしましょうc,d,e。
bここで、入力グラフから削除して を取得しa,c,d,e,f,gます。
このグラフの最大一致が であるとしましょうa,d,e。
cここで、入力グラフから削除して を取得しa,b,d,e,f,gます。
このグラフの最大一致が であるとしましょうa,b,g。
c,d,e、a,d,eまたはのいずれかa,b,gが 2 番目に最適になります (それが であるとしましょうa,b,g)。
a次に、b、 、gからを削除してa,b,d,e,f,g、これら 3 つのグラフのそれぞれの最大一致を取得してみてください。
これらの 5 つのセット (2 番目に最適なセットを除く 6 つの生成されたセット) の 1 つが 3 番目に最適なセットになるはずです。
等々。
証拠：
もう少し考えないといけないですね…。
ノート：
たとえばa,b,c,d,e、最大一致が のエッジがあるとしa,b,cます。
削除して最大一致としてa取得します。c,d,e
削除して最大一致としてb取得します。c,d,e
これら 2 つは同一であるため、一方を 2 番目に最適なものとして、もう一方を 3 番目に最適なものとして使用しないでください。
c両方を維持する必要がありますが、 、dおよびeの両方から生成されたグラフを確認する必要がありb,c,d,eますa,c,d,e。
c,d,eが次に最適な場合は、両方から削除されたすべてのエッジをチェックする必要があるため、これは実行時間に少し悪影響を与える可能性があります。
于 2013-11-04T06:51:24.310 に答える