GTALibでTSP

GTALibでは,ライブラリ側の提供してくれるJoinListのGeneratorが「そういう形」になっているため,それらのGeneratorを使ってればDP化及び並列化がかかる.segs,inits,tailsなどはどれも組化リスト準同型で効率的に構成でき,これらのGeneratorもそのように実装されている.TesterやAggregatorは最終的にGenerator中の演算を置き換えるようにして変換されてくるので計算の屋台骨となるGeneratorの構造は主に効率面でとっても大事だ.

では,あまり効率的でないオレオレGeneratorを使うとどうなるだろう.ためしにTSP(巡回セールスマン問題)を脳直で書いてみる.

Generatorは[1〜N番目の各頂点から他の頂点へのエッジを表現するタプル]というリストを全生成する.明らかにこのエッジの集合それぞれは全頂点を含む.その中で閉路(ひとつとは限らない)だけで構成されており,しかもエッジが連結であればそれはハミルトン閉路なので,そう搾れるようにTesterを書き,エッジ重み(=距離)和の最小値(=符号反転して最大値)を取る解を拾うAggregatorを利用してあげる.つまり,TSPの解の定義(=最小ハミルトン閉路)そのままの記述である.

結果的にGeneratorの構造がTSPのDP解法になっておらず,どちらにせよ頂点数を各コアに分散させてうれしいほどに多くはできない(=DP解法にしたところで30都市とかその程度)ので並列もまた悲しいカンジになっている.そもそもTSPのDP解法を上手くGeneratorとして書けるか?あまり深く考えてないのでだれか教えてくらさいという甘え.(´・ω・`)チカラヨワイ…

効率的なJoinList GTAのGeneratorを作るのは結構難しい.特に,短時間のコンテスト中とかに安易に自作Generatorを書き始めるとかは死亡フラグ感あるので避けたほうが良いだろう(と,江本さんも言ってたし).あなたが余程極まった運算屋でもない限り…