このディレクトリの索引

% 以下のサイトは # [1] 授業単元:情報処理 # [2] 問題文(含コード&リンク): # 例えば下図に示すように,通行可能なマス目に'0'が, # 障害物があって通行不能なマス目に'+'が記されている盤がある. # 盤の左上をスタート地点,右下をゴール地点として,経路を表示する # プログラムを作りなさい. # 盤の例 # 0 0 + 0 + # + 0 0 0 + # 0 + + 0 0 # 0 0 + 0 0 # + 0 0 0 0 # # 例えばこのようなアルゴリズムが考えられる. # # 1) 現在位置を表示の後、進行方向に対して,右に進めるなら右に, # そうでなければ直進,それもだめなら左に,さらにそれもダメなら後退する. # 2) 1を繰り返してゴールに達したらその旨を表示する. # ただし,マス目の数分だけ移動してもゴールに達しない場合はその時点で終了する. # # 入力形式は、 # # %> ./a.out 00+0+ +000+ 0++00 00+00 +0000 # # とする. t340(X) :- abolish(経路/2), write('盤面を一行で入力しなさい '), get_line(S), t340_1(S,_終点), 経路探索((1,1),_終点,[(1,1)],X). 経路探索(_終点,_終点,Log,Log) :- !. 経路探索(A,_終点,Log,X) :- 経路(A,B), not(member(B,Log)), 経路探索(B,_終点,[B|Log],X),!. 経路探索(A,_終点,Log,X) :- 経路(B,A), not(member(B,Log)), 経路探索(B,_終点,[B|Log],X),!. t340_1(S,(N,M)) :- split(S,[' '],L), findall(L1,(member(A,L),atom_chars(A,L1)),Ls), length(Ls,N), t340_2(1,Ls), 行列の転置(Ls,Ls2), length(Ls2,M), t340_3(1,Ls2),!. t340_2(_,[]) :- !. t340_2(N,[L|R]) :- t340_2_1(N,1,L), N2 is N + 1, t340_2(N2,R). t340_2_1(_,_,[_]) :- !. t340_2_1(N,M,['+'|R]) :- M2 is M + 1, t340_2_1(N,M2,R),!. t340_2_1(N,M,[A,B|R]) :- not(A='+'), not(B='+'), M2 is M + 1, assertz(経路((N,M),(N,M2))), t340_2_1(N,M2,[B|R]),!. t340_2_1(N,M,[A,B|R]) :- not(A='+'), B='+', M2 is M + 1, t340_2_1(N,M2,[B|R]),!. t340_3_1(_,_,[_]) :- !. t340_3_1(N,M,['+'|R]) :- M2 is M + 1, t340_3_1(N,M2,R),!. t340_3_1(N,M,[A,B|R]) :- not(A='+'), not(B='+'), M2 is M + 1, assertz(経路((M,N),(M2,N))), t340_3_1(N,M2,[B|R]),!. t340_3_1(N,M,[A,B|R]) :- not(A='+'), B='+', M2 is M + 1, t340_3_1(N,M2,[B|R]),!. % 以下のサイトは # 出典:: http://pc12.2ch.net/test/read.cgi/tech/1255709298/697 # # [1] 授業単元: # アルゴリズムとプログラミング # [2] 問題文(含コード&リンク): # 初めて呼損が起こるまでに確率できた通信回数を評価したい。 # 次のプログラムに追加して、以下の方法で評価を行うプログラムを完成させてください。 # # 1、ランダムに送受信ノードを決定する # 2、与えられた送受信ノード間の経路を決定する # (a)その経路上の全てのリンクに空き容量がある場合、それらを1Mbpsだけ減少させ、「確率できた通信回数」を1増やし、手続き1に戻る # (b)その経路上に空き容量のないリンクが存在する場合、呼損とし、その時点までの「確率できた通信回数」を記録して手続き3に進む。 # 3、全リンクの空き容量を初期状態に戻し、手続き1に戻る # 4、1〜3の手続きを1000回行い、「初めて呼損が起こるまでに確立できた通信回数」の平均を算出する。 送受信ノード(a,10000). 送受信ノード(b,10000). 送受信ノード(c,10000). 送受信ノード(d,10000). 送受信ノード(e,10000). 経路(a,b). 経路(b,a). 経路(b,c). 経路(c,b). 経路(b,d). 経路(c,e). 経路(e,c). 経路(d,e). 経路(e,d). 経路(e,a). 経路(e,c). 初めて呼損が起こるまでに確率できた通信回数を評価(0,_平均値) :- findavg(_接続数,経路点情報(_接続数),_平均値). 初めて呼損が起こるまでに確率できた通信回数を評価(N,_平均値) :- ノードの総数を調べる(_ノードの総数,_ノードならび), ノード空き容量の初期化(_ノード空き容量ならび), 組み合わせの総数を調べる(_ノードならび,_組み合わせの総数,_組み合わせ), ランダムに送受信ノードを決定する(1,1000,_ノードの総数,_ノードならび,_組み合わせ総数,_組み合わせ,_ノードの空き容量ならび,_経路情報). 初めて呼損が起こるまでに確率できた通信回数を評価(N) :- N1 is N -1, 初めて呼損が起こるまでに確率できた通信回数を評価(N1,_平均値). ランダムに送受信ノードを決定する(_接続数1,_接続数,_ノードの総数,_ノードならび,_組み合わせ総数,_組み合わせ,_ノードの空き容量ならび,[[X,Y]|R]) :- 経路の選択(_組み合わせの総数,_組み合わせ,X,Y), 接続(1,M,X,Y,_ノード空き容量ならび,_更新されたノード空き容量ならび), _接続数2 is _接続数1 + M, ランダムに送受信ノードを決定する(_接続数2,_接続数,_ノードの総数,_ノードならび,_組み合わせ総数,_組み合わせ,_ノードの空き容量ならび,R). ランダムに送受信ノードを決定する(_接続数,_接続数,_ノードの総数1,_ノードならび1,_組み合わせ総数1,_組み合わせ1,_ノードの空き容量ならび1,[]) :- assertz(経路点情報(_接続数)),!,fail. ランダムに送受信ノードを決定する(_ノードの総数,_ノードならび,_組み合わせ総数,_組み合わせ,_ノードの空き容量ならび,[[X,Y]|R]). 経路の選択(_組み合わせの総数,_組み合わせ,X,Y) :- 乱数の発生(_組み合わせの総数,_乱数), list_nth(_乱数,_組み合わせ,[X,Y]),!. 経路の選択(_組み合わせの総数,_組み合わせ,X,Y) :- 経路の選択(_組み合わせの総数,_組み合わせ,X,Y). 乱数の発生(_組み合わせの総数,_乱数) :- _乱数 is (random mod _組み合わせの総数) + 1. ノードの総数を調べる(_ノードの総数,_ノードならび) :- findall(A1,送受信ノード(A1,_),_ノードならび), length(_ノードならび,_ノードの総数). ノード空き容量の初期化(_ノード空き容量ならび) :- findall([A,B],送受信ノード(A,B),_ノード空き容量ならび),!. 組み合わせの総数を調べる(_ノードならび,_組み合わせの総数,_組み合わせ) :- findall(L2,組み合わせ(_ノードならび,2,L2),_組み合わせ), length(_組み合わせ,_組み合わせの総数). 接続(N,N,X,X,_ノード空き容量ならび,_更新されたノード空き容量ならび) :- 容量更新(X,_ノード空き容量ならび,_ノード空き容量ならび),!. 接続(N,M,X,Y,_ノード空き容量ならび,_更新されたノード空き容量ならび) :- 経路(X,Z), 容量更新(X,_ノード空き容量ならび,_ノード空き容量ならび2), N2 is N + 1, 接続(N2,M,Z,Y,_ノード空き容量ならび2,_更新されたノード空き容量ならび). 容量更新(X,[[X,N]|R],[[X,N1]|R]) :- N < 1000,!,fail. 容量更新(X,[[X,N]|R],[[X,N1]|R]) :- N1 is N - 1000,!. 容量更新(X,[A|R1],[A|R2]) :- 容量更新(X,R1,R2). % 以下のサイトは # 出典:: http://pc12.2ch.net/test/read.cgi/tech/1258158172/771 # # [1] 授業単元:C言語演習 # [2] 問題文(含コード&リンク):これに全て記載 http://ime.nu/kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/10245.c # # 問題 # graph.cの関数print_graph_memory()を参考に、グラフの連結であるか否かの判定を行うプログラムを作成せよ。 # または連結な場合は、一筆書きできるか否かの判定を行うようにせよ。 # sample5.dimacs、sample6.dimacs、sample7.dimacsを連結判定・一筆書き判定せよ。 有向グラフに於いて一筆書き(A,_経路) :- setof((B,C),有向グラフ(B,C),L), length(L,Len), 有向グラフに於いて一筆書き(A,A,Len,[],_経路). 有向グラフに於いて一筆書き(A,A,Len,L,[]) :- length(L,Len),!. 有向グラフに於いて一筆書き(A,S,Len,L,[A|R]) :- 有向グラフ(A,B), \+(member((A,B),L)), 有向グラフに於いて一筆書き(B,S,Len,[(A,B)|L],R). % 以下のサイトは # 出典:: http://pc12.2ch.net/test/read.cgi/tech/1248012902/509 # # 【 課題 】 # http://nojiriko.asia/jpeg/841.jpg # 図の有向グラフの最短経路を求めよ。 # 初期値がMAXでアルゴリズムを作れ。 有向グラフ(1,2,50). 有向グラフ(1,3,80). 有向グラフ(2,4,15). 有向グラフ(2,3,20). 有向グラフ(4,5,30). 有向グラフ(3,4,10). 有向グラフ(3,5,15). 有向グラフの最短経路(_頂点1,_頂点2,_最短距離,_最短経路) :-   findmin([_距離,_経路],有向グラフの距離と経路(_出発点,_終点,_距離,_経路),[_ 最短距離,_最短経路]). 有向グラフの距離と経路(_頂点,_頂点,0,[_頂点]) :- !. 有向グラフの距離と経路(_頂点1,_頂点2,_距離,[_頂点1|R]) :-   有向グラフ(_頂点1,_頂点3,_距離1),   有向グラフの距離と経路(_頂点3,_頂点2,_距離2,R),   _距離 is _距離2 + _距離1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 有向グラフ(1,2,50). 有向グラフ(1,3,80). 有向グラフ(2,4,15). 有向グラフ(2,3,20). 有向グラフ(4,5,30). 有向グラフ(3,4,10). 有向グラフ(3,5,15). 有向グラフの最短経路(_頂点1,_頂点2,_最短距離,_最短経路) :- findmin([_距離,_経路],有向グラフの距離と経路(_出発点,_終点,_距離,_経路),[_ 最短距離,_最短経路]). 有向グラフの距離と経路(_頂点,_頂点,0,[_頂点]) :- !. 有向グラフの距離と経路(_頂点1,_頂点2,_距離,[_頂点1|R]) :- 有向グラフ(_頂点1,_頂点3,_距離1), 有向グラフの距離と経路(_頂点3,_頂点2,_距離2,R), _距離 is _距離2 + _距離1. % 以下のサイトは # 出典:: http://pc12.2ch.net/test/read.cgi/tech/1248012902/509 # # 【 課題 】 # http://nojiriko.asia/jpeg/841.jpg # 図の有向グラフの最短経路を求めよ。 # 初期値がMAXでアルゴリズムを作れ。 有向グラフ(1,2,50). 有向グラフ(1,3,80). 有向グラフ(2,4,15). 有向グラフ(2,3,20). 有向グラフ(4,5,30). 有向グラフ(3,4,10). 有向グラフ(3,5,15). 有向グラフの最短経路(_頂点1,_頂点2,_最短距離,_最短経路) :-   findmin([_距離,_経路],有向グラフの距離と経路(_出発点,_終点,_距離,_経路),[_ 最短距離,_最短経路]). 有向グラフの距離と経路(_頂点,_頂点,0,[_頂点]) :- !. 有向グラフの距離と経路(_頂点1,_頂点2,_距離,[_頂点1|R]) :-   有向グラフ(_頂点1,_頂点3,_距離1),   有向グラフの距離と経路(_頂点3,_頂点2,_距離2,R),   _距離 is _距離2 + _距離1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 有向グラフ(1,2,50). 有向グラフ(1,3,80). 有向グラフ(2,4,15). 有向グラフ(2,3,20). 有向グラフ(4,5,30). 有向グラフ(3,4,10). 有向グラフ(3,5,15). 有向グラフの最短経路(_頂点1,_頂点2,_最短距離,_最短経路) :- findmin([_距離,_経路],有向グラフの距離と経路(_出発点,_終点,_距離,_経路),[_ 最短距離,_最短経路]). 有向グラフの距離と経路(_頂点,_頂点,0,[_頂点]) :- !. 有向グラフの距離と経路(_頂点1,_頂点2,_距離,[_頂点1|R]) :- 有向グラフ(_頂点1,_頂点3,_距離1), 有向グラフの距離と経路(_頂点3,_頂点2,_距離2,R), _距離 is _距離2 + _距離1. % 以下のサイトは # 出典:: http://hibari.2ch.net/test/read.cgi/tech/1294061094/32 # # [1] 授業単元:C言語 # [2] 問題文(含コード&リンク): #   巡回セールスマン問題 #   いくつかの都市と都市間を結ぶ経路があります。全ての都市を一巡するのに最も短い経路を求めるプログラムを作成せよ。 #   TSPのデータファイルはgr17.txtで、数字の部分が都市数です。 #   ファイルの記述の仕方が以下のようになっています。 # #   gr17.txtの例 # #   17   最初の数値は都市数 #   0    第0都市と第0都市との距離が0 #   633 0  第1都市と第0都市との距離が633、第1都市と第1都市との距離が0 #   257 390 0 第2都市と第0、第1、第2都市との距離がそれぞれ257,390,0 #   91 661 228 0 以下同様 #   412 227 169 383 0 # 150 488 112 120 267 0 #      以下略 # #   補足説明として #   ・同じ道を通ってもよい #   ・全ての都市を1回通ればよい(巡回しなくていい) #   ・全探索はなるべく使用しないで深さ優先探索、分子限定法を用いること # # 17 # 0 # 633 0 # 257 390 0 # 91 661 228 0 # 412 227 169 383 0 # 150 488 112 120 267 0 # 80 572 196 77 351 63 0 # 134 530 154 105 309 34 29 0 # 259 555 372 175 338 264 232 249 0 # 505 289 262 476 196 360 444 402 495 0 # 353 282 110 324 61 208 292 250 352 154 0 # 324 638 437 240 421 329 297 314 95 578 435 0 # 70 567 191 27 346 83 47 68 189 439 287 254 0 # 211 466 74 182 243 105 150 108 326 336 184 391 145 0 # 268 420 53 239 199 123 207 165 383 240 140 448 202 57 0 # 246 745 472 237 528 364 332 349 202 685 542 157 289 426 483 0 # 121 518 142 84 297 35 29 36 236 390 238 301 55 96 153 336 0 # # 'いくつかの都市と都市間を結ぶ経路があります。全ての都市を一巡するのに最も短い経路を求めるプログラムを作成せよ。'(_出発都市,_最短経路) :- グラフを読み取る(LL), グラフを作成する(LL,_都市数), findmin([_距離合計,_巡回ならび],( 巡回(_都市数,_出発都市,_巡回ならび,_距離合計)), [_距離合計,_最短経路]). グラフを読み取る(LL) :- get_split_lines('gr17.txt',[' '],LL). グラフを作成する([_都市数|R],_都市数) :- グラフを作成する([],R). グラフを作成する([],_) :- !. グラフを作成する([_|Ln],[L|R]) :- length(Ln,_都市N), 都市間の距離定義([],Ln,L), グラフを作成する(Ln,R). 都市間の距離定義(Ln,Ln,[]) :- !. 都市間の距離定義(Ln,_都市N,[A|R]) :- !. length(Ln,_都市M), assertz(都市間の距離(_都市N,_都市M,A)), assertz(都市間の距離(_都市M,_都市N,A)), 都市間の距離定義([_|Ln],_都市N,R). 巡回(_都市数,_出発都市,_巡回ならび,_距離合計) :- 都市間の距離(_出発都市,_隣接都市,_距離), 巡回(_都市数,_出発都市,_隣接都市,[_出発都市],_巡回ならび,_距離,_距離合計). 巡回(_都市数,_出発都市,_出発都市,_巡回ならび,_巡回ならび,距離合計,_距離合計) :- sort(_巡回ならび,_巡回ならびの二), length(_巡回ならびの二,_都市数),!. 巡回(_都市数,_出発都市,_隣接都市,_巡回ならびの一,_巡回ならび,距離合計の一,_距離合計) :- 都市間の距離(_隣接都市,_隣接都市の二,_距離), \+(append(_,[_隣接都市の二,_隣接都市|_],_巡回ならびの一)), _距離合計の二 is _距離合計の一 + _距離, 巡回(_都市数,_出発都市,_隣接都市の二,[_隣接都市|_巡回ならびの一],_巡回ならび,_距離合計の二,_距離合計). % 以下のサイトは # 出典:: http://hibari.2ch.net/test/read.cgi/tech/1296387672/27 # # [1] 授業単元:C言語 # [2] 問題文(含コード&リンク):http://ime.nu/codepad.org/zKDn7mD5 # # # 壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁S壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁 # 壁 壁   壁   壁 壁     壁 壁   壁 壁   壁 # 壁 壁 壁壁壁 壁 壁 壁 壁壁壁 壁 壁 壁 壁 壁壁壁 壁 # 壁 壁   壁 壁 壁 壁 壁   壁   壁 壁 壁   壁 # 壁 壁壁壁 壁 壁 壁 壁 壁 壁壁壁 壁壁壁壁壁 壁壁壁 壁 # 壁     壁 壁     壁   壁 壁   壁 壁   壁 # 壁 壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁 壁 壁 壁壁壁 壁壁壁 壁 # 壁     壁   壁   壁 壁 壁     壁 壁   壁 # 壁 壁壁壁壁壁壁壁 壁 壁 壁 壁 壁 壁壁壁壁壁 壁壁壁 壁 # 壁     壁     壁 壁   壁   壁 壁 壁   壁 # 壁壁壁 壁 壁壁壁 壁 壁 壁 壁 壁 壁壁壁 壁 壁壁壁 壁 # 壁   壁 壁   壁 壁 壁 壁 壁     壁 壁   壁 # 壁 壁 壁 壁 壁壁壁 壁 壁 壁 壁壁壁壁壁 壁 壁壁壁 壁 # 壁 壁 壁 壁   壁 壁 壁 壁       壁 壁 壁 壁 # 壁 壁壁壁壁壁壁壁 壁 壁 壁 壁 壁壁壁壁壁 壁 壁 壁 壁 # 壁     壁   壁 壁   壁 壁     壁 壁 壁 壁 # 壁 壁壁壁 壁 壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁 壁 壁 壁 # 壁 壁   壁     壁 壁   壁     壁 壁 壁 壁 # 壁 壁壁壁壁壁 壁 壁 壁 壁壁壁 壁壁壁 壁壁壁 壁 壁 壁 # 壁     壁 壁 壁   壁   壁     壁     壁 # 壁壁壁壁壁 壁 壁壁壁壁壁壁壁 壁 壁 壁 壁壁壁 壁壁壁壁壁 # 壁             壁 壁 壁 壁   壁     壁 # 壁 壁壁壁 壁壁壁壁壁壁壁 壁 壁 壁 壁壁壁壁壁壁壁壁壁 壁 # 壁 壁   壁         壁       壁   壁 壁 # 壁 壁 壁 壁 壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁 壁 壁 # 壁 壁 壁 壁 壁           壁   壁     壁 # 壁 壁 壁 壁 壁 壁壁壁壁壁壁壁 壁 壁 壁 壁壁壁壁壁 壁 # 壁 壁 壁 壁         壁 壁 壁 壁 壁     壁 # 壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁 壁 壁 壁 壁 壁 壁壁壁壁壁 # 壁       壁 壁   壁 壁 壁   壁 壁 壁   壁 # 壁壁壁壁壁壁壁 壁 壁 壁壁壁 壁 壁壁壁 壁 壁 壁壁壁 壁 # 壁               壁 壁   壁 壁 壁 壁 壁 # 壁 壁 壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁 壁 壁 壁 壁 # 壁 壁 壁 壁       壁 壁     壁 壁 壁 壁 壁 # 壁壁壁 壁 壁 壁壁壁 壁 壁 壁 壁壁壁壁壁 壁 壁 壁 壁 # 壁         壁 壁   壁             壁 # 壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁壁G壁 迷路探索(_迷路ファイル,_経路) :- 迷路情報の取得(_迷路ファイル,_迷路情報), Sの位置は(_迷路情報,_行S,_列S), Gの位置は(_迷路情報,_行G,_列G), 迷路探索(_迷路情報,_置換された迷路情報,_行S,_列S,_行G,_列G,[],Log), reverse(Log,Log2), 経路の整理(Log2,_経路). 迷路情報の取得(_迷路ファイル,_迷路情報) :- get_chars(_迷路ファイル,Chars), 改行文字で分割(Chars,_迷路情報),!. Sの位置は(LL1,_行,_列) :- append(L0,[L|_],LL1), length([_|L0],_行), append(L1,[S|_],L), length([_|L1],_列),!. Gの位置は(LL1,_行,_列) :- append(L0,[L|_],LL1), length([_|L0],_行), append(L1,[G|_],L), length([_|L1],_列),!. 改行文字で分割([],[]) :- !. 改行文字で分割(L1,[L0|R2]) :- append(L0,['\n'|R],L1),!, 改行文字で分割(R,R2). 迷路探索(LL1,_行G,_列G,_行G,_列G,Log,Log) :- !. 迷路探索(LL1,_行,_列,Log1,Log) :- append(L0,[L|_],LL1), length([_|L0],_行), append(L1,[A|_],L), length([_|L1],_列), 次の選択(LL1,_行,_列,Log1,_行2,_列2), 迷路探索(LL1,_行2,_列2,_行G,_列G,[[_行,_列,_行2,_列2]|Log1],Log). 次の選択(LL1,_行,_列,Log1,_行2,_列) :- _行2 is _行 + 1, \+(append(_,[[_行2,_列,_行,_列]|_],Log1), \+(append(_,[[_行,_列,_行2,_列]|_],Log1), append(L0,[L|_],LL1), length([_,_|L0],_行), append(L1,[A|_],L), length([_|L1],_列), \+(A = 壁). 次の選択(LL1,_行,_列,Log1,_行2,_列) :- _行2 is _行 - 1, \+(append(_,[[_行2,_列,_行,_列]|_],Log1), \+(append(_,[[_行,_列,_行2,_列]|_],Log1), append(L0,[L|_],LL1), length(L0,_行), append(L1,[A|_],L), length([_|L1],_列), \+(A = 壁). 次の選択(LL1,_行,_列,Log1,_行2,_列) :- _列2 is _列 + 1, \+(append(_,[[_行,_列2,_行,_列]|_],Log1), \+(append(_,[[_行,_列,_行,_列2]|_],Log1), append(L0,[L|_],LL1), length([_|L0],_行), append(L1,[A|_],L), length([_,_|L1],_列), \+(A = 壁). 次の選択(LL1,_行,_列,Log1,_行2,_列) :- _列2 is _列 - 1, \+(append(_,[[_行,_列2,_行,_列]|_],Log1), \+(append(_,[[_行,_列,_行,_列2]|_],Log1), append(L0,[L|_],LL1), length([_|L0],_行), append(L1,[A|_],L), length(L1,_列), \+(A = 壁). 経路の整理([[_行1,_列1,_行2,_列2]],[[行1,_列1],[_行2,_列2]]) :- !. 経路の整理([[_行1,_列1,_行2,_列2]|R1],[[行1,_列1]|R2]) :- !. 経路の整理([R1,R2). % 以下のサイトは # 出典:: http://hibari.2ch.net/test/read.cgi/tech/1296387672/122 # # [1] 授業単元:アルゴリズム # [2] 問題文(含コード&リンク):http://ime.nu/www.dotup.org/uploda/www.dotup.org1311028.txt.html # # Map.datを読み取って画面に一覧表を表示「1」と「.」は半角 # 県と県の間を半角開ける # # 1.北海道 2.青森県・・・47.沖縄県を表示 # 一行につき6県 # # (例) # _1.北海道____2.鹿児島県__3. # # ↑ # 桁が上がったとき用 # # # 43.□□□___44.□□ # # # 次に47都道府県のうち出発地と目的地の入力を要求する. # # 「出発の県を入力してください」 # 「目的の県を入力してください」 # # # # # 次に結果を表示. # # ・距離と経路を出力 # # 経路 # □□□□→□□□□→・・・→□□□□ # # -10byte-- # # 経路は7県まで # # # # とする # # # # map.datの中身は↓です # # 北海道,青森県,岩手県,宮城県,秋田県,山形県,福島県,茨城県,栃木県,群馬県,埼玉県,千葉県,東京都,神奈川県,新潟県,富山県,石川県,福井県,山梨県,長野県,岐阜県,静岡県,愛知県,三重県,滋賀県,京都府,大阪府,兵庫県,奈良県,和歌山県,鳥取県,島根県,岡山県,広島県,山口県,徳島県,香川県,愛媛県,高知県,福岡県,佐賀県,長崎県,熊本県,大分県,宮崎県,鹿児島県,沖縄県 # # 北海道,0,426,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 青森県,426,0,187,-1,190,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 岩手県,-1,187,0,193,108,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 宮城県,-1,-1,193,0,258,72,84,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 秋田県,-1,190,108,258,0,212,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 山形県,-1,-1,-1,72,212,0,102,-1,-1,-1,-1,-1,-1,-1,169,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 福島県,-1,-1,-1,84,-1,102,0,203,172,275,-1,-1,-1,-1,189,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 茨城県,-1,-1,-1,-1,-1,-1,203,0,76,-1,-1,116,128,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 栃木県,-1,-1,-1,-1,-1,-1,172,76,0,109,100,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 群馬県,-1,-1,-1,-1,-1,275,-1,109,0,103,-1,-1,-1,220,-1,-1,-1,-1,151,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 埼玉県,-1,-1,-1,-1,-1,-1,116,100,103,0,69,24,-1,-1,-1,-1,-1,157,215,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 千葉県,-1,-1,-1,-1,-1,-1,128,-1,-1,69,0,50,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 東京都,-1,-1,-1,-1,-1,-1,-1,-1,-1,24,50,0,37,-1,-1,-1,-1,133,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 神奈川県,-1,-1,-1,-1,-1,-1,-1,-1,-1,37,0,-1,-1,-1,-1,134,-1,-1,240,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 新潟県,-1,-1,-1,-1,169,189,-1,-1,220,-1,-1,-1,-1,0,250,-1,-1,-1,208,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 富山県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,250,0,61,-1,-1,196,294,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 石川県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,61,0,83,-1,-1,235,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 福井県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,83,0,-1,-1,160,-1,-1,-1,176,188,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 山梨県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,164,-1,126,134,-1,-1,-1,-1,0,162,-1,109,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 長野県,-1,-1,-1,-1,-1,-1,-1,-1,-1,151,220,-1,-1,-1,208,196,-1,-1,162,0,295,271,272,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 岐阜県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,294,235,160,-1,295,0,-1,43,113,128,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 静岡県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,167,-1,-1,-1,-1,109,271,-1,0,181,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 愛知県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,272,43,181,0,82,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 三重県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,113,-1,82,0,95,107,-1,-1,91,91,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 滋賀県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,176,-1,-1,128,-1,-1,95,0,14,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 京都府,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,188,-1,-1,-1,-1,-1,107,14,0,49,75,48,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 大阪府,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,49,0,45,33,80,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 兵庫県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,75,45,0,-1,-1,180,-1,139,-1,-1,115,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 奈良県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,91,-1,48,33,-1,0,98,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 和歌山県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,91,-1,-1,-1,-1,98,0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 鳥取県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,180,-1,-1,0,128,167,296,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # 島根県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,80,-1,128,0,-1,212,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 岡山県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,139,-1,-1,167,-1,0,165,-1,-1,70,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 広島県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,296,212,165,0,131,-1,-1,190,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 山口県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,131,0,250,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 徳島県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,115,-1,-1,-1,-1,-1,-1,250,0,73,191,161,-1,-1,-1,-1,-1,-1,-1,-1 # # 香川県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,70,-1,-1,73,0,156,-1,-1,-1,-1,-1,-1,-1,-1,-1 # # 愛媛県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,190,-1,191,156,0,156,-1,-1,-1,-1,-1,-1,-1,-1 # # 高知県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,161,-1,156,0,-1,-1,-1,-1,-1,-1,-1,-1 # # 福岡県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,165,-1,-1,-1,-1,0,61,-1,117,159,-1,-1,-1 # # 佐賀県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,61,0,109,-1,-1,-1,-1,-1 # # 長崎県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,109,0,-1,-1,-1,-1,-1 # # 熊本県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,117,-1,-1,0,218,192,187,-1 # # 大分県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,159,-1,-1,218,0,181,-1,-1 # # 宮崎県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,192,181,0,158,-1 # # 鹿児島県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,187,-1,158,0,733 # # 沖縄県,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,733,0 # '47都道府県のうち出発地と目的地の入力して最短経路を求めて距離と順路を表示する(ただし経路は7以下とする)' :- 'Map.datを読み取って画面に一覧表を表示「1」と「.」は半角 県と県の間を半角 開ける'(_都道府県名ならび), '47都道府県のうち出発地と目的地の入力する'(_都道府県名ならび,_出発地,_目的地), 最短経路(_出発地,_目的地,_距離,_順路), 距離と経路の表示(_出発地,_目的地,_距離,_順路). '47都道府県のうち出発地と目的地の入力する'(_都道府県名ならび,_出発地,_目的地) :- 出発地を入力する(_都道府県名ならび,_出発地), 目的地を入力する(_都道府県名ならび,_目的地). 出発地を入力する(_都道府県名ならび,_出発地) :- write('出発地の都道府県名番号を入力してください : '), get_line(Line), 出発地を入力診断(Line,_都道府県名ならび,_出発地),!. 出発地を入力する(_都道府県名ならび,_出発地) :- 出発地を入力する(_都道府県名ならび,_出発地). 出発地を入力診断(Line,_都道府県名ならび,_出発地) :- atom_to_term(Line,_出発地番号,_), integer(_出発地番号), _出発地番号 > 1, _出発地番号 =< 47, list_nth(_出発地番号,_都道府県名ならび,_出発地),!. 出発地を入力診断(Line,_都道府県名ならび,_出発地) :- write_formatted('入力された %t から適切な出発地を得ることができません。再入力をお願いします。\n',[Line]), fail. 目的地を入力する(_都道府県名ならび,_目的地) :- write('目的地の都道府県名番号を入力してください : '), get_line(Line), 目的地を入力診断(Line,_都道府県名ならび,_目的地), 目的地を入力する(_都道府県名ならび,_目的地) :- 目的地を入力する(_都道府県名ならび,_目的地). 目的地を入力診断(Line,_都道府県名ならび,_目的地) :- atom_to_term(Line,_目的地番号,_), integer(_目的地番号), _目的地番号 > 1, _目的地番号 =< 47,!. 目的地を入力診断(Line,_,_目的地) :- write_formatted('入力された %t から適切な目的地を得ることができません。再入力をお願いします。\n',[Line]), fail. 距離と経路の表示(_出発地,_目的地,_距離,_順路) :- write_formatted('距離は %t,経路は %t',[_距離,_出発地]), append(_,[[A,B]|R],_順路), write_formatted(' -> %t ',[B]), R = [], write('\n'),!. 'Map.datを読み取って画面に一覧表を表示「1」と「.」は半角 県と県の間を半角 開ける'(_都道府県名ならび) :- get_split_lines('Map.dat',[','],LL), 第要素は都道府県名、残りは経路情報(LL,_都道府県名ならび,_経路情報ならび), append(L0,[[_県名|_隣接情報ならび]|R2],_経路情報ならび), 隣接情報の登録(_県名,_都道府県名ならび,_隣接情報ならび), length([_|L0],_都道府県番号), write('%2d.%t ',[_都道府県番号,_県名]), R2 = [], write('\n'). 第一要素は都道府県名、残りは経路情報(LL,_都道府県名ならび,_経路情報ならび) :- LL = [_都道府県名ならび|_経路情報ならび],!. 隣接情報の登録(_都道府県名,_都道府県名ならび,L1) :- abolish(隣接県距離/3), append(L0,[_距離|R],L1), \+(_距離 = (-1)), \+(_距離 = 0), length([_|L0],Nth), list_nth(Nth,_都道府県名ならび,_都道府県名2), assertz(隣接県距離(_都道府県名,_件名2,_距離)), fail. 隣接情報の登録(_,_,_). 最短経路(_出発地,_目的地,_距離,_順路) :- findall([_順路,_距離],( 到達(_出発地,_目的地,_距離,[],_順路)), _順路・距離ならび), findmin(_距離,append(_,[[_,_距離]|_],_順路・距離ならび),_最短距離), append(_,[[_順路,_最短距離]|_],_順路距離ならび). 到達(_都道府県名1,_都道府県名2,_距離,_順路1,_順路) :- 隣接県距離(_都道府県名1,_都道府県名2,_距離), append(_順路1,[[_都道府県名1,_都道府県名2]],_順路),!. 到達(_都道府県名1,_都道府県名2,_距離,_順路1,_順路) :- length(_順路1,_経路数), _経路数 < 7, 隣接県距離(_都道府県名1,_都道府県名3,_距離1), この経路は選択されたことがない(_都道府県名1,_都道府県名2), append(_順路1,[[_都道府県名1,_都道府県名3]],_順路2), 到達(_都道府県名1,_都道府県名2,_距離2,_順路2,_順路), _距離 is _距離1 + _距離2. この経路は選択されたことがない(_都道府県名1,_都道府県名2) :- \+(append(_,[[_都道府県名1,_都道府県名3]|_],_順路1)), \+(append(_,[[_都道府県名3,_都道府県名1]|_],_順路1)),!. % 以下のサイトは # 出典:: http://hibari.2ch.net/test/read.cgi/tech/1296387672/337 # # [1] 授業単元:プログラミング # [2] 問題文(含コード&リンク):次の書きこみにまとめます。 # # 地図データmap.dat に対して、出発点の交差点番号をキーボードから入力すると、 # A. 隣接する交差点名と交差点番号および出発点からの距離をディスプレイに表示 # する # B. 表示された交差点の中から次に進む交差点を選択できる # C. 選択された交差点に対して、A. の手順に戻り、順々に道案内する # プログラムを作成しなさい。手順A の距離は、出発点からの直線距離ではなく、 # 経路の累計移動距離を計算すること。また、プログラムを途中で終了させるコマ # ンドも用意すること。 # # # という問題について次のようなソースを書いたのですが、これでは経路の累計移動距離が計算されないため、不十分だと言われました。 # http://ime.nu/codepad.org/1hcQfHlM # 地図データはこちらに上げてあります # http://ime.nu/www1.axfc.net/uploader/Sc/so/202935.dat # どこをどう直せばいいのか、どなたかお願いします # # 1, 0.0, 0.0, A, 2, 2, 4 # 2, -0.6, 0.15, B, 3, 1, 3, 11 # 3, -0.83, 0.0, C, 4, 2, 4, 9, 10 # 4, -0.6, -0.38, D, 3, 1, 3, 5 # 5, -0.38, -0.68, E, 3, 4, 6, 7 # 6, 6.0, -0.3, F, 1, 5 # 7, -0.18, -1.02, G, 2, 5, 8 # 8,-0.84, -1.58, H, 3, 7, 9, 18 # 9, -0.9, -0.98, I, 2, 3, 8 # 10, -0.98, 0.15, J, 3, 3, 11, 13 # 11, -0.78, 0.3, K, 3, 2, 10, 12 # 12, -1.28, 0.68, L, 2, 11, 13 # 13, -1.32, 0.53, M, 4, 10, 12, 14, 15 # 14, -1.8, 0.98, N, 2, 13, 20 # 15, -1.43, -0.15, O, 2, 13, 16 # 16, -1.73, -0.26, P,3, 15, 17, 20 # 17, -1.8, -1.43, Q, 3, 16, 18, 19 # 18, -1.2, -1.73, R, 2, 8, 17 # 19, -2.48, -1.2, S, 2, 17, 20 # 20, -2.33, -0.51, T, 3, 14, 16, 19 交差点を進む(_出発交差点,_移動記録,_移動累積距離) :- 地図データを読み込む(_地図データ), 地図データの登録(_地図データ), 交差点を進む(_出発交差点,0.0,[],_移動記録,_移動累積距離). 交差点を進む(_交差点,_移動記録1,_移動累積距離1,_移動記録,_移動累積距離) :- 隣接交差点を表示する(_交差点), write_formatted('ここまでの移動累積距離は%tです\n',[_移動累積距離1]), write('どの交差点に進みますか ? '), get_line(_隣接交差点), 隣接交差点との距離(_交差点,_隣接交差点,_距離), _移動累積距離2 is _距離 + _移動累積距離1, 交差点を進む(_交差点,[_隣接交差点|_移動記録1],_移動累積距離2,_移動記録,_移動累積距離). 交差点を進む(_交差点,_移動記録,_移動累積距離,_移動記録,_移動累積距離) :- write_formatted('交差点%tは存在しません\nここまでの移動累積距離は%tでした\nプログラムを終了します\n',[_交差点,_累積移動距離]). 隣接交差点を表示する(_交差点) :- findall(_隣接交差点,隣接交差点(_交差点,_隣接交差点),_隣接交差点ならび), \+(_隣接交差点ならび=[]), concat_atom(_隣接交差点ならび,',',_隣接交差点表示), write_formatted('隣接交差点は %t があります\n',[_隣接交差点表示]). 隣接交差点との距離(_交差点,_隣接交差点,_距離) :- 交差点位置(_交差点,X1,Y1), 隣接交差点(_交差点,X2,Y2), _距離 is sqrt((X2 - X1) ^2 + (Y2 - Y1) ^ 2). 地図データを読み込む(_地図データ) :- get_split_lines('map.dat',[','],LL). 地図データの登録(_地図データ) :- 交差点位置の登録(_地図データ), 隣接交差点の登録(_地図データ). 交差点位置の登録(_地図データ) :- abolish(交差点位置/3), append(_,[[_,X,Y,_交差点|_]|R],_交差点データ), assertz(交差点位置(_交差点,X,Y)), R = []. 隣接交差点の登録(_地図データ) :- abolish(隣接交差点/2), append(_,[[_交差点ID,_,_,_交差点|_隣接交差点ならび]|R],_地図データ), 隣接交差点を得る(_地図データ,_隣接交差点IDならび,_隣接交差点), assertz(隣接交差点(_交差点,_隣接交差点)), R = []. 隣接交差点を得る(_地図データ,[_隣接交差点ID|R],_隣接交差点) :- list_nth(_隣接交差点ID,_地図データ,[_,_,_,_隣接交差点|_]). 隣接交差点を得る(_地図データ,[_|R],_隣接交差点) :- 隣接交差点を得る(_地図データ,R,_隣接交差点). % 以下のサイトは % % http://pc12.2ch.net/test/read.cgi/tech/1242655611/809 % % <問題>> % http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/9353.txt % %  バックトラッキング法 % % 問題を解く過程が段階的に分かれており、各段階で次に進む選択肢が複数あるという問題は多々ある。各段階で判定を下すときは、 % 適当に選びずっと先の段階まで行って、その時の選択が間違っていたことが判って時点で、この段階まで逆戻りして異なる選択をする。 % 囲碁将棋の「待った」である。このような方法で正しい解を見つけるやり方をバックトラッキング法 % という。この解決の実装にはスタックが用いられることが多い。 % % そこで今回は2題問題を挙げる。 % % 題1 騎士の巡回問題 %     %    西洋のチェスは8×8枡の盤にいろいろな駒が置かれている。騎士の駒は日本の将棋の斜め前に進む桂馬に似ているが、斜め後ろにも %    戻れるところは異なっている。盤のKの位置に騎士いるときに、次に進むことができる位置は、図の0のところどれでも良い。 % % % %     %        +−−+−−+−−+−−+−−+−−+−−+−−+ %        |  |  |  |  |  |  |  |  | %        +−−+−−+−−+−−+−−+−−+−−+−−+ %        |  |  | O |  | O |  |  |  | %        +−−+−−+−−+−−+−−+−−+−−+−−+ %        |  | O |  |  |  | O |  |  | %        +−−+−−+−−+−−+−−+−−+−−+−−+ %        |  |  |  | K |  |  |  |  | %        +−−+−−+−−+−−+−−+−−+−−+−−+ %        |  | O |  |  |  | O |  |  | %        +−−+−−+−−+−−+−−+−−+−−+−−+ %        |  |  | O |  | O |  |  |  | %        +−−+−−+−−+−−+−−+−−+−−+−−+ %        |  |  |  |  |  |  |  |  | %        +−−+−−+−−+−−+−−+−−+−−+−−+ %         % 問題はある位置から出発してすべての位置を一回だけ訪れる方法が何種類あるかを求めること。つまり、一筆書きで全ての升目を通る方法が何回あるか。 % %    この問題を8×8枡でやると解がとてつもなくあるので盤を5×5枡に制限し、最初の位置をAとします。 % % % % %        +−−+−−+−−+−−+−−+ %        | A |  |  |  |  | %        +−−+−−+−−+−−+−−+ %        |  |  |  |  |  |  %        +−−+−−+−−+−−+−−+ %        |  |  |  |  |  | %        +−−+−−+−−+−−+−−+ %        |  |  |  |  |  | %        +−−+−−+−−+−−+−−+ %        |  |  |  |  |  | %        +−−+−−+−−+−−+−−+ % % 最後に求まった盤の状況(訪れた順に番号を入れる)を印字し、全部の解答数を報告すること。 % % % % %  題2 再帰法による解法 %      おなじ問題をスタックを用いずに再帰プログラムで書きなさい。 % % 可能経路数(_桝,_開始点_X,_開始点_Y,_経路の数) :- 開始点は桝の中にある(_桝,_開始点_X,_開始点_Y), 度数(駒の動き(_桝,_開始点_X,_開始点_Y,_),_経路の数). 開始点は桝の中にある(_桝,_開始点_X,_開始点_Y) :- between(1,_桝,_開始点_X), between(1,_桝,_開始点_Y). 駒の動き(_桝,_開始点_X,_開始点_Y,_経路) :- 駒の動き(_桝,_開始点_X,_開始点_Y,[[_開始点_X,_開始点_Y]],_経路). 駒の動き(_桝,X,Y,L,_経路) :- 移動可能点(_桝,X,Y,X2,Y2), \+(member([X2,Y2],L)), 駒の動き(_桝,X2,Y2,[[X2,Y2]|L],_経路). 駒の動き(_桝,X,Y,L,_経路) :- 全ての升目を通過した(_桝,L,_経路). 変位(2,1). 変位(1,2). 変位(-1,2). 変位(-2,1). 変位(-2,-1). 変位(-1,-2). 変位(1,-2). 変位(2,-1). 移動可能点(_桝,I,J,X,Y) :- 変位(U,W), X is I+U, Y is J+W, 'X,Yは盤面上'(X,Y,_桝). 'X,Yは盤面上'(X,Y,_桝) :- X > 0, X =< _桝, Y > 0, Y =< _桝. 全ての升目を通過した(_桝,L,_経路) :- _桝2 is _桝 * _桝, length(L,_桝2), reverse(L,_経路). 度数(_副目標,_度数) :- findall(1,_副目標,L), length(L,_度数). % 以下のサイトは # 出典:: http://hibari.2ch.net/test/read.cgi/tech/1086272325/886 # # 木に一本だけ辺をつけ加えて最長となる閉路を探すアルゴリズム # 木に一本だけ辺をつけ加えて最長となる閉路を探す(_根,_辺起点,_辺終点) :- findall([_深さ,_葉に至る経路],( 葉を捜す(_根,_葉に至る経路), length(_葉に至る経路,_深さ)), LL1), sort(LL1,LL2), reverse(LL2,LL3), 一本辺をつけ加えて閉路とする(LL3,_辺起点,_辺終点). 葉を捜す(_根,[_根|R]) :- 木(_根,_葉), 葉を捜す(_葉,R). 葉を捜す(_根,[]). 一本辺をつけ加えて閉路とする([[N,L1],[N,L2]|R],_辺起点,_辺終点) :- findall(_葉,( member([N,L],[[N,L1],[N,L2]|R]), last(L,_葉)), _葉ならび), 組合せ(_葉ならび,2,[_辺起点,_辺終点]). 一本辺をつけ加えて閉路とする([[N1,L1],[N2,L2]|R],_辺起点,_辺終点) :- \+(N1 = N2), last(L1,_辺起点), member([N2,L],[[N2,L2]|R]), last(L,_辺終点). % 以下のサイトは # # 図.1のような。格子状の経路があるとします。 # (1) このときPからQまでいくのに何通りの経路があるか数えてください。 # (2) (1)と条件は同じで、図.2のように経路の一部がない(通れない)場合に、PからQまでいくのに何通りの経路があるか数えてください。 # P-+-+-+ P-+-+-+ # | | | | | | | | # +-+-+-+ +-+-+-+ # | | | | | | | # +-+-+-+ +-+-+ + # | | | | | | | | # +-+-+-+ +-+ +-+ # | | | | | | | | # +-+-+-Q +-+-+-Q # 図.1 図.2 # 経路の表現の仕方、記憶の仕方は自由とします。上記のようなキャラクタでの表現でもよいですし、最初からプログラムで扱いやすいデータとして持っていてもOKです。入力も外部からの入力でもよいですし、プログラム中にコーディングされていてもOKです。 # 出発点(あ). 終着点(と). 接続(あ,い). 接続(あ,お). 接続(い,う). 接続(い,か). 接続(う,え). 接続(う,き). 接続(え,お). 接続(え,く). 接続(お,か). 接続(お,け). 接続(か,き). 接続(か,こ). 接続(き,く). 接続(き,さ). 接続(く,し). 接続(す,せ). 接続(す,ち). 接続(せ,そ). 接続(せ,つ). 接続(そ,た). 接続(そ,と). 接続(た,と). 接続(ち,つ). 接続(つ,て). 接続(て,と). 接続(い,あ). 接続(お,あ). 接続(う,い). 接続(か,い). 接続(え,う). 接続(き,う). 接続(お,え). 接続(く,え). 接続(か,お). 接続(け,お). 接続(き,か). 接続(こ,か). 接続(く,き). 接続(さ,き). 接続(し,く). 接続(せ,す). 接続(ち,す). 接続(そ,せ). 接続(つ,せ). 接続(た,そ). 接続(と,そ). 接続(と,た). 接続(つ,ち). 接続(て,つ). 接続(と,て). 完全格子で全方向移動可の道順は何通り(_何通り) :- 度数(道順(_),_何通り). 道順(_道順) :- 出発点(_出発点), 終着点(_終着点), 道順(_出発点,_終着点,[],_道順). 道順(_点,_隣接点,_履歴,[_点,_隣接点]) :- 接続(_点,_隣接点), \+(member([_点,_隣接点],_履歴)), \+(member([_隣接点,_点],_履歴)). 道順(_点,_終着点,_履歴,[_点|R]) :- 接続(_点,_隣接点), \+(member([_点,_隣接点],_履歴)), \+(member([_隣接点,_点],_履歴)), 道順(_隣接点,_終着点,[[_点,_隣接点]|_履歴],R). % 度数/2 % 以下のサイトは # # 図.1のような。格子状の経路があるとします。 # (1) このときPからQまでいくのに何通りの経路があるか数えてください。 # (2) (1)と条件は同じで、図.2のように経路の一部がない(通れない)場合に、PからQまでいくのに何通りの経路があるか数えてください。 # P-+-+-+ P-+-+-+ # | | | | | | | | # +-+-+-+ +-+-+-+ # | | | | | | | # +-+-+-+ +-+-+ + # | | | | | | | | # +-+-+-+ +-+ +-+ # | | | | | | | | # +-+-+-Q +-+-+-Q # 図.1 図.2 # 経路の表現の仕方、記憶の仕方は自由とします。上記のようなキャラクタでの表現でもよいですし、最初からプログラムで扱いやすいデータとして持っていてもOKです。入力も外部からの入力でもよいですし、プログラム中にコーディングされていてもOKです。 # 出発点(あ). 終着点(と). 接続(あ,い). 接続(あ,お). 接続(い,う). 接続(い,か). 接続(う,え). 接続(う,き). 接続(え,く). 接続(お,か). 接続(お,け). 接続(か,き). 接続(き,く). 接続(き,さ). 接続(く,し). 接続(け,こ). 接続(け,す). 接続(こ,さ). 接続(こ,せ). 接続(さ,そ). 接続(し,た). 接続(す,せ). 接続(す,ち). 接続(せ,つ). 接続(そ,た). 接続(ち,つ). 接続(つ,て). 接続(て,と). 接続(い,あ). 接続(お,あ). 接続(う,い). 接続(か,い). 接続(え,う). 接続(き,う). 接続(く,え). 接続(か,お). 接続(け,お). 接続(き,か). 接続(く,き). 接続(さ,き). 接続(し,く). 接続(こ,け). 接続(す,け). 接続(さ,こ). 接続(せ,こ). 接続(そ,さ). 接続(た,し). 接続(せ,す). 接続(ち,す). 接続(つ,せ). 接続(た,そ). 接続(つ,ち). 接続(て,つ). 接続(と,て). 通れない通路ありの全方向移動可の道順は何通り(_何通り) :- 度数(道順(_),_何通り). 道順(_道順) :- 出発点(_出発点), 終着点(_終着点), 道順(_出発点,_終着点,[],_道順). 道順(_点,_隣接点,_履歴,[_点,_隣接点]) :- 接続(_点,_隣接点), \+(member([_点,_隣接点],_履歴)), \+(member([_隣接点,_点],_履歴)). 道順(_点,_終着点,_履歴,[_点|R]) :- 接続(_点,_隣接点), \+(member([_点,_隣接点],_履歴)), \+(member([_隣接点,_点],_履歴)), 道順(_隣接点,_終着点,[[_点,_隣接点]|_履歴],R). % 度数/2 % 以下のサイトは # # 図.1のような。格子状の経路があるとします。 # (1) このときPからQまでいくのに何通りの経路があるか数えてください。ただし遠回りはせずかならずQに近づく方向に進む(右方向か下方向にだけ進む)とします。 # (2) (1)と条件は同じで、図.2のように経路の一部がない(通れない)場合に、PからQまでいくのに何通りの経路があるか数えてください。 # P-+-+-+ P-+-+-+ # | | | | | | | | # +-+-+-+ +-+-+-+ # | | | | | | | # +-+-+-+ +-+-+ + # | | | | | | | | # +-+-+-+ +-+ +-+ # | | | | | | | | # +-+-+-Q +-+-+-Q # 図.1 図.2 # 経路の表現の仕方、記憶の仕方は自由とします。上記のようなキャラクタでの表現でもよいですし、最初からプログラムで扱いやすいデータとして持っていてもOKです。入力も外部からの入力でもよいですし、プログラム中にコーディングされていてもOKです。 # 出発点(あ). 終着点(と). 接続(あ,い). 接続(あ,お). 接続(い,う). 接続(い,か). 接続(う,え). 接続(う,き). 接続(え,お). 接続(え,く). 接続(お,か). 接続(お,け). 接続(か,き). 接続(か,こ). 接続(き,く). 接続(き,さ). 接続(く,し). 接続(す,せ). 接続(す,ち). 接続(せ,そ). 接続(せ,つ). 接続(そ,た). 接続(そ,と). 接続(た,と). 接続(ち,つ). 接続(つ,て). 接続(て,と). 完全格子で右または下へのみ移動の道順は何通り(_何通り) :- 度数(道順(_),_何通り). 道順(_道順) :- 出発点(_出発点), 終着点(_終着点), 道順(_出発点,_終着点,_道順). 道順(_点,_隣接点,[_点,_隣接点]) :- 接続(_点,_隣接点). 道順(_点,_終着点,[_点|R]) :- 接続(_点,_隣接点), 道順(_隣接点,_終着点,R). % 度数/2 % 以下のサイトは # # 図.1のような。格子状の経路があるとします。 # (1) このときPからQまでいくのに何通りの経路があるか数えてください。ただし遠回りはせずかならずQに近づく方向に進む(右方向か下方向にだけ進む)とします。 # (2) (1)と条件は同じで、図.2のように経路の一部がない(通れない)場合に、PからQまでいくのに何通りの経路があるか数えてください。 # P-+-+-+ P-+-+-+ # | | | | | | | | # +-+-+-+ +-+-+-+ # | | | | | | | # +-+-+-+ +-+-+ + # | | | | | | | | # +-+-+-+ +-+ +-+ # | | | | | | | | # +-+-+-Q +-+-+-Q # 図.1 図.2 # 経路の表現の仕方、記憶の仕方は自由とします。上記のようなキャラクタでの表現でもよいですし、最初からプログラムで扱いやすいデータとして持っていてもOKです。入力も外部からの入力でもよいですし、プログラム中にコーディングされていてもOKです。 # 出発点(あ). 終着点(と). 接続(あ,い). 接続(あ,お). 接続(い,う). 接続(い,か). 接続(う,え). 接続(う,き). 接続(え,く). 接続(お,か). 接続(お,け). 接続(か,き). 接続(き,く). 接続(き,さ). 接続(く,し). 接続(け,こ). 接続(け,す). 接続(こ,さ). 接続(こ,せ). 接続(さ,そ). 接続(し,た). 接続(す,せ). 接続(す,ち). 接続(せ,つ). 接続(そ,た). 接続(ち,つ). 接続(つ,て). 接続(て,と). 通れない通路ありで右または下のみ移動可の道順は何通り(_何通り) :- 度数(道順(_),_何通り). 道順(_道順) :- 出発点(_出発点), 終着点(_終着点), 道順(_出発点,_終着点,_道順). 道順(_点,_隣接点,[_点,_隣接点]) :- 接続(_点,_隣接点). 道順(_点,_終着点,[_点|R]) :- 接続(_点,_隣接点), 道順(_隣接点,_終着点,R). % 度数/2 % 以下のサイトは # # 述語経路/2を定義するための述語 経路定義/1 を定義しなさい。 # # 仕様として図.2のような格子状グラフが述語'図2.1'で定義されています。 # これを図.2.2で表されるグラフに対応する 述語 経路/1として定義します。 # 節の名称は"あ-と"を述語 節の命名順/1 の引数リストから受け取って # 順に振っていきます。 # # P-+-+-+ あーいーうーえ # | | | | | | | |  # +-+-+-+ おーかーきーく # | | | |   | | # +-+-+ + けーこーさ し # | | | | | | | | # +-+ +-+ すーせ そーた # | | | | | | | | # +-+-+-Q ちーつーてーと # # 図.2 図.2.2 # # この図.2から 図.2.2 に対応する述語 経路/2 を以下のように定義するための # 述語を定義します。 # # 経路(あ,い). # 経路(あ,お). # 経路(い,う). # 経路(い,か). # 経路(う,え). # 経路(う,き). # 経路(え,く). # 経路(お,か). # 経路(お,け). # 経路(か,き). # 経路(き,く). # 経路(き,さ). # 経路(く,し). # 経路(け,こ). # 経路(け,す). # 経路(こ,さ). # 経路(こ,せ). # 経路(さ,そ). # 経路(し,た). # 経路(す,せ). # 経路(す,ち). # 経路(せ,つ). # 経路(そ,た). # 経路(ち,つ). # 経路(つ,て). # 経路(て,と). # 節の命名順([あ,い,う,え,お,か,き,く,け,こ,さ,し,す,せ,そ,た,ち,つ,て,と]). '図.2.1'([['P',-,+,-,+,-,+], ['|',' ','|',' ','|',' ','|'], [+,-,+,-,+,-,+], ['|',' ',' ',' ','|',' ','|'], [+,-,+,-,+,' ',+], ['|',' ','|',' ','|',' ','|'], [+,-,+,' ',+,-,+], ['|',' ','|',' ','|',' ','|'], [+,-,+,-,+,-,'Q']]). % '図.2.1'([['あ',-,い,-,う,-,え], % ['|',' ','|',' ','|',' ','|'], % [お,-,か,-,き,-,く], % ['|',' ',' ',' ','|',' ','|'], % [け,-,こ,-,さ,' ',し], % ['|',' ','|',' ','|',' ','|'], % [す,-,せ,' ',そ,-,た], % ['|',' ','|',' ','|',' ','|'], % [ち,-,つ,-,て,-,と]]). 接続定義 :- '図.2.1'(_グラフ), 節に名前を振る(_グラフ,_命名された節をもつグラフ), 接続定義(_命名された節をもつグラフ). 節に名前を振る(_グラフ,_命名された節をもつグラフ) :- 節の命名順(_節の命名順), 節に名前を振る(_グラフ,_節の命名順,_命名された節をもつグラフ). 節に名前を振る([],_,[]). 節に名前を振る([L1|R1],L2,[L1_2|R3]) :- 節に名前を振る(L1,L2,R,L1_2), 節に名前を振る(R1,R,R3). 節に名前を振る([],R2,R2,[]). 節に名前を振る(['P'|R1],[A|R2],R,[A|R4]) :- assertz(出発点(A)), 節に名前を振る(R1,R2,R,R4). 節に名前を振る(['Q'|R1],[A|R2],R,[A|R4]) :- assertz(終着点(A)), 節に名前を振る(R1,R2,R,R4). 節に名前を振る(['+'|R1],[A|R2],R,[A|R4]) :- 節に名前を振る(R1,R2,R,R4),!. 節に名前を振る([' '|R1],L2,R,[' '|R4]) :- 節に名前を振る(R1,L2,R,R4),!. 節に名前を振る([_記号|R1],L2,R,[_記号|R4]) :- 節に名前を振る(R1,L2,R,R4). 右と下両方向の接続定義(_命名された節をもつグラフ) :- 接続定義(_命名された節をもつグラフ), 転置(_命名された節をもつグラフ,_転置された命名された節をもつグラフ), 接続を定義する(_転置された命名された節をもつグラフ). 接続定義([]) :- !. 接続定義([L|R]) :- 一列の接続の定義(L), 接続定義(R). 一列の接続の定義([]). 一列の接続の定義([A,-,C|R]) :- \+(空白か記号(A)), \+(空白か記号(C)), assertz(接続(A,B)), 一列の接続の定義([C|R]),!. 一列の接続の定義([A,'|',C|R]) :- \+(空白か記号(A)), \+(空白か記号(C)), assertz(接続(A,B)), 一列の接続の定義([C|R]),!. 一列の接続定義([A|R]) :- 接続の定義(R). 空白か記号(' ') :- !. 空白か記号(A) :- member(A,[-,'|']). % 以下のサイトは # 出典:: http://toro.2ch.net/test/read.cgi/tech/1276873238/771 # # 【 課題 】迷路の最短経路を与えるプログラムを考えよ. # 壁は#, 通路は.で表されている. # また迷路の外側は全て壁(即ち#)となっている. # スタート地点はS, ゴール地点はGである. # スタートからゴールまでの道のりを表わせ. # 上へ移動する場合にはu, 同様に下はd, 右はr, 左はlとせよ. # 最短経路が複数ある場合は, それらのうちどれかひとつを出力せよ。 # # 例1) # ####### # #..S..# # #.....# # #..G..# # ####### # 答え) # dd # # 例2) # ####### # #.....# # #.G.#.# # #..#..# # #.#.S.# # #.....# # ####### # 答え) # ldlluuru # 最短経路(_迷路文字列ならび,_最短経路) :- 迷路の定義(_迷路文字列ならび), 出発点(Y0,X0), findmin([_距離,_経路],( 道に迷う([[Y0,X0]],Y0,X0,_方向ならび), length(_方向ならび,_距離), atom_chars(_経路,_方向ならび)), [_,_最短経路]). 道に迷う(_,Y,X,[]) :- 終着点(Y,X). 道に迷う(_既に通過した点ならび,Y_1,X_1,[_方向|R]) :- 隣接点を得る(_既に通過した点ならび,Y_1,X_1,Y_2,X_2,_方向), 道に迷う([[Y_2,X_2]|_既に通過した点ならび],Y_2,X_2,R). 隣接点を得る(_既に通過した点ならび,Y_1,X_1,Y_2,X_2,_方向) :- member([_方向,A,B],[[r,1,0],[l,-1,0],[d,0,1],[u,0,-1]]), Y_2 is Y_1 + B, X_2 is X_1 + A, 道(Y_2,X_2), \+(member([Y_2,X_2],_既に通過した点ならび)). 迷路の定義(_行文字列ならび) :- append(L0,[_行文字列|R],_行文字列ならび), length(L0,Y), sub_atom(_行文字列,X,1,_,_点), 迷路の道部分の点定義(_点,Y,X), R = []. 迷路の道部分の定義(_点,Y,X) :- '道ならば位置を定義'(_点,Y,X), '出発点・終着点ならば位置を定義'(_点,Y,X),!. 迷路の道部分の定義(_,_,_). '出発点・終着点ならば位置を定義'('S',Y,X) :- assertz(出発点(Y,X)),!. '出発点・終着点ならば位置を定義'('G',Y,X) :- assertz(終着点(Y,X)),!. 道ならば位置を定義(A,Y,X) :- \+(A = '#'), assertz(道(Y,X)). % 以下のサイトは ダイクストラ法による最短距離探索(_出発点,_距離,_最短経路,_確定集合) :- _確定集合_1 = [[_出発点,0,[_出発点]]], 初期の未確定集合を得る(_出発点,_未確定集合), ダイクストラ法による最短距離探索(_確定集合_1,_未確定集合,_確定集合). 初期の未確定集合を得る(_出発点,_初期未確定集合) :- findsetof([_出発点,9999,[]],( 経路(_点,_,_), \+(_点 = _出発点)), _初期未確定集合). ダイクストラ法による最短距離探索(_確定集合,[],_確定集合). ダイクストラ法による最短距離探索([[_直前に確定した点,_距離,_経路]|R],_未確定集合_1,_確定集合) :- 直前に確定した点から全ての隣接点の未確定集合を更新する(_直前に確定した点,_距離,_経路,_未確定集合_1,_未確定集合_2), 未確定集合から最小距離点を抜き取る(_未確定集合_2,_最小距離点,_最小距離,_最小距離点の経路,_未確定集合_3), 確定集合に追加(_最小距離点,_最小距離,_最小経路点の経路,[[_直前に確定した点,_距離,_経路]|R],_確定集合_2), ダイクストラ法による最短距離探索(_確定集合_2,_未確定集合_3,_確定集合). 直前に確定した点から全ての隣接点の未確定集合を更新する(_直前に確定した点,_距離,_経路,_未確定集合_1,_未確定集合_2) :- findall([_隣接点,_距離], 隣接点を得る(_直前に確定した点,_未確定集合,_隣接点,_距離), LL), 直前に確定した点から全ての隣接点の未確定集合を更新する(_直前に確定した点,_距離,_経路,LL,_未確定集合_1,_未確定集合_2). 直前に確定した点から全ての隣接点の未確定集合を更新する(_直前に確定した点,_直前に確定した点までの距離,_直前に確定した点までの経路,[[_隣接点,_距離]|R],_未確定集合_1,_未確定集合_2) :- 未確定集合の更新(_直前に確定した点,_直前に確定した点までの距離,_直前に確定した点までの経路,_隣接点,_距離,_未確定集合_1,_未確定集合_3), 直前に確定した点から全ての隣接点の未確定集合を更新する(_直前に確定した点,_直前に確定した点までの距離,_直前に確定した点までの経路,R,_未確定集合_3,_未確定集合_2). 隣接点を得る(_直前に確定した点,_未確定集合,_隣接点,_距離) :- 経路(_直前に確定した点,_隣接点,_距離), member([_隣接点,_,_],_未確定集合). 未確定集合の更新(_直前に確定した点,_直前に確定した点までの距離,_直前に確定した点までの経路,_隣接点,_距離,_未確定集合_1,_未確定集合_2) :- _距離_2 is _直前に確定した点までの距離 + _距離, append(L1,[[_隣接点,_距離_1,_経路_1]|L2],_未確定集合_1), _距離_1 > _距離_2, append(L1,[[_隣接点,_距離_1,[_隣接点|_直前に確定した点までの経路]]|L2],_未確定集合_2),!. 未確定集合の更新(_,_,_,_,_,_未確定集合,_未確定集合). 未確定集合から最小距離点を抜き取る(_未確定集合_1,_最小距離点,_最小距離,_最小距離点の経路,_未確定集合_2) :- append(L1,[[_最小距離点,_最小距離,_最小距離の経路]|L2],_未確定集合_1), forall(member([_,_距離_1,_],L1),_距離_1 >= _最小距離), forall(member([_,_距離_2,_],L1),_距離_2 >= _最小距離), append(L1,L2,_未確定集合_2),!. 確定集合に追加(_点,_距離,_経路,_確定集合_1,[[_点,_距離,_経路]|_確定集合_1]). findsetof(A,B,L) :- findall(A,B,C), setof(A,member(A,C),L). % 以下のサイトは # お題:下の端に一本だけ当たりが付いているあみだくじについて、 # 当たりくじを引く手を求めよ。橋と橋の交差はないと仮定する。 # 入力データ:くじの本数num。左から数えた当たりくじの位置mark。各橋の両端のくじの位置(left,right)を上から並べたリスト。 # 'お題:下の端に一本だけ当たりが付いているあみだくじについて、 当たりくじを引く手を求めよ。橋と橋の交差はないと仮定する。 入力データ:くじの本数num。左から数えた当たりくじの位置mark。各橋の両端のくじの位置(left,right)を上から並べたリスト。'(_くじの本数,_当たり) :- あみだくじ(_くじの本数,_当たり). 経路((1,1),(1,2)). 経路((1,2),(1,3)). 経路((1,2),(2,3)). 経路((2,1),(2,2)). 経路((2,2),(2,3)). 経路((2,3),(2,4)). 経路((2,2),(3,2)). 経路((3,1),(3,2)). 経路((3,2),(3,3)). ゴール((1,3)). ゴール((2,4)). ゴール((3,3)). 当たりくじ((2,4)). あみだくじ(_くじの本数,_当たり) :- between(1,_くじの本数,_当たり), 経路((_当たり,1),_次の点), あみだくじ(_次の点). あみだくじ(_現在点) :- ゴール(_現在点),!. あみだくじ(_現在点) :- 次の点(_現在点,_次の点), あみだくじ(_現在点). 次の点(_現在点,_次の点) :- 左から右へ橋を渡る(_現在点,_次の点),!. 次の点(_現在点,_次の点) :- 右から左へ橋を渡る(_現在点,_次の点),!. 次の点(_現在点,_次の点) :- 下方へ移動する(_現在点,_次の点). 左から右へ橋を渡る((X,Y),(X_2,Y_2)) :- 経路((X,Y),(X_2,Y_2)), \+(X = X_2),!. 右から左へ橋を渡る((X,Y),(X_2,Y_2)) :- 経路((X_2,Y_2),(X,Y)), \+(X = X_2),!. 下方へ移動する((X,Y),(X,Y_2)) :- 経路((X,Y),(X,Y_2)), Y_2 > Y.