このディレクトリの索引
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 _距離合計の一 + _距離,
        巡回(_都市数,_出発都市,_隣接都市の二,[_隣接都市|_巡回ならびの一],_巡回ならび,_距離合計の二,_距離合計).