メインコンテンツへスキップ
見出し画像

グラフ・最短経路・最適化――つながりと最善の選択を考える

    ここでのグラフは棒グラフではなく、点と線でつながりを表すものです。経路や作業順序を整理する基礎になります。

    グラフの用語

    正確な意味: グラフは頂点と辺からなる構造です。有向グラフは辺に向きがあり、無向グラフは向きを持ちません。重み付きグラフは辺などに距離や費用の値を付けたものです。

    道(経路)は辺をたどったつながり、閉路は出発点へ戻る経路です。無向グラフの次数は頂点に接続する辺の数です。有向では入次数と出次数を区別します。木は、連結で閉路のない無向グラフです。

    ざっくり言うと: 場所や状態を点、行き来や関係を線にした地図です。

    用途・問題での見方: 通信網、依存関係、道順を表します。矢印に逆らって進めるかを確認します。「最短」は辺の本数の最少か重みの合計の最少かを読み分けます。

    最短経路と動的計画法

    正確な意味: 最短経路問題は出発点と到着点の間の経路の費用などを最小にする問題です。ダイクストラ法は辺の重みが非負である場合の代表的な方法です。

    動的計画法は、問題を部分問題へ分け、その結果を保存・再利用して全体の解を求める方法です。状態とその更新式を設計します。

    ざっくり言うと: 小さな答えを使い回し、同じ計算を繰り返さない考え方です。

    用途・問題での見方: 経路や組合せ最適化などに使います。A→Bが2、B→Cが3、A→Cが8なら、A→B→Cの費用5の方が小さくなります。動的計画法では「いま必要な情報を状態に含めたか」を確認します。その場で一番よい選択だけをする貪欲法と常に同じ結果になるわけではありません。

    線形計画法

    正確な意味: 線形計画法は、線形な等式・不等式の制約の下で、線形な目的関数を最大化・最小化する方法です。変数が取り得る範囲を実行可能領域といいます。

    ざっくり言うと: 材料や時間の制約を守りながら、利益などを最善にする計算です。

    用途・問題での見方: 製品量や資源配分を考えます。目的関数と制約条件を分けて書きます。変数を整数に限るなら整数計画の条件が加わり、連続値の解を単に丸めてよいとは限りません。

    たとえばx、yを非負とし、x+y≦4、x≦2、y≦3の制約で3x+2yを最大にするなら、x=2、y=2で10になります。両製品とも単位利益が正なので使える総量4まで作り、その中で利益の高いxを上限2まで作る、と確認できます。

    PERTとクリティカルパス

    正確な意味: PERTは、作業の先行関係と所要時間をネットワークで整理し、計画を分析する手法です。クリティカルパスは、開始から完了までの所要時間を決める最長の経路です。

    ざっくり言うと: 同時にできる作業と、前の終了を待つ作業を見分けます。

    用途・問題での見方: Aの後にBとCが並行し、両方の後にDなら、全体はA+max(B,C)+Dです。Aが2日、Bが4日、Cが6日、Dが1日なら9日です。クリティカルパス上でない作業だけを短縮しても、全体が短くなるとは限りません。詳しい工程管理は後のマネジメント単元でも扱います。

    確認問題【オリジナル】

    作業Aが3日、その後にB(2日)とC(5日)が並行し、両方の完了後にD(4日)を行います。最短の完了日数はどれでしょうか。

    • ア:9日

    • イ:10日

    • ウ:12日

    • エ:14日

    正解と理由

    ウ:12日です。 3+max(2,5)+4=12です。アはCを待たずBだけを使った日数です。イは指定された先行関係を満たす計算ではありません。エはBとCを直列に足していて、並行できる条件を使っていません。経路A→C→Dが全体を決めます。

    参考資料と問題について

    学習範囲の確認:IPA「基本情報技術者試験 シラバス Ver.9.2」。本記事は独自の説明・例題です。

    確認問題と解説はオリジナルです。公開過去問の転載・改変問題ではありません。出題頻度は未集計です。

    前後の記事と学習目次

    前の記事:因数分解・微分・積分――式を整理し、変化と累積を見る

    次の記事:待ち行列とM/M/1――利用率が高いと待ち時間はどうなる?

    学習ノートの目次に戻る

    この記事が参加している募集

     
     
    ITの知識ゼロから、基本情報技術者試験の勉強を始めました📚 わからなかった言葉や問題を、自分の言葉でまとめる備忘録です。 基礎からコツコツ学んで、いつかは応用情報にも挑戦したいです! 一緒に学んでいただけたらうれしいです🌱

    あなたへのおすすめ