nirasan's tech blog

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

アルゴリズム

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

はじめに 前回で終わるつもりでしたが、CPANに既に解法があれば楽だと思って調べてみました。 まとめ 「Traveling Salesman」で検索したところ Algorithm::TravelingSalesman::BitonicTour というモジュールを見つけたので試してみました。 結果だけ先にいう…

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

はじめに 前回に引き続き、巡回セールスマン問題の解法をPythonからPerlに移植します。 今回は、greed1関数内で既存ライブラリ(List::PriorityQueue, Graph::UnionFind)を使っていた部分を、元サイトのロジックどおりに実装し直して、draw_path関数の移植を…

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

はじめに 前回に引き続き、巡回セールスマン問題の解法をPythonからPerlに移植します。 今回は、2-opt法とor-opt法の対応です。 参考サイト http://www.geocities.jp/m_hiroi/light/pyalgo64.html 「2-opt 法のプログラム」と「or-opt 法のプログラム」をPer…

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

はじめに 前回の巡回セールスマン問題をPerlで - nirasan's tech blogで、巡回セールスマン問題の解法をPythonからPerlに移植しましたが、Tkまわりは省略しました。 今回はTkのインストールとTkまわりのコードを移植を行います。 参考サイト http://www.geoc…

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

はじめに 巡回セールスマン問題の解法をPythonで解説しているサイトがあったので、Perlに移植してみたメモ。 参考サイト http://www.geocities.jp/m_hiroi/light/pyalgo62.html 「TSP を「欲張り法」で解く」をPerlで Tkまわりは省略 割とそのまま移植できた…