バレンタインイベントの教範消化が果てしなく辛い。昨日も今日もレベル上げをサボってしまった。
もう、ソロはウアーcの夢があるセージしか無理っぽい、精神的に。
…と話したら、優しいにむさんがPT狩りに誘ってくれたので、狭間03へ行ってベントス持って帰ってきました(∩´∀｀)∩
あと、久々にHiME動かしたりも。MEやっと5。
◇
以前のエントリにできるだけ無駄のないクエストのまわり方を探す計算機を作ったと書いた。
それから9ヶ月かけて改良を続け、他の計算機もまとめて公開することに。
よかったら、来て見て触って!
―――『クエスト道案内』
扱う問題がTravelling salesman problemそのもので、最適解をパッと求めることは不可能とされている。まわり方は数億パターン、狩りをして稼ぐという行為も含めるとほぼ無限なので、単純な総当たりで短時間に答えを出すことができない。
そこで、最適解を諦め、『やや最適っぽい解』を返すことにした。以前公開したものは『最適でもない解』ぐらいしか出せなかった。あと、出た答えに対して、手動で書きかえられるようにもした。最初からすべて手動で道順を組み立てることもできる。
Nearest neighbor search法を使ってさらに良い解を求めようとしてみたが、質があがらず、計算時間ばかり食うのでやめた。何かいい方法がないか、暇があったらまた考えてみたい。
―――『カプラ探』
ある場所からある場所への最短・最安ルートを探す計算機です。
公共機関の乗換案内でもよく用いられている、Dijkstra’s algorithm法での求解。
とりあえず作ってはみたものの、ROには乗りものが少ないので、頭でルートを考えたほうが早かったりする。
えっ、それを言っちゃおしまい…?
まあ誰かの役に立つことを願ってます(｀・ω・´)
Comments are closed.