読者です 読者をやめる 読者になる 読者になる

nirasan's tech blog

趣味や仕事の覚え書きです。Linux, Perl, PHP, Ruby, Javascript, Android, Cocos2d-x, Unity などに興味があります。

巡回セールスマン問題をPerlで(5)

はじめに

前回で終わるつもりでしたが、CPANに既に解法があれば楽だと思って調べてみました。

まとめ

「Traveling Salesman」で検索したところ Algorithm::TravelingSalesman::BitonicTour というモジュールを見つけたので試してみました。
結果だけ先にいうと、10都市程度のデータではよい成績でしたが、50都市以上程度のデータにおいて、単純な欲張り法よりもよい成績が出せませんでした。

Algorithm::TravelingSalesman::BitonicTour を使ったスクリプト

  • ほぼSYNOPSISのままです
#!/usr/bin/perl
use strict;
use warnings;
use lib './extlib/lib/perl5';

use Algorithm::TravelingSalesman::BitonicTour;
my $bt = Algorithm::TravelingSalesman::BitonicTour->new;

while (my $line = <STDIN>) {
    chomp $line;
    my ($x, $y) = split /\s+/, $line;
    $bt->add_point($x,$y);
}

# get and print the solution
my ($len, @coords) = $bt->solve;
print "optimal path length: $len\n";
print "coordinates of optimal path:\n";
print "   ($_->[0], $_->[1])\n" for @coords;

試した結果

  • まず対象モジュールでは、Xの値が重複するポイントを二つ以上登録するとエラーになります。これは内部的にXをキーに、Yを値にしたハッシュでポイントを保持しているためのようです。
  • Xが重複しないようなデータを作成し、前回まで移植したスクリプトと性能を比較しました。データの内容と結果は以下の通りです。
結果比較表
  • 横軸は解法で、縦軸はデータ、値は距離
  • Algorithm::TravelingSalesman::BitonicTourは"BT"、移植スクリプトはオプションで記載
BT g0 g1 g0 2or g0 or2
10 684 725 688 684 684
50 2323 1781 1980 1781 1686
100 4202 2305 2404 2122 2122
比較結果
  • データ量が少なければ、"g0 2or(単純な欲張り法+2-opt法+or-opt法)"と同程度の成績だった
  • データ量が多くなるにつれ、"g0(単純な欲張り法)"にも劣るようになった
  • Xの重複を許さない点でも扱い辛いので、個人的には使うことはなさそう
データ生成コマンド
perl -e 'for (1..10)  { $h->{int(rand(300))} = int(rand(300)); } END{ for $k (keys %$h) { printf "%d %d\n", $k, $h->{$k} } }' > d10_a.txt
perl -e 'for (1..50)  { $h->{int(rand(300))} = int(rand(300)); } END{ for $k (keys %$h) { printf "%d %d\n", $k, $h->{$k} } }' > d50_a.txt
perl -e 'for (1..100) { $h->{int(rand(300))} = int(rand(300)); } END{ for $k (keys %$h) { printf "%d %d\n", $k, $h->{$k} } }' > d100_a.txt
データ
  • d10_a.txt
189 143
91 285
122 132
41 179
42 211
38 161
98 154
93 84
136 27
24 156
  • d50_a.txt
170 250
129 184
2 198
17 214
166 49
244 134
125 252
255 185
222 299
75 1
273 19
61 199
220 273
115 25
145 24
24 22
104 135
131 181
189 41
130 157
225 194
263 291
167 289
143 100
48 70
22 83
281 170
42 250
87 178
77 281
46 45
219 277
96 190
257 245
6 243
203 67
261 228
226 153
137 212
173 282
132 116
164 51
216 86
19 208
43 214
195 67
  • d100_a.txt
170 294
118 84
119 198
180 60
179 113
72 2
255 202
27 42
246 290
190 172
298 40
61 259
230 205
103 14
152 209
35 3
189 244
225 81
295 237
208 173
287 276
48 127
87 171
93 125
77 98
157 194
275 34
290 63
197 114
39 34
64 235
58 272
226 18
41 135
52 297
284 92
19 73
293 258
247 275
289 78
241 198
198 190
129 237
188 123
68 248
2 81
88 261
141 290
100 59
82 13
83 184
75 76
192 174
236 181
59 7
112 79
215 291
140 103
223 156
155 61
53 175
181 196
239 121
122 292
267 262
143 219
22 174
205 168
154 111
46 126
0 57
23 157
96 256
235 224
105 218
6 46
183 236
213 45
111 159
176 116
47 188
98 215
265 13
37 44
256 114
196 284
270 205
242 251