2013年09月05日

巡回セールスマン問題のテスト

いつの間にやら9月ですね。先月1回しか書いていない・・・。

Hopfield型ネットワークで巡回セールスマン問題[1]を解いてみたのですが、都市数をNとすると、ユニット数がN*N必要で、相互結合型ネットワークなので単純計算で各ユニットがN*N個の重みを持ちますので、計N*N*N*N個の重みが必要です。
double型で8bytes使うとすると、N*N*N*N*8bytes必要になりますので、1024都市の場合8PB(ペタバイト)ほどメモリが必要になる気がするのですが、合ってるんでしょうかね。

そんなわけで方向転換して2-opt法という良く知られているらしい方法を試してみました[2]。
最初適当に経路を作成して、その後2本直線を選んで、つなぎかえて距離が短くなるのであればつなぎかえるというとてもわかりやすいアルゴリズムです。

50都市での実行結果



500都市の実行結果

tsp_500_result.png

500都市の場合は収束しましたが、800都市以上辺りから収束しなくなりました。
原因として、短くなれば必ずつなぎかえる点などが考えられますので、温度・確率を取り入れるシミュレーティド・アニーリング法などを組み合わせればうまくいくかもしれません。
気が向いたら試してみたいと思います。

[1] http://www.eva.ie.u-ryukyu.ac.jp/~endo/HFTSP.pdf
[2] http://www.geocities.jp/m_hiroi/light/pyalgo64.html
web拍手 by FC2
posted by シンドラー at 17:42 | Comment(0) | TrackBack(0) | Computational Geometry | このブログの読者になる | 更新情報をチェックする

2013年06月23日

計算幾何学の勉強 その1

点群からメッシュ作成を何となく自分でやってみたくなったので[1]を買ってきました。
自分でやらずに既存のライブラリを使った方が速くて良いものができると思います。

本から式とかアルゴリズムって引用していいんでしょうか。
とりあえず引用なしで書いてみます。

1章

凸包を計算する場合、点群から構成される全ての直線において、直線以外の全ての点に対して左側に折れるか折れないかをチェックしていって、全て左側に折れなければその直線は凸包を構成する直線である、ということだそうです。
確かに直線から見て左に折れない、ということは一番外側の直線なのでそうなるみたいですね。
左側にあるかどうかは、直線を構成する2点p1, p2と、それ以外のある点p3からつくることができる行列の行列式が0より大きければ左側に折れ、0以下の場合は左側に折れないそうです。

実行結果

geometry_001.png

適当な7点でやってみましたが、同一直線状の3点など退化した状態ではうまくいかない場合があるようです。
2章ではその対策として、整数帰着法と記号摂動法というものを使った超ロバスト計算原理が説明されています。

実行結果

geometry_000.png

読んでもわからないところは適当に実装したので合っているのかどうかわかりませんが、一応直線状にある場合でも凸包が計算できました。

3章は省略

4章 ボロノイ図とドロネー図

三角形分割などでよく聞く名前ですね。
まずはある3点p1, p2, p3とある1点pに対する関数Gを定義しています。
このGが0の場合は3点p1, p2, p3が作る円上に点pがあり、G<0の場合は内部に点pが存在するそうです。

実行結果

geometry_002.png

黒が3点で構成される三角形で、画像上の画素に対してG≦0のところを赤、それ以外を白にしています。
また、3点から計算できるボロノイ点(円の中心)を緑色の点で表し、そこから三角形への垂直二等分線を青色で表示しています。

とりあえず3点だけの場合はできたので、これから点が増えた場合のボロノイ図の作り方を試していきたいと思います。

[1] 杉原厚吉著,“計算幾何学”,朝倉書店,2013
web拍手 by FC2
posted by シンドラー at 02:10 | Comment(0) | TrackBack(0) | Computational Geometry | このブログの読者になる | 更新情報をチェックする