データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也

さまざまな問題とアルゴリズム 離散最適化問題 グラフ問題 巡回セールスマン問題 最大クリーク問題 グラフ分割問題 最短経路問題 ハミルトン閉路問題 最大マッチング問題

最短経路問題 出発地から目的地までの最短の経路を求める． 駅すぱあと カーナビゲーション http://www.me.sophia.ac.jp/or/lab/ishizuka/OC/spath_01.html

最短経路問題の定義 問題の定義： 重みつきグラフの2頂点が与えられたとき，その2点を結ぶ重み和最小の経路を求めよ． 2 2 2 3 1 1 4 2 3 2 1 3

ダイクストラのアルゴリズム（1） 近い頂点から順番に，最短経路と最短距離を求めていく． 頂点毎のデータ： 各時点での最短距離，確定か否か 辺毎のデータ： 最短経路に含まれるか否か 出発頂点までの最短距離を0とし確定にする 2 2 2 3 1 1 2 4 2 3 2 1 3

ダイクストラのアルゴリズム（2） 確定した頂点の隣接頂点までの仮の最短距離を計算 最も仮の最短距離が短い頂点を確定，最短経路も確定 2 2 3 1 1 2 1 4 2 3 2 1 3 3 2 2 2 2 3 1 1 2 1 1 4 2 3 2 1 3 3

ダイクストラのアルゴリズム（3） 確定した頂点の隣接頂点までの仮の最短距離を計算 最も仮の最短距離が短い頂点を確定，最短経路も確定 2 2 1 1 2 1 4 2 3 2 1 3 5 3 2 2 2 3 2 2 3 1 1 2 1 4 2 3 2 1 3 5 3

ダイクストラのアルゴリズム（4） 確定した頂点の隣接頂点までの仮の最短距離を計算 最も仮の最短距離が短い頂点を確定，最短経路も確定 2 2 3 2 2 3 1 1 2 1 4 2 3 2 1 3 5 4 3 2 2 2 3 2 2 3 1 1 2 1 4 2 3 2 1 3 3 4 3

ダイクストラのアルゴリズム（5） 確定した頂点の隣接頂点までの仮の最短距離を計算 最も仮の最短距離が短い頂点を確定，最短経路も確定 2 2 3 2 2 3 1 1 2 1 4 5 2 3 2 1 3 3 4 5 3 2 2 2 3 3 2 2 3 1 1 2 1 4 5 2 3 2 1 3 3 4 3

ダイクストラのアルゴリズム（6） 確定した頂点の隣接頂点までの仮の最短距離を計算 最も仮の最短距離が短い頂点を確定，最短経路も確定 2 2 3 3 2 2 3 1 1 2 1 4 5 6 2 3 2 1 3 3 5 4 3 2 2 2 3 3 2 2 3 1 1 2 1 4 5 6 2 3 2 1 3 3 4 3

ダイクストラのアルゴリズム（7） 確定した頂点の隣接頂点までの仮の最短距離を計算 最も仮の最短距離が短い頂点を確定，最短経路も確定 2 2 3 3 2 2 3 1 1 2 1 4 5 5 2 3 2 1 3 3 5 4 3 2 2 2 3 3 2 2 3 1 1 2 1 4 5 5 2 3 2 1 3 3 4 3

ダイクストラのアルゴリズムの 最悪時間計算量 頂点の数を n とする． 最悪時間計算量 頂点を確定する回数 → 最悪 n 一回の確定当たりの計算： 隣接頂点の数 → 最悪 n 仮の最短距離最小の頂点の探索 → 最悪 n 最悪時間計算量は，O(n2) （nの多項式である!!） 2 2 2 3 3 2 2 3 1 1 2 1 4 5 5 2 3 2 1 3 3 4 3

ハミルトン閉路問題 与えられたグラフが，全頂点をちょうど1回だけ通過する閉路（ハミルトン閉路）を持つか否かを判定せよ． →持つ →持たない

ハミルトン閉路問題の解法（1） 適当な順番で頂点が番号付けられているとする． ハミルトン閉路は頂点の置換（並び替え）で表現できる． （以下の例では，<1,4,5,8,3,2,7,6>） 頂点数をnとしたとき，可能な置換の総数は，n! すべての置換がハミルトン閉路になるわけではない． 例： <1,2,3,4,5,6,7,8> 1 2 7 8 3 6 4 5

ハミルトン閉路問題の解法（2） ハミルトン閉路問題の総当り探索アルゴリズム： n!通りの頂点の置換を列挙 各置換がハミルトン閉路を成しているか否かを判定 1つでもハミルトン閉路を成す置換があれば Yes を出力して終了，すべて調べて見つからなければ No を出力 <1,2,3,4,5,6,7,8> → × <1,2,3,4,5,6,8,7> → × <1,2,3,4,5,7,6,8> → × <1,2,3,4,5,7,8,6> → × <1,2,3,4,5,8,6,7> → × <1,2,3,4,5,8,7,6> → × <1,2,3,4,6,5,7,8> → × : 1 2 7 8 3 6 4 5

ハミルトン閉路問題の解法（3） 総当り探索アルゴリズムの最悪時間計算量： ハミルトン閉路問題を多項式時間で解くアルゴリズムは知られていない． 与えられた置換がハミルトン閉路を成しているか否かの判定： O(n) 置換の総数： n!個 最悪時間計算量： O(n!) × O(n) = O(2n) (指数時間であることに注意!) ハミルトン閉路問題を多項式時間で解くアルゴリズムは知られていない．

巡回セールスマン問題 全都市を最短の 道のりで巡回してくる 商品の配送計画など スウェーデンの24,978都市に ついて解いたもの （Xeron 2.8GHz dual CPU×96， 84.8 CPU years） http://www.tsp.gatech.edu/

巡回セールスマン問題の定義 問題の定義： 重みつき完全グラフが与えられたとき，重み和最小のハミルトン閉路を求めよ． （完全グラフ：すべての頂点間に辺が存在しているグラフ） （決定問題版）巡回セールスマン問題： 重み和が k 以下のハミルトン閉路が存在するか否か？ 3 2 3 1 2 3 2 2 2 1 →重み和8

巡回セールスマン問題の解法 ハミルトン閉路問題同様，全頂点置換を総当り． 総当り探索アルゴリズムの最悪時間計算量： 与えられた置換が長さ k 以下のハミルトン閉路を成しているか否かの判定： O(n) 置換の総数： n!個 最悪時間計算量： O(n!) × O(n) = O(2n) 巡回セールスマン問題を多項式時間で解くアルゴリズムは知られていない．

問題のクラス 多項式時間問題（クラスP） 非決定性多項式時間問題（クラスNP） 多項式時間で解くアルゴリズムが知られている問題 最短経路問題など… ほとんどの実用的な問題はここに入る 非決定性多項式時間問題（クラスNP） 解の候補が与えられた時に，それが解となっているか否かを多項式時間で判定できる問題 ハミルトン閉路問題，巡回セールスマン問題など 一般に，解くのに指数時間かかる 「手に負えない」問題とも言われる

P≠NP予想 クラスPとクラスNPは一致するか否かは未解決問題． （P≠NP予想，またはP=NP問題という） NP完全問題： 恐らく，情報科学分野で一番難しい問題． ミレニアム懸賞問題の1つ． （アメリカのクレイ数学研究所によって2000年に発表され数学の7つの未解決問題，100万ドルの懸賞金） NP完全問題： NPの中で一番難しい問題． ハミルトン閉路問題，決定問題版巡回セールスマン問題は，NP完全問題． NP完全問題を多項式時間で解くアルゴリズムを発見すれば，P=NPを証明したことになる．