ワーシャルフロイド法
最短経路繋がりで、ワーシャルフロイド法を用いて全ての2点間の最短距離を求めてみた。入力データは前回用いたものと同じ(隣接行列表現)なので、結果の二次元配列の最初の要素はダイクストラ法で求めたものと同じ出力結果になっている。
#light "off" //ワーシャルフロイド法 let m = int.MaxValue;; let nodenum = 6;; //隣接行列 let adj = [| [|0;5;4;2;m;m;|]; [|5;0;2;m;6;m;|]; [|4;2;0;3;m;2;|]; [|2;m;3;0;m;6;|]; [|m;6;m;m;0;4;|]; [|m;m;2;6;4;0;|]; |];; //結果が入るデータ let cost = Array.copy adj;; //メインの処理 for k=0 to nodenum-1 do for i=0 to nodenum-1 do for j=0 to nodenum-1 do //オーバーフロー対策 if cost.[i].[k] = int.MaxValue || cost.[k].[j] = int.MaxValue then () else cost.[i].[j] <- min (cost.[i].[j]) (cost.[i].[k]+cost.[k].[j]) done done done; print_any cost;;
グラフの可視化
グラフ理論の勉強用にグラフの元データからグラフを可視化するプログラムを作成してみた。Graphクラスのコンストラクタにノード数と(点A、点B、AB間のコスト)の配列を渡せばグラフが表示される。見栄えは、微妙。
アルゴリズムは非常に単純で、グラフのノードを円形に並べ、線でつなぐだけ。線の交わりが出来るだけ少なくなるように描くプログラムが書ければかっこいいのだが。
隣接行列にもそのうち対応してみたい
#light "off" open Microsoft.FSharp.Core;; open System;; open System.Windows.Forms;; open System.Drawing;; //要素数と(始点、終点、コスト)の配列を受け取り、そのグラフを表示するクラス type Graph = class inherit Form val pbox : PictureBox val pos : (float32*float32) array //各ノードのx,y座標 val circle_width : float32 //1つのノードの幅 val circle_height : float32 //1つのノードの高さ new (pnum:int,adj) as this = {pbox = new PictureBox(); pos=Array.init pnum (fun x -> (0.f,0.f)); circle_width = 50.f; circle_height = 50.f;} then let (whole_width,whole_height)=(800,600) in this.Width <- whole_width; this.Height <- whole_height; let (screen_width,screen_height)=(this.ClientRectangle.Width,this.ClientRectangle.Height) in this.pbox.Dock <- DockStyle.Fill; this.Controls.Add(this.pbox); this.pbox.Image <- new Bitmap(screen_width,screen_height); //画面中央の計算 let (cx,cy)=((Float32.of_int screen_width)/2.f,(Float32.of_int screen_height)/2.f) in //各ノードの座標計算 for i=0 to pnum-1 do let dist = 200.f in let (dx,dy)= (cx+dist*Float32.of_float(Math.Cos(2.*Math.PI/(Float.of_int pnum)*(Float.of_int i))), cy+dist*Float32.of_float(Math.Sin(2.*Math.PI/(Float.of_int pnum)*(Float.of_int i)))) in this.pos.[i]<-(dx,dy); done; //ノードを描く Array.mapi (fun i x -> this.circle (fst x) (snd x) (i.ToString())) this.pos; //ノード間の接続とコストを描く for i in adj do let (s,e,c) = i in this.line (fst this.pos.[s]) (snd this.pos.[s]) (fst this.pos.[e]) (snd this.pos.[e]) (Float32.of_int c) done //円とラベルを指定座標に描く member this.circle (x:float32) (y:float32) label = use g = System.Drawing.Graphics.FromImage(this.pbox.Image) in let w,h = (this.circle_width,this.circle_height) in g.DrawEllipse(Drawing.Pens.Black,x,y,w,h); let font = new Font("MS UI Gothic",18.f) in let size = g.MeasureString(label,font,768,new StringFormat()) in g.DrawString(label,font,Brushes.Black,x+w/2.f-size.Width/2.f,y+h/2.f-size.Height/2.f); //線を指定座標から指定座標へ描き、間にコストを描く member this.line (sx:float32) (sy:float32) (ex:float32) (ey:float32) c= use g = System.Drawing.Graphics.FromImage(this.pbox.Image) in let (dx,dy) = (this.circle_width/2.f,this.circle_height/2.f) in let font = new Font("MS UI Gothic",12.f) in let (nsx,nsy,nex,ney) = (sx+dx,sy+dy,ex+dx,ey+dy) in g.DrawLine(Pens.Black,nsx,nsy,nex,ney); //線を1:2に内分する点にコストを描く g.DrawString(c.ToString(),font,Brushes.Black,(nsx+2.f*nex)/3.f,(nsy+2.f*ney)/3.f); end;; //(始点、終点、コスト)からなる配列。 let adj = [|(0,1,5);(0,2,4);(0,3,2);(1,2,2);(1,4,6);(2,3,3);(2,5,2);(3,5,6);(4,5,4)|];; [<STAThread>] do System.Windows.Forms.Application.Run(new Graph(6,adj));;
ダイクストラ法
練習がてら、F#でダイクストラ法のアルゴリズムを実装してみた。といっても最短距離を求めるところまでで、最短経路は求めていない。
入力データはこのページにあるものをそのまま利用させてもらった。このページはわかりやすくてためになります。
プログラムではupdate関数の副作用を無くすために毎回配列をcopyしているので、その分メモリを食うはず。プログラムとしてはなんとか動作はするが、もうちょっとうまくかけそうな気がするなぁ。
#light "off" let pe x = print_any x;print_endline "";; //点の数 let nodenum = 6;; //(始点,終点,間のコスト) let adj = [|(0,1,5);(0,2,4);(0,3,2);(1,2,2);(1,4,6);(2,3,3);(2,5,2);(3,5,6);(4,5,4)|];; //i番目に始点から点iまでのコストと、点iが確定したかのflagを格納する配列 let cost = Array.init nodenum (fun x -> (int.MaxValue,false));; cost.[0] <- (0,false);; //1つの点を確定させる操作。確定後のコストを新しい配列で返す let update adj cost = //確定していない点の中で最小のものを求める let unchecked = Array.find (fun x -> snd x = false) cost in let next = Array.fold_left (fun acc x -> if not (snd x) then if (fst acc) > (fst x) then x else acc else acc) unchecked cost in let pos = Array.find_index ((=)next) cost in let ret = Array.copy cost in ret.[pos] <- (fst next,true); //確定した点からたどれる点のコストを更新 Array.iter (fun x -> let s,e,c = x in if s = pos then if fst ret.[e] > fst ret.[s] + c then ret.[e] <- (fst ret.[s] + c,snd ret.[e]) else () else if e = pos then if fst ret.[s] > fst ret.[e] + c then ret.[s] <- (fst ret.[e] + c,snd ret.[s]) else () else ()) adj; ret;; //全ての点が確定するまで確定操作を繰り返す Array.fold_left (fun acc _ -> let next = update adj acc in pe next;next) <| cost <| Array.zero_create nodenum |> ignore;;
All your base are belong to us
#lightシンタックスについて思うこと
#lightシンタックスはOCamlとの互換性がないためあまり好きじゃない。
しかし、matchをネストするようなケースは、lightシンタックスのほうが綺麗に記述出来る。通常のシンタックスだと()またはbegin〜endが事実上必須になる(ように思う)から。
通常のシンタックスだと、括弧やbegin〜endを書かない場合、2番目に書いたmatchが残り全てのパターンにマッチしてしまう。そのため、次の例(#light "off")では一番下のワイルドカードにはマッチしないどころか、最初の1にマッチするルールが無いと言われ例外が発生する。
match 1 with | 0 -> match 10 with | 0 -> 0 | _ -> 10 | _ -> 1
しかし、一番良いのは、ネストしたパターンマッチを使用しないようにプログラムすることかもしれない
ワイルドカードパターンのメリット
今、暇な時間に少しずつ、F# for Scientistsを読んでいて
その中で、なるほど、思った部分があったので紹介してみる。
F#では任意のパターンにマッチするワイルドカードパターンというものがあるが、ワイルドカードを使わずにパターン部に変数をおいた場合にも、任意のパターンにマッチする動作をする。
具体的には次の例の通り。
これらはかけ算を行う関数の定義で、どちらも同じ動作をします。
//ワイルドカードパターン不使用 let product a b = match a,b with | a,0 -> 0 | 0,b -> 0 | a,b -> a*b;;
//ワイルドカードパターン使用 let product2 a b = match a,b with | _,0 -> 0 | 0,_ -> 0 | a,b -> a*b;;
しかし、下の例のワイルドカードパターンを用いたバージョンのほうが実際は良くて、ワイルドカードパターンを用いた場合、
○パターンマッチした値は使用されない
という点が明確になるとのこと。
また、場合は限られるが、このケースではワイルドカードパターンを用いた場合は、最初2つのパターンマッチをORパターンでかけるという点も有利です。
ほんとにちょっとしたことだけれども、コーディングスタイルの一例としていかがでしょうか。
