空間充填曲線のある組合せ論的応用

空間充填曲線のある組合せ論的応用 図1: 巡回セールスマン問題のヒューリスティック解法は、Sierpinski空間充填曲線と同じ順序で点を訪れることである。空間充填曲線は、低次元空間から高次元空間への連続的な写像である。有名な空間充填曲線はSierpinskiによるもので、単純なパターン（図1の複雑な経路）を繰り返しコピーして縮小することで形成される。空間充填曲線の有用な特性は、その領域に入ると、その領域内のすべての点を一度に訪れる傾向があることである。したがって、平面上で近い点は、曲線に沿った見た目でも近くなる傾向がある。これが、L. Platzmanと私が考案した、n個の与えられた場所の比較的短い経路（いわゆる巡回セールスマン問題）を生成するためのヒューリスティックの基礎となっている。単純に、空間充填曲線と同じ順序でそれらを訪れるだけである。例えば、赤で示された点の短い経路は、緑の線で示されており、空間充填曲線での出現順に点を結んでいる。空間充填曲線ヒューリスティック（SFC）には多くの利点がある。ただし、最適解より約25%長い解を受け入れる用意がある場合（ランダムな点の集合に対して予測される）である。これらの利点には以下が含まれる：SFCアルゴリズムは高速である：n個の点の経路を構築するのにO(n log n)の労力しかかからず、点の追加または削除による解の更新にはO(log n)の労力しかかからない。SFCヒューリスティックは、点間の明示的な距離を必要としないため、他のほとんどのヒューリスティックが計算または測定する必要があるような距離を計算または測定する必要がない。アルゴリズムは並列化可能である。（比較すると、同等のアルゴリズムであるNearest Neighborは、並列化できないようである。）ランダムな点のSFC経路におけるリンクの長さは小さく、分散も小さいと予想されるため、(1/k)番目の停止地点が移動時間の約(1/k)を占めることになる。これは、SFC経路をk個のセグメントに分割するだけで、k台の車両の経路に簡単に変換できることを意味する。空間充填曲線ヒューリスティックは、多くのアプリケーションで使用されてきた。これには以下が含まれる：ファルトン郡（ジョージア州アトランタ）のMeals-on-Wheelsのルーティングシステムを構築するために使用された。これは、自分で買い物をするには病気または高齢すぎる人々に毎日数百食を配達している。我々はこれを2つのロールデックスカードファイル上に構築した。アメリカ赤十字によるアトランタ都市圏の病院への血液配送をルーティングするために使用された。戦略防衛構想（一般に「スターウォーズ」プログラムとして知られる）のための宇宙ベースのレーザーをターゲットにするために使用された。このアプリケーションは、SDI契約業者であるTRW Systemsの科学者から伝えられたもので、彼らは空間充填曲線ヒューリスティックを、よく分析されており、並列化可能で、軌道にブースト可能なコンピュータで実行できるという理由で、代替案よりも選択した。地図を描画するためのペンプロッターを制御するために使用された。（東京大学のM. Iriらの研究グループは、ペンを効率的にルーティングすることで大規模な道路地図の描画時間を短縮する方法を示した。彼らは、描画時間が10時間から30分に短縮された例を示した。）空間充填曲線によるルーティングのアイデアは、その後、ARC/Info Geographical Information System、Baan SystemsのCAPS Logistics Toolkit、およびその他の2次元データを管理する商用システムに組み込まれた。技術的な詳細はないが、技術文献へのポインタが含まれたアイデアの概要は、私のクラスノート「空間充填曲線に基づくルーティングシステム」[PDF形式、22ページ]で見つけることができる。これに加えて、100 x 100グリッドの点のSierpinskiインデックスの表[PDF形式、22ページ]があり、これを使えば午後に独自のルーティングシステムを構築できる。アルゴリズムのパフォーマンスに関する技術的な詳細と、関連研究への引用は、「Spacefilling curves and the planar travelling salesman problem」（L. K. Platzmanとの共著、Journal of the Association for Computing Machinery 36(4):719-737 (1989)）で見つけることができる。図2：ドイツの15,112都市のTSP経路。この経路は、Sierpinski空間充填曲線によって1秒未満で生成され、最短可能な経路よりも約1/3長い。この軽量なヒューリスティックを、D. Applegate、R. Bixby、V. Chvatal、W. Cookによって開発されたようなヘビーデューティー最適化パッケージと比較するのは興味深い。彼らのTSPパッケージは、数学的最適化技術の傑作であり、15,112都市のドイツの巡回セールスマン問題を解決するために使用された。これは、証明可能な最適解が生成された最大の非自明な問題である。Applegateらは計算リソースについて説明している：「計算は、ライス大学とプリンストン大学にある110台のプロセッサのネットワーク上で行われた。計算に使用された総コンピュータ時間は、500 MHzで実行されるCompaq EV6 Alphaプロセッサにスケールすると22.6年であった。最適経路の長さは、TSPLIBで使用される単位で1,573,084であり、これはドイツを横断する約66,000キロメートルの旅行に相当する。」比較のために、Paul Goldsmanは空間充填曲線ヒューリスティックを使用して同じインスタンスを解決した。我々の解は（図2で）約34%長かった。1日あたり600 kmの移動というゆったりしたペースで考えると、総運転時間は110日に対して約147日になる。しかし、我々の計算は安価なラップトップで1秒未満で完了した。したがって、ここにトレードオフがある：我々のヒューリスティックを使用すれば、すぐにルートが得られるが、1ヶ月余分に移動する必要がある。あるいは、110台のプロセッサのネットワークを構成し、2ヶ月かけて最短ルートを計算して、1ヶ月の運転時間を節約する。図3：三角形分割不規則ネットワークのすべての点を、三角形のハミルトンパスまたは回路を見つけ、それぞれに適切に方向付けられた空間充填曲線で埋めることによって連続的にインデックス付けできる。Bill Nulty、Paul Goldsman、および私は、これらのアイデアをいくつかの方向に拡張してきた。「Robust Multidimensional Searching with Spacefilling Curves」（J. BartholdiおよびW. Nulty、Proceedings of the Sixth International Symposium on Spatial Data Handling、Edinburgh、Scotland、September 1994）、「Continuous indexing of hierarchical subdivisions of the globe」（J. BartholdiおよびP. Goldsman (2000)）。これは、Int. J. Geographical Information Science 15(6):489-522 (2001)にわずかに改訂された形式で掲載された。「Vertex-labelling algorithms for the Hilbert spacefilling curve」（J. BartholdiおよびP. Goldsman (2000)）。これは、Software -- Practice and Experience 31:395-408 (2000)にわずかに改訂された形式で掲載された。「The vertex-adjacency dual of a triangulated irregular network has a Hamiltonian cycle」（J. BartholdiおよびP. Goldsman、Operations Research Letters 32 (2004)）。Perouz Taslakianは、これらのアイデアとアルゴリズムの非常に良いイラストを作成した。最終更新：2012年8月11日木曜日17:24:53 EDT