これはデータ構造とアルゴリズムのコースの問題であるため、特定の回答や完全な回答を求めているわけではありませんが、正しい道を進んでいるかどうかを確認するためのヒント (または正しい方向に向けることができるヒント) をいただければ幸いです。追跡）
ノードが場所で道路がエッジである場所の無向グラフが与えられた場合 (特定の道路を通過するのにかかる時間によって重み付けされます)、最大重みですべてのノードに到達できるポイント* の最小数を見つけますof 5. *ポイントはグラフ上の任意のポイントです。それらはエッジまたはノード上にあります。これからはクリティカルポイントと呼びます。
たとえば、次のグラフがあるとします。
ノード 1 -> ノード 3 (重み 1) -> ノード 2 (重み 7)
node2->node1(重み 7)->node4(w 1)->node7(w 8)
Node3->node1(1)->node4(2)->node5(2)->node6(2)
Node4->node2(1)->node3(2)->node5(2)
Node5->node3(2)->node4(2)->node7(3)
Node6->node3(2)->node7(5)
Node7->node6(5)->node5(3)->node2(8)
次に、クリティカル ポイントは次のようになります。ノード 1 と 2 の間のエッジに 1 つ、ノード 1 からの重みが 2 で、ノード 2 からの重みが 5 です (これらの合計は、ノード 1 から 2 への元の重みである 7 に等しくなければならないことに注意してください)。 )、2 つ目はノード 7 自体にあります。最初のクリティカル ポイントは、最大重み 5 でノード 1 ～ 6 に到達できます。このポイントから重み 5 ではノード 7 のみが到達不能のままであるため、2 番目のクリティカル ポイントはノード 7 自体にあります。したがって、グラフ全体は、重み 5 (またはそれ以下) でこれら 2 つの臨界点から到達可能です。
私の考え: 鼻ごとにブール値を "完了" しておき、既に見つかった重要なポイントの 1 つから到達できるかどうかを通知します。あるノードから開始します。BFS を使用してグラフをトラバースします。完了していないノードでは、次の操作を行います。
ノードの隣接リストを確認してください。重みが 10 を超えるエッジは無視します。これは、これらのエッジがつながるノードだけでなく、現在のノードにも到達するクリティカル ポイントを配置できないためです。「完了」ノードにつながるエッジを無視します。エッジが残っていない場合は、現在のノードと同じ場所の臨界点を臨界点のリストに追加します。それ以外の場合は、残りの最大ウェイト エッジを確認し、このエッジにクリティカル ポイントを作成します。クリティカル ポイントには 2 つのオプションがあります。curr_node から critical_point=5 まで、および critical_node から隣接ノード (エッジがつながるノード) までの重みは edgeWeight-5 です。または、crtical_point から隣接ノードへの重みは 5 で、curr_node から critical_point までの重みは edgeWeight-5 です。両方を試して、重み 5 でどの臨界点がより多くのノードに到達できるかを確認します。到達可能なノードが多い方を使用し、これらのノードを完了としてマークします。
ここでの問題は、有効性の証明です。各クリティカル ポイントには 2 つ以上のオプションがあり (最大の重みエッジを使用する場合)、私は 2 つだけを検討しています。最適化されました。さらに、ノードを囲むエッジに複数の臨界点を配置する必要がある場合があります。このアルゴリズムは 1 つだけ配置するか、何も配置せずに先に進みます。これは、複数配置すると必要以上に多くのポイントが配置される可能性があると想定したためです。
基本的に、ここからどこへ行くべきかよくわかりません。どんな助けでも本当に感謝しています。