アルゴリズム、ネットワーク、線形計画法
導入済み| English | 意味 |
|---|---|
| minimum spanning tree/ˈmɪnɪməm ˈspænɪŋ triː/ | 最小生成木 |
最安ネットワークか最短ルートか？
- 学校はケーブルで建物を接続しなければならない。2つの建物の間の最短ルートと、最も安価な全体ネットワークは異なる問題である。
- この授業では最小スパニングツリーを学ぶ: 全頂点を連結させ、総辺重みが最小となる無循環ネットワークである。
数学的構造を選択せよ
- クルスカル法は重みを増大する順に辺を選択しながら循環を避ける。ダイクストラ法は始点からの最短暫定距離を更新する。線形計画法は許容領域内で線形目的関数を最適化し、必要に応じて頂点と整数制約を確認する。
- 計算する前に許容される入力と単位を明記すること。数式は単なる電卓の入力記録ではなく、関係性を表すべきである。
クルスカル法と最短路アルゴリズムは、例題ネットワーク上でともに総重み6を出力した。それにもかかわらず両者が置き換え可能ではないのはなぜか。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
目的が異なる: 最小スパニングツリーはすべての頂点を結ぶ(n-1本のエッジ、ループなし)のに対し、最短路は単一の始点から終点への経路を最適化する。ここでは答えが等しいのは偶然に過ぎない。
検証済みケースを解く
- 結果を初期の数量と比較して確認する。適切な場合、元の関係式に代入するか、グラフと数値解答を比較する。
頂点 A, B, C, D および辺 AB=2, BC=3, AC=4, CD=1, BD=5 において、クルスカル法は CD, AB, BC を選択して合計6とする。A から D への最短経路は A-B-C-D で、これも6であるが、この等号は偶然の一致に過ぎない。3x+2y を最大化し、x+y≤4, x≤2, x,y≥0: 最良の頂点は (2,2)、値は10である。
アルゴリズム、ネットワーク、線形計画法
クルスカル法は Cycle を避けながら、重みの小さい順に辺を選択する。
モデルと解答例を比較し、1つの違いを説明せよ。
例示されたネットワークにおける最小 spanning tree の重さを求めよ。
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
クルスカル法は、 Cycle を形成しない重み 1,2,3 の辺を選び、すべての頂点を接続する：合計 6。
魅力的な近道を検証せよ
- スパニングツリーには循環がなく、全頂点を連結させる。最大単一辺がすべての最適解から自動的に除外されるわけではない。最短経路アルゴリズムは最小スパニングツリーアルゴリズムを置き換えることができない。
- 近道が機能しない場合は、それが破られる仮定を特定すること。要求された最終的な四捨五入まで正確な値を維持すること。
2つの頂点間の最短経路は、必ずしも全体ネットワークの最小スパニングツリーであるとは限らない。この主張は誤りである。どの定義や仮定に違反しているかを説明せよ。
例題の許容領域において、3x+2y の最大値を求めよ。
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
許容頂点を確認する：(2,2) は 3×2+2×2=10 を与え、これが最大の目的関数値である。
2 つの頂点間の最短経路は、必ずしもネットワーク全体の最小木（minimum spanning tree）とはならない。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
木（spanning tree）は Cycle を持たず、すべての頂点を接続する。最も長い単一の辺が自動的に最適解から除外されるわけではない。最短経路アルゴリズムは最小木アルゴリズムを置き換えることはできない。
新しい状況を読み解く
- クリティカルパスについては、最早発時刻と最遅着時刻を計算し、スラックゼロの作業を特定する。単位を明記し、最適解を解釈せよ。既存アーカイブに D1 ペアがないため、これらのオリジナルタスクは確認済みの D1 過去問バンクを確立しない。
- 完全な解答は数学的な結果を示し、その意味を説明する。指定された文脈内で可能であることを確認すること。
4 個の頂点を持つ木（spanning tree）には何本の辺があるか？
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
n 個の頂点を持つ木には n-1 本の辺があり、4 個の頂点には 3 本必要である。
各アルゴリズムに対応するルールをセットにしてください。
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
各アルゴリズムはそれぞれの問題クラスに対して厳密です。指定されたルール（同点時の処理を含む）をトレースすることで得点が与えられます。
コースでこれを使用する
- edexcel IAL数学；公式単元D1。他単元の enrichment（補強）は範囲確認で特定されていますが、追加の必修要件ではありません。
- 最終的な答えの前に手法を示し、試験用紙の電卓および数式ルールを使用すること。誤答については、最初に無効となったステップを特定して見直すこと。
全頂点を連結させ、総辺重みが最小となる無循環ネットワーク。関係を選択し、手法を示し、仮定を確認し、結果を解釈せよ。