- TSP について、
参考プログラム
http://grape.astron.s.u-tokyo.ac.jp/~makino/
kougi/keisan_tenmongakuII/programs/index.html
にある anneal.C を動かしてみて、単位正方形内にランダムに 100 個
程度の点をばらまいた時にどんな答がでるか見てみよ。また、アニーリングス
ケジュールをいろいろ変えてみて、答がどのように変わるか調べよ。
規則的に点を並べた場合には、TSP の厳密解が全数探索をしなくても求まる。
100点程度の場合にそのような厳密解がある場合を作ってみて、 SA で厳密解
に到達できるかどうか調べよ。
- 参考プログラムではコストがユークリッド距離であるとしている。これ
をマンハッタン距離()にして、答の変化を見てみよ
- のところに川があって、川を渡るのには
のコストが余計に掛かるとして答の変化を見てみよ。もっともらしいか?また、
どのようにしてもっともらしいと判断したか?
- 「単位正方形の中に 個の円を重ならないように詰め込めるような
円の最大半径はいくつか」という問題を、「円の詰め込み問題」という。いく
つかの については厳密解が知られているが、一般の について解かれ
ているわけではない。これを SA で解いてみて、どれくらいもっともらしい答
がでるか調べよ。目的関数として、 個の点間の距離と壁への距
離の最小値をとればよい。知られている厳密解のいくつかは以下にまとめられ
ているので、比べてみること。
http://www.cg.inf.ethz.ch/~peikert/personal/CirclePackings/