「鉄道のスケジューリングアルゴリズム」という本を買って読んでいます。
その中で以下のような簡単な巡回セールスマン問題があったのでPrologでさくっと解いてみました。
あなたの会社は東京にある。札幌、大阪、博多、那覇にそれぞれクライアントを抱えており、それぞれの都市間の距離は以下である。
東京から出発してクライアント全員を１回づつ訪問し、東京に戻らなければいけない。このとき、移動距離の総和が2900km以下であるような経路は存在するだろうか？
sapporo-tokyo,511km
sapporo-osaka,667km
sapporo-hakata,883km
sapporo-naha,1398km
tokyo-osaka,278km
tokyo-hakata,566km
tokyo-naha,984km
osaka-hakata,289km
osaka-naha,740km
hakata-naha,537km
プログラム
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
distance(sapporo,tokyo,511):-!. distance(sapporo,osaka,667):-!. distance(sapporo,hakata,883):-!. distance(sapporo,naha,1398):-!. distance(tokyo,osaka,278):-!. distance(tokyo,hakata,566):-!. distance(tokyo,naha,984):-!. distance(osaka,hakata,289):-!. distance(osaka,naha,740):-!. distance(hakata,naha,537):-!. distance(X,Y,Dist):-distance(Y,X,Dist),!. solve_salesman:- Cities = [sapporo,osaka,hakata,naha], make_houmonjun(Cities,HoumonLstInit), append([tokyo],HoumonLstInit,HoumonLst2), append(HoumonLst2,[tokyo],HoumonLst3), calc_distance(HoumonLst3,Distance), write(HoumonLst3),write(' '),write(Distance),nl, Distance =< 2900, write('Success! Houmonjun:'),write(HoumonLst),write(' distance:'),write(Distance). make_houmonjun([],[]):-!. make_houmonjun(Cities,[SelectedCity|RestSelected]):- select(SelectedCity,Cities,RestCities), make_houmonjun(RestCities,RestSelected). calc_distance([_],0):-!. calc_distance([FirstCity,SecondCity | RestCities],DistSum):- !, distance(FirstCity,SecondCity,CurrentDistance), calc_distance([SecondCity | RestCities],OtherDistSum), DistSum is CurrentDistance + OtherDistSum. |
実行結果
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
[4] 27 ?- solve_salesman. 3 ?- solve_salesman. [tokyo,sapporo,osaka,hakata,naha,tokyo] 2988 [tokyo,sapporo,osaka,naha,hakata,tokyo] 3021 [tokyo,sapporo,hakata,osaka,naha,tokyo] 3407 [tokyo,sapporo,hakata,naha,osaka,tokyo] 2949 [tokyo,sapporo,naha,osaka,hakata,tokyo] 3504 [tokyo,sapporo,naha,hakata,osaka,tokyo] 3013 [tokyo,osaka,sapporo,hakata,naha,tokyo] 3349 [tokyo,osaka,sapporo,naha,hakata,tokyo] 3446 [tokyo,osaka,hakata,sapporo,naha,tokyo] 3832 [tokyo,osaka,hakata,naha,sapporo,tokyo] 3013 [tokyo,osaka,naha,sapporo,hakata,tokyo] 3865 [tokyo,osaka,naha,hakata,sapporo,tokyo] 2949 [tokyo,hakata,sapporo,osaka,naha,tokyo] 3840 [tokyo,hakata,sapporo,naha,osaka,tokyo] 3865 [tokyo,hakata,osaka,sapporo,naha,tokyo] 3904 [tokyo,hakata,osaka,naha,sapporo,tokyo] 3504 [tokyo,hakata,naha,sapporo,osaka,tokyo] 3446 [tokyo,hakata,naha,osaka,sapporo,tokyo] 3021 [tokyo,naha,sapporo,osaka,hakata,tokyo] 3904 [tokyo,naha,sapporo,hakata,osaka,tokyo] 3832 [tokyo,naha,osaka,sapporo,hakata,tokyo] 3840 [tokyo,naha,osaka,hakata,sapporo,tokyo] 3407 [tokyo,naha,hakata,sapporo,osaka,tokyo] 3349 [tokyo,naha,hakata,osaka,sapporo,tokyo] 2988 false. |
2900km以下の経路は存在しないようですね。
今回は経路が4!とおりで網羅が簡単だったけど、実際の問題はこれよりうんと複雑だろう。
自分は健康診断の会社で９年間働いていたのですが、いろいろな会社を回る健診バスの運行経路を決めるのは道路状況やリソース(人、機械)の問題もありかなり複雑そうでした。