プログラミングの基礎 /浅井健一 メトロネットワーク メモ

プログラミングの基礎 / 浅井健一

メトロネットワーク最短経路問題

• ダイクストラ法で東京の地下鉄の最短経路を導出するプログラムをつくる

ダイクストラ法の確認

1. 始点への最短距離は 0 と確定する。それ以外の点への最短距離は無限大としておく
2. 最短距離が確定した点の集合を「U」、未確定の点の集合を「V」とする。始点は「U」に、他は「V」に入れる
3. Vが空集合になったら終了する。（すべての点が確定したら終わり）
4. 直前に確定した点につながっている点の最短距離をすべて更新する
5. 「V」の中で最短距離が最小の点 p を選択する
6. p を確定し「V」から「U」に移す
7. ステップ 3 へ

これを段階に分けると...

• 準備：1, 2
• 処理：4, 5, 6
• 終了：3

メインアルゴリズム

• koushin：更新部分（ダイクストラ法の「4」）
• saitan_wo_bunri：確定と分離。（ダイクストラ法の「5」と「6」）

dijkstra_main

(* eki_t list -> ekikan_t list -> eki_t list *)
(* dijkstra: 未確定の駅リスト と 駅間リストを与えたら、ダイクストラのアルゴリズムにしたがって各駅について最短距離と最短経路が入ったリストを返す *)
let rec dijkstra_main eki_t_lst ekikan_t_list = match eki_t_lst with
  [] -> []
  | first :: rest ->
    let (saitan, etc_lst) = saitan_wo_bunri eki_t_lst in
    let updated_eki_lst = koushin saitan etc_lst ekikan_t_list in
    saitan :: dijkstra_main updated_eki_lst ekikan_t_list

koushin

• 駅pと駅リストを与えたら、駅 p に繋がっている駅の最短距離を更新する

(* eki_t -> ekikan list -> eki_t list *)
(* koushin: 直前に確定した駅p と未確定の駅リスト v が与えられたら、更新処理を済ませた駅リストを返す *)
(* 確定した点からの距離が小さかったら距離と手前リストを更新して返す *)
  let koushin p v ekikan_lst =
  List.map (fun q -> 
    match p with {namae = n; saitan_kyori = s1; temae_list = tl1} ->
    match q with {namae = n2; saitan_kyori = s2; temae_list = tl2} ->
      let kyori = get_ekikan_kyori n n2 ekikan_lst in
      let kyori_updated = s1 +. kyori in
      let temae_list_updated = n2 :: tl1 in
      let q_updated = {namae = n2; saitan_kyori = kyori_updated; temae_list = temae_list_updated} in
      if kyori = infinity then q
                          else if kyori < s2 then q_updated
                                             else q
  ) v

get_ekikan_kyori

• 二つの駅の距離を返す。koushin で用いる。

(* string -> string -> global_ekikan_list -> float *)
(* get_ekikan_kyori: 漢字の駅名をふたつ与えられたら、その駅間の距離を返す *)
let rec get_ekikan_kyori ekimei_k1 ekimei_k2 lst = match lst with
  [] -> infinity
  | {kiten=ki; shuten=s; keiyu=ke; kyori=ky; jikan=j} :: rest ->
    if ki = ekimei_k1 && s = ekimei_k2 || ki = ekimei_k2 && s = ekimei_k1 then ky
    else get_ekikan_kyori ekimei_k1 ekimei_k2 rest

saitan_wo_bunri

• ダイクストラ法「5」と「6」の部分
• 駅リストから最短距離の駅を選択して、それとそれ以外の駅リストを返す
  • 「5」：「V」の中で最短距離が最小の点 p を選択する
  • 「6」： p を確定し「V」から「U」に移す

(* eki_t list -> (eki, eki_t list) *)
(* saitan_wo_bunri: eki_t型リストを与えると、最短距離の駅とそれ以外のリストを組で返す *)
let saitan_wo_bunri eki_t_list = 
  let bunri eki_t_list eki = 
    List.filter (fun item -> item <> eki) eki_t_list in
  let saitan_eki = List.fold_right (fun x y ->
    match x with {namae = n; saitan_kyori = s; temae_list = t} ->
    match y with {namae = n2; saitan_kyori = s2; temae_list = t2} ->
    if s <= s2 then x else y) eki_t_list ({namae = ""; saitan_kyori = infinity; temae_list = []}) in
  let bunri_list = bunri eki_t_list saitan_eki in
  (saitan_eki, bunri_list)

準備部分

• romaji_to_kanji：駅名を漢字にする
• make_initial_eki_list：ダイクストラ法で使用するリストを作成する

romaji_to_kanji

• ローマ字の駅名を与えると漢字の駅名を返す

(* string -> ekimei_t list -> string *)
(* romaji_to_kanji: ローマ字の駅名と駅名リストを与えると、対応する漢字の駅名を返す *)
let rec romaji_to_kanji ekimei_romaji ekimei_lst = match ekimei_lst with
  [] -> ""
  | {kanji=kj; kana=kn; romaji=r; shozoku=s} :: rest -> 
    if ekimei_romaji = r then kj
                         else romaji_to_kanji ekimei_romaji rest

make_initial_eki_list

• 駅名リストを与えたらダイクストラ法で使えるような駅リストとして返す

(* eki_t list -> string -> eki_t list *)
(* make_initial_eki_list: ekimei_t 型のリストと漢字の駅名が与えられたら、始点を設定した上で eki_t 型のリストを返す *)
let make_initial_eki_list ekimei_lst ekimei_k =
  List.map (fun eki -> match eki with {kanji=kj; kana=kn; romaji=r; shozoku=s} ->
    if kj = ekimei_k then {namae=kj; saitan_kyori=0.0; temae_list=[kj]}
                     else {namae=kj; saitan_kyori=infinity; temae_list=[]}) ekimei_lst

ダイクストラプログラム

メインプログラム

(* 始点の駅名(ローマ字の文字列)と終点の駅名(ローマ字の文字列)を受け取ったら
    - romaji_to_kanji で始点と終点の漢字表記を求め、
    - global_ekimei_list から make_initial_eki_list を使って駅のリストを作成し、
    - dijkstra_main を使って、各駅までの最短路を確定し、
    - その中から終点の駅のレコード (eki_t型)を返す
*)
(* string -> string -> eki_t *)
let dijkstra shiten shuten =
  let shiten_k = romaji_to_kanji shiten global_ekimei_list in
  let shuten_k = romaji_to_kanji shuten global_ekimei_list in
  let eki_t_list = make_initial_eki_list global_ekimei_list shiten_k in
  let eki_t_list_done = dijkstra_main eki_t_list global_ekikan_list in
  find shuten_k eki_t_list_done 

実行結果

渋谷駅から永田町駅まで

dijkstra "shibuya" "nagatacho";;  
- : eki_t =
{namae = "永田町"; saitan_kyori = 4.;
 temae_list =
  ["永田町"; "青山一丁目"; "外苑前"; "表参道"; "渋谷"]}

代々木上原駅から和光市駅まで

dijkstra "yoyogiuehara" "wakousi";;
- : eki_t =
{namae = "和光市"; saitan_kyori = 26.8;
 temae_list =
  ["和光市"; "営団成増"; "営団赤塚"; "平和台"; "氷川台";
   "小竹向原"; "千川"; "要町"; "池袋"; "新大塚"; "茗荷谷";
   "後楽園"; "飯田橋"; "九段下"; "半蔵門"; "永田町";
   "青山一丁目"; "外苑前"; "表参道"; "明治神宮前";
   "代々木公園"; "代々木上原"]}