nirasan's tech blog

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

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

perl アルゴリズム

はじめに

前回で終わるつもりでしたが、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

d50_a.txt

d100_a.txt