n 個の頂点を持つ完全なグラフがあるとします。各頂点には値があります。2 つの頂点 i と j の間のエッジの重みは、value[i] xor value[j] に等しくなります。
問題は、頂点 1 から頂点 n までのパスで、パス内のエッジの重みの最大値が最小になるパスを見つけることです。私はすでにダイクストラのアルゴリズムを修正し、O(n ^ 2 lg(n)) のアルゴリズムを見つけました。誰かがより効率的なアルゴリズムを見つけるのを手伝ってくれますか?
質問する
2070 次
1 に答える
1
ボトルネックの最小値は、この値の最上位ビット ( M) によって決定される数よりも小さくすることはできません: value[1] XOR value[n]。ノード と の2 つのノードAとが見つかった場合B、との間のエッジの重みが最小で、ノードとの上位ビットが等しくM、ノード1との上位ビットが等しい場合、最小のボトルネック パスは 1-ABn になります (またはA=1 および/または B=n の場合は短くなります)。AMnBAB
A/Bエッジの重みが最小のペアを選択するには、 nodeMと一致する上位ビット (およびそれ以上) を持つすべてのノード値のバイナリ トライを作成します1。次に、上位ビットが node と一致するすべてのノード値nについて、このトライでこれらの値を検索してみてください。完全一致が見つからない場合は、最も深い部分一致を選択します。
時間計算量は O(n * M) です。
于 2013-06-29T10:13:21.073 に答える