TCO11 Round 2
(2011年6月29日の記事を移行したものです。)
結果
136位/222 Rating 1795→1694
このRoundで敗退かつレーティング的にも大敗北…
問題
複数の点がだいたいランダムに配置されている（点の数は50～5000）。それらの点を結んで多角形を作れ。
- 入力パラメータsidesDiff。1≦sidesDiff≦20。sidesDiffは多角形の各辺の、最小の長さと最長の長さの割合、もしsidesDiffが20だったら、最小の辺の長さは、最長の辺の長さの100-20=80%以上でないといけない。
- 入力パラメータradiiDiff。1≦radiiDiff≦20。radiiDiffはは多角形の中心（点の座標の平均）から、各頂点からの距離の、最小の長さと最長の長さの割合。sidesDiffと同様。
- 同じ点を２回以上使ってはいけない。
- n角形につきn*n点もらえる。
点が少ないケース(Example1)
点が多いケース(Example7200)
このように、つくるべき多角形は正多角形に近い形になります。
方針
今回は反省点が多いのですが、まずは、良さげ見える（が実は良くない）今回の目標と方針を書きます。あとで、失敗した点を書きます。
目標
今までのマラソンマッチでは、最高点が伸びなそうなアルゴリズムだったので、中途半端な順位だった→
「今回はすぐに結果がでないくてもいいから、到達最高点が伸びるような、計算量もギリギリまで使い切るような、スケールの大きいアルゴリズムにする。」
方針が決まるまでの流れ
「たいていの人は頂点数Nが多いときに苦戦するであろう」
→「計算量がNにあまり依存しないアルゴリズムを考えれば勝てるのではないか？」
→「下記のアルゴリズムなら、O(中央の点の数*N)と、Nのオーダーは1乗。しかも、計算量も中央の点を(1,1)おきにとれば、700*700*5000=2450000000で10秒ギリギリぐらい？いけるかも」
→「しかも、この方針は、正10角形を求めるのも、正100角形を求めるのも、かかる時間はそれほど変わらないので、めっちゃ有利」
実際以下の方針を思いつくまでに、10日ぐらい消費してしまいました…
方針
１．まず、中央の点(cx,cy)を決めます。
２．N個の点を極座標に配置します。各点のr,θを求めるのは三角関数で簡単に求まります。
３．座標に分けたので、θ方向に等間隔の座標にあれば、正多角形に近い形になります。
４．結局は、r,θの２次元の座標に落とせるので、「もし、ある(dr,dθ)の範囲内に点があるか調べたい」ときはDPを使えます。
だいたい、「θの範囲、rの範囲がどれぐらいに収まっていれば、正多角形ができるか？」についての基準は、あらかじめ別なプログラムで、sidesDiffとradiiDiffごとに求めておきました（ある半径rのn角形の,範囲dr・dθに点をランダムに配置し、sidesDiffとradiiDiffを満たす多角形ができるか調べる）。実際にこの部分の精度については、かなり高かったので、うまくいってたと思われます。
反省点
目標が間違ってる
そもそも「計算量をギリギリまで使ったアルゴリズム」が高得点とは限りません。欲しいのはスコアです。大きく勘違いしてます。
スコア分析がだめ！
これ、すごく重要で、初回のマラソンでは出来てたのですが・・・。この問題を「正ｎ角形で、できるだけｎが大きい多角形をたくさん作ろう！」と考えているようではダメです。もうちょっと細かくみていかないといけません。例えば、６角形１個は３６点、３角形４個も３６点です。大きい多角形を無理してつくるよりは、多くの小さい多角形をつくったほうが良い場合も十分考えられますよね。スコアについて、ほんとによく考えたほうがいいです。
計算時間あたり・頂点数あたりなど、単位を意識した考察ができていない。
６角形１個つくるのに1秒、３角形１個つくるのに0.1秒だったら、断然３角形をつくったほうが、時間あたりの得点が高いです。同じように、頂点数あたりの得点なんかも考慮するべきでした。今回の自分のアルゴリズムでは、計算時間あたりの得点について全く考慮していません。単位を統一して考えるのは、アルゴリズム以前の重要な問題です。これがちゃんとしてないと、そもそもアルゴリズムの良し悪しの比較ができなくなってしまいます。仕事では、めっちゃ注意しているのですが(T T)
「頂点数Nに依存しにくいアルゴリズム」にする必要はない。
別にNによってアルゴリズムを変えるのは全然構いません。Nに依存しないアルゴリズムは、裏をかえせば「Nが小さいときの有利さを生かせない」アルゴリズムでもあります。（ただ、複数のアルゴリズムを用意するのは、実装の時間はかかるので、１つに統一するメリットもあります。）
実装時間も考えて計画をたてよう。
誰でも思いつくようなケースをほとんど試さなかった。
特に、時間がかからずに実装できるものは、絶対試したほうがいいです。仮に全然結果がでなかったとしても、その後のヒントになる可能性もありますし、条件によっては使えるかもしれません。今回、自分の考えたのは実装時間がかかるため、それが外れ方針なのに気づくのに時間がかかってしまいました。
このアルゴリズムの欠点
実は、計算量が多くなり、(cx,cy)を調べられる箇所が少ない。
当初の予定では700*700マス（中央がマス上にあるとは限りませんが）調べる予定でしたが、だいたい10000～100000点ぐらいしか調べられませんでした。実は、
(1)r,θを等間隔で細かくとった場合（dr=1,dθ=1）、矩形でO(1)を計算するため、DPで2次元部分和を計算するときが計算量がO(rの分割数(=350)*θの分割数(=360))となり、頂点数Nより大きくなり、そこがボトルネックとなる
(2)r,θを等間隔ではなく、n角形時のdr,dθにあわせてとると、ボトルネックは解消されるが、n角形ごとに計算しなければならない。
最終的には(2)の方針でいきましたが、計算量的にはきつく、多くの(cx,cy)を調べることはできませんでした。
(cx,cy)の位置についての工夫がない。
全く思いつきませんでしたが、多くの人は中央を先に決めるという手法を使ってました。
「(cx,cy)を変えるたびに、N点配置する」ということ自体が損
もし(cx,cy)によらずに、再利用できるデータがあれば、それでも高速化できたはずです。
まぁ、いろいろ試して失敗した点（ひどい焼きなまし法とか）や、反省点（10秒に間に合ってないケースが5つあった）とかは、まだまだありますが、これぐらいで。
TCO11 Round 1
(2011年6月1日の記事を移行したものです。)
結果
62位/368 Rating 1754→1795
大反省点
- 調査してね（インターネットつかえます）
- 文字を置く・何か置く、やり直し(Undo)が可能な部分については、最初からやり直し可能な実装をしていかないと、だめです。
- 最初の解答ができるまで、とにかく、がんばれ。
- 前回の反省点を守ろう。同じ失敗をくりかえす自分は最悪です(>_<)
- マラソン開始日前に、もやもや要素をすべてとりのぞく。何も用事がない・借りがない状態でマラソンをスタートしましょう！
- マラソン期間中に、アクシデントにまきこまれない。普通の生活をしよう。
- Javaを自分の場合つかわないので、Javaでの採点部分や、scan部分などは、できるだけはやくC++に移植する。
- ちゃんとマラソンスタートしたら、はじめる。毎日安定してやる。
- はやめにスタートしたほうが、計算リソースを有効に使える。
- ぎりぎりなってからだと常にパソコンでプログラムを書きたいので、計算結果待ちとかの時間が無駄。はやいうちにスタートしておけば、夜中に計算とか、出勤中に計算とか、有効に計算リソースを使うことができる。
- パソコン２台あるのを有効に使う
ポイント
（いろいろあったのですが、マラソンRound2前に書く時間がなくなってしまったので、すごいてきとーです・・・。せめてツールの画像だけでも。本当は画面右側に文字情報のリストが表示され、選択中のものだけ色を変えたりすることもできます。）
基本的には重なる黒のマスが多い文字からおいていったのだが、上のIのように、TLEはIに負けたりする。つまり、
「実際にはかなり合ってるのに、登場することができない不幸な文字があるのでは？」
と思い
- 外れている文字を使ったら選ばれにくくする
- 答えにあるのに使わない文字があったら選ばれやすくする
というのを多くのテストケースでまわし、文字の選ばれやすさの重み付けを決めるという方針で行った。
しかし、結果はほぼ効果がなかった。実際には、ほとんどの文字の「当たっているのに選ばれない」＝「当たっていないのに選ばれる」の確率はITLEなどを除き、ほぼ一緒になってしまった。
Marathon Match 68
(2011年6月1日の記事を移行したものです。)
結果
9位/147 Rating --→1754
大反省点
- 開始日になんでもいいから提出して追い込む！
- 準備完了までは集中！
- ちゃんとスコアがでるようになると、面白いので集中できる。準備の段階が面白くないので脱線しやすい）
- 異常を早めに察知するために、ときどきArenaにいって、サブミット＆まわりの人のチェック（提出時間・得点）
- テストケース50個では少なすぎ
- 誤差でまくり論外！！！テストケースは最悪でも300,500は必要
- 疲れているときにできること、疲れているときにできないことにタスク分けして作業をすすめる。
- 10秒間の計算時間があるのを有効に使ったアルゴリズムにする
- 最後のほうまで、即終わるアルゴリズムだったので…
反省点
- サブミッションの問題（1時間３０分次の提出ができないのでお早めに。
- 早めに知ってれば、「へび」配置をいれるかいれないかも含めて調整できたのに・・・。
- タイマーの問題（１０秒）Clock関数。とくにアリーナ上では、時間がかかるよう。
- gettimeofdayのほうがよい？
- 序盤の準備にわりと時間がかかる。
- やってみて気づくことはたくさん。なので、後で追い込むのではなく、最初から少しずつやってったほうがいい。
- ソースは丁寧に書く。リファクタリングは、時間に余裕があるときなら、多少眠くても疲れててもできる。
- ネット切断は効果的だったけど、たまにはアリーナものぞくべきだった。
ポイント
「回」型の配置パターンで62.5ptsは取れるのは予想がついたけど、「回」型の配置に気づくのが遅すぎた。また、正方形のときにしか対応できないアルゴリズムを書いてしまったので、「田」型への応用が難しくなってしまった。
唯一良かったのは、大きさの違う正方形「回」を組み合わせることにより、rcFillingScoreが満点のままで「田」型にする方法を思いついたこと。これのおかげで、上位になんとか食い込むことができた。
例えば、3等分の「田」にしたいときは、横幅がN%3==0,N%3==1は以下のような配置にできる。普通の「田」だと隙間の行ができてrcFillingScoreが下がってしまうが、これならＯＫ．
4等分の「田」にしたいときは、以下のような配置もある。
あと、上位の方は
- 「回」「田」以外でも点対称な配置はいろいろあった
- 置き換えが可能なアルゴリズムにしていた。
といった点で大きく差がついた。
「海外で働く人が驚いた日本とのギャップ」に、ツッコミました
Naverまとめの記事「海外で働く人が驚いた日本とのギャップ http://matome.naver.jp/odai/2129410761628592301 by なぁーこさん」が、とても面白かったのですが、納得するケースと、これは違うなと思うケースと、いろいろだったので、自分の経験を元にツッコミを入れてみました。
以下の点については、ご了承ください。
- 環境や、個人の感じ方で、全然違ってくると思うので、一般論だとは思わないでください。
- 自分が今までは働いたのは、日本のゲーム会社と、海外のゲーム会社の２社です。「東京」が日本の会社、「バンクーバー（カナダ）」「バルセロナ（スペイン）」「シンガポール」は海外の同じ会社です。
- ゲーム会社しか知らないので業界による偏り、海外については「同じ会社」でしか働いてないという偏りは、かなりあると思います。
- 「海外」と表記してても、基本、働いた３ヶ国だけを指してます。
それでは、ここからスタートです。長文です。
長期休暇はしっかり取る
| 東京 | △ |
| バンクーバー | ○ |
| バルセロナ | ○ |
| シンガポール | ○ |
日本にいたときも２週間程度の長期休暇は取れてましたが、プロジェクト終了後に、休日出勤分の振替休暇を使っていたというかんじです。有給休暇は年に１・２日しか使えてなかったので、△にしました。
海外では、ほぼ全員が振替休暇・有給休暇を使っていると思います。余って消える場合は、休暇買い取りになってます。
あと、スペインは有給休暇が長いです（年27日でした）、振替休暇と組み合わせて、２・３ヶ月の休暇を取っている人は普通にいました。前年の分の有給休暇と組み合わせて、半年ぐらい休んでる人もいました。
決して謝らない
| 東京 | × |
| バンクーバー | × |
| バルセロナ | × |
| シンガポール | × |
たぶん、「I'm sorry. というと責任を全部認めたことになるので、そう簡単に言うべきではない」というのが日本に広まってるからかもしれませんが、謝らないってことはないです。謝るべきケースで謝らない人も、まれにいましたが、そういう人は信用をただ失っているだけでした。それは、日本でも海外でも同じだと思います。
ロシアの社長は平社員と一緒に飲まない
| 東京 | × |
| バンクーバー | × |
| バルセロナ | × |
| シンガポール | × |
ロシアはそうなのかもしれませんが、東京・バンクーバー・バルセロナ・シンガポールいずれも飲んでますｗ
残業はしません
| 東京 | × |
| バンクーバー | ○ |
| バルセロナ | △ |
| シンガポール | × |
残業する必要があったら、多くの人はしますが、どんなことがあってもしないという人の割合は、バンクーバーが多かったかもしれません。海外だと、残業時間が長いと、管理職の管理能力が低いとみなされるので、残業時間を減らす工夫はいろいろしてる気がします。残業時間には大きな差がありますね。
仕事中でも平気で私用電話する
| 東京 | × |
| バンクーバー | ○ |
| バルセロナ | ○ |
| シンガポール | ○ |
これは、今でも違和感を感じるギャップです。ミーティング中でも、家族から電話があったら、普通に電話にでる人がほとんどです。日本だったら、電話の着信音がなった時点で、相当まずいケースだと思うのですが…。
14時から16時にかけて昼休み
| 東京 | × |
| バンクーバー | × |
| バルセロナ | × |
| シンガポール | × |
スペインには、シエスタ（長い昼休み）があるのですが、大きな会社やスペイン北部では、なくなりつつあるようです。実際、バルセロナでは14時〜15時が昼休みでした。
残業があるときなど、皆必ず残業に入る前にしっかり夕食を食べる
| 東京 | ○ |
| バンクーバー | ○ |
| バルセロナ | ○ |
| シンガポール | ○ |
日本でも、しっかり夕食食べる気がするのですが、もしかしてゲーム業界だけなんでしょうか…。
違いといえば、海外では、残業のための夕食はOT Mealと呼ばれて、会社が払います。会社が出前をとったり、自分で夕食を買いにいって後で代金を払い戻したりです。ただ、たまに働かずにOT mealを食べる人や、OT mealを食べて19:30ぐらいに帰ったりする、ずるい人は割といます（もちろん、怒られます）。
賞与は一切無しでインセンティブのみ
キムチ作りにボーナス（諸手当についてと解釈しました）
| 東京 | △ |
| バンクーバー | × |
| バルセロナ | × |
| シンガポール | × |
通勤手当、住居手当など王道なものから、ちょっと変わった諸手当まで、日本は意外とあると思います。海外は基本は年俸だけです。年俸だけ＝実力勝負というかんじがするので、自分は海外の形式のほうが好きです。ゲームが大きな利益をあげたらインセンティブがもらえるのは、日本も海外も一緒ではないでしょうか？
ただ、他社に転職する際には、交渉があるので、そこで手当などがつく場合があります。自分の場合も、引っ越し手当と、日本への帰省の手当がありました。ちなみに、バンクーバーの元上司が、イギリスからカナダの別会社に移る際に、交渉で「ペットの引っ越し手当も契約に含めてくれ」とお願いしてOKがでたのですが、それでペットとして馬を飛行機で輸送させてました…。
男性育児休暇が当たり前にとれる
| 東京 | × |
| バンクーバー | △ |
| バルセロナ | ？ |
| シンガポール | × |
日本では、見たことなかったです。バンクーバーでは数ヶ月の育児休暇を取ってる男性はいました。シンガポールは、制度が複雑ですが、短いので、取ってる人は見たことがありません。
あと、女性の育児休暇についてですが、バンクーバーでは、数週間で職場に戻ってくる人も、それなりにいました。日本だと、女性が育児休暇をとった場合は、だいたいは長期間休むと思いますので、あまりこういうケースはないかもしれません。
人の席の電話は鳴ってもとらない
| 東京 | × |
| バンクーバー | ？ |
| バルセロナ | ？ |
| シンガポール | ？ |
そもそも、ほとんど会社に電話がありません…。電話を受けるのは事務の人だけです。日本では、５席に１個ぐらいあって、外線・内線ともに電話を取ることが多くあったのですが…。日本でなぜ会社に電話がかかってきていたのか、あまり覚えてません…。
顧客のメールを1週間以上普通に放置する
メールの返事が嫌い
催促されなければ仕事をしない
責任感がなく、ミスを指摘すると「マイペンライ（問題ない）」と答える
| 東京 | × |
| バンクーバー | △ |
| バルセロナ | × |
| シンガポール | × |
この４つについては、日本・海外云々じゃないですね。日本であろうと、海外であろうと、仕事で結果を出してる部署・支店についてはちゃんとしてますし、結果を出してないところはダメです。断言できます。全部、仕事に直結することですし、そうなるのも当然かと。
ブログでクビになる
| 東京 | × |
| バンクーバー | × |
| バルセロナ | × |
| シンガポール | × |
今の海外の会社との契約で「常識的な使用範囲なら、仕事の間にSNS等をやっても問題ない」と明記されてるので、問題ありません。心配だったら契約の際に聞けば良いだけです。もちろん、会社の秘密等を書き込んだらクビになりますが、それは日本も海外も同じでしょう。
仕事より家族
| 東京 | △ |
| バンクーバー | ○ |
| バルセロナ | ○ |
| シンガポール | ○ |
日本にいたときの会社は、「仕事より家族が大事」ということに理解がありましたが、個人レベルでは、「仕事より家族が大事」か「家族より仕事が大事」は考え方はバラついてると思いますし、実際、家族を犠牲にして、不幸な感じになってる例も数例見かけました…。海外では、「家族より仕事が大事」と言ってる人を、ひとりも見たことがありません…。家族の問題があったときは、制度的にも融通がきくので、助かっています。自分の場合、身内の病気があったのですが、「無給の休暇については、何か月とってもOK」と言われて、とても助かりました。
バンバン転職する
| 東京 | × |
| バンクーバー | ○ |
| バルセロナ | △ |
| シンガポール | ○ |
バンクーバー、シンガポールでは、バンバン転職してます。うちの会社のシンガポール支店は、出ていく人が少ない（といっても年に１・２割はやめる）ですが、明らかに例外で、シンガポール全体では、とても多いそうです。
あと、「海外では、転職する人ほど、能力が高いとみなされる（能力が低い人は転職できない）」というのは、日本にいたときには耳にしてたのですが、実際はケースバイケースです。本人の実力次第です。
納期が自己都合で延長される
| 東京 | × |
| バンクーバー | × |
| バルセロナ | × |
| シンガポール | × |
さすがにゲームの開発でそれはないですが、海外の事務系の仕事は、てきとーすぎるので、そういうケースは見られます。
終業時刻は厳守する
| 東京 | × |
| バンクーバー | × |
| バルセロナ | △ |
| シンガポール | × |
日本でも海外でもコアタイムがありますが、終業時刻はそんなに気にしてないと思います。タイムカードをちゃんときってたバルセロナが一番終業時刻を気にしてたかも。
遅刻は平気でする
| 東京 | △ |
| バンクーバー | △ |
| バルセロナ | △ |
| シンガポール | △ |
全部△にしましたが、意味的には結構違います。バンクーバーの場合は、時間を守る意識はむしろ低いのですが、そもそも朝早く来て早めに帰る人が多かったです。朝にランニングしたり、昼にジムにいったり、健康を意識した生活をしている人が本当に多いので、そもそもギリギリにくる必要がないかんじです。でも、遅く来る人は、自分のペースですごい遅くきてたので、△にしました。マイペースの結果です。バルセロナ・シンガポールは、大遅刻する人はいませんが、コアタイム間際にくる人が多く、多少遅れる人もいるかんじです。日本にいたときは、最初の部署が何時に来ても良い感じで、次の部署は時間に厳しい感じだったので、まちまちです。
仕事中に飲食可
| 東京 | ○ |
| バンクーバー | ○ |
| バルセロナ | ○ |
| シンガポール | ○ |
どこでも、いつでも、普通に食べてます。IT系の会社で、ダメって言われてるところは、あるのかなぁ。
仕事中にカウンター内で弁当を食べたり、PCでチャットやオンラインゲームをしたり、従業員同士で大声でべちゃくちゃおしゃべり（飲食部分はダブってるので無視しました）
| 東京 | △ |
| バンクーバー | ○ |
| バルセロナ | △ |
| シンガポール | △ |
これは、日本・海外によらず、チームの雰囲気による気がします。結果重視なので、迷惑をかけなければ、何してもOKではありますが。
大卒の学歴がいらないような仕事に就く
| 東京 | ？ |
| バンクーバー | △ |
| バルセロナ | ○ |
| シンガポール | × |
シンガポールは、明らかな格差社会になってますし、×でしょうね。バルセロナは、この問題をよく聞きましたが、経済危機による若者の失業問題の影響なので、時間がたてば、たぶん学歴にあった仕事に就くのではと思います。
ゲーム業界だけで言えば、日本のほうが、学歴を気にせず、雇っていると思います。
女たちが汗水垂らして働く横で、男たちがグータラと寝そべっている
| 東京 | × |
| バンクーバー | × |
| バルセロナ | × |
| シンガポール | × |
どんな仕事でも、上記の４か国では、見かけないですね…。
チップがもらえる
| 東京 | × |
| バンクーバー | ○ |
| バルセロナ | △ |
| シンガポール | × |
もちろん、ゲーム業界では一切ありませんので、一般論として。シンガポールは日本と同じでチップ不要。バルセロナは良いサービスを受けたらって感じで、基本はいりません。バンクーバーはチップあります。チップは慣れるまでは面倒ですね…。
チームの同僚が仕事をやめる日のfarewell partyとかでも定時後の時間ではなく、ランチの時間を使ってる
| 東京 | × |
| バンクーバー | ○ |
| バルセロナ | ○ |
| シンガポール | ○ |
ランチの時間も使いますが、プロジェクトの忙しさによりけりです。日本の場合は、そもそも辞める人が少なく、プロジェクト終了後とか辞める時期を考えて辞めていきます。海外の場合、プロジェクトの時期を気にせず、いつでも、しかも頻繁にやめていくので、ランチの時間にせざるをえないケースが結構あります。プロジェクトが忙しくないとき・やめる人が飲み好きで夜にしたいとき・影響の大きい人のときは、ふつうに夜にfarewell partyをやってると思います。
会社のイベントは自由参加
| 東京 | ○ |
| バンクーバー | ○ |
| バルセロナ | ○ |
| シンガポール | ○ |
日本にいたときは、自分はイベントは喜んで全参加してたので、あまり分からないですが、日本でも断ろうと思えば断れたと思うので、自由参加なのかな？一般的には、強制参加というケースも多いのかもしれませんね。
海外だと、会社イベント（忘年会・新年会・打ち上げ）で、内容によって、家族同伴可のイベントや、恋人同伴可のイベントになったりします。むしろ、恋人同伴可のイベントに、１人で参加するのが、プレッシャー…（; ;）。
仕事に関することは勤務時間内
| 東京 | ○ |
| バンクーバー | ○ |
| バルセロナ | ○ |
| シンガポール | ○ |
これは、個人によります。基本、勤務時間内ですが、勤務時間外でも勉強できることは、無限にありますし、影で努力している人はいくらでもいます。ちなみに、「ゲームエンジンアーキテクチャ」という業界内ではとても有名な本を書いた人がいるのですが、毎朝５時に出勤して本を書いていたそうです。逆に、勤務時間内にめっちゃ集中して仕事をして、すごい結果を出している人もいます。
出社後は、ゆったりコーヒー飲んでたり朝ご飯食べてたりする
| 東京 | × |
| バンクーバー | ○ |
| バルセロナ | △ |
| シンガポール | △ |
バンクーバーは◎つけたいです。出社後すぐに仕事を始める人は、あまりいなかったかも。キッチンで朝飯を調理してる人もいました。バルセロナ・シンガポールでも、それなりにいます。日本ではアウトでしょう。
こんなかんじです。所詮１人の見識なので、あてにしないように。ただ、いろんな人が、こういうツッコミをいれたら、海外での実態が見えやすくなるかもしれませんね。他の人のツッコミにも期待しましょう。
それでは！
健康について考える(1) - セカンドオピニオンは重要！
実は先月、身内の手術・入院のため（自分じゃないよ）に、兵庫県の病院に3週間ほど滞在してました。近くの施設から入院病棟に通う生活です。そのときに、いろいろ健康について考えさせられました。シリーズになるか分かりませんが、第１回。
(1) セカンドオピニオンは重要！
簡単に書くと、地元の病院（東北では評判良い病院）での診断は、
| 「２つの脳の血管がつながっているところに異常があるので、カテーテル手術は不可能。開頭手術してみないと分からないし、治せない可能性が高い。開頭手術だけでも後遺症もありうる。治さないと、いつでも突然死ありうる。」 |
という感じで、絶望していたのですが、インターネットでいろいろ調べたところ、その症状に詳しそうな先生がいたので、セカンドオピニオンをお願いしてみました。結果、
| 先生「この角度からの写真ではつながって見えるけど、本当はつながってないかも」 →診断受ける 先生「血管の１つに造影剤を入れてみて、つながってたら両方光るし、つながってなかったら片方だけ光るはず」 →確かにそうだと思ったので、検査入院する 先生「１つしか光らなかったので、血管はつながってない別々のもの。カテーテル手術可能です」 →入院・カテーテル手術 →無事退院 |
と、治ってしまいました…。ここまで、医者の能力差があるのかと、驚きました。セカンドオピニオンは活用すると良いと思います。
ただ、お医者さんを探すときに、いろいろ胡散臭そうな人もでてきます…。ちゃんとした人を探すのに、論文とか文献とか調べる能力は、かなり役立つと思います。たとえば、
- 医者のもってる資格・実績は、正当なものか、価値はあるものか調べる。
- 医者の言っている薬・病気・技術などの専門用語を検索してみる。
- 論文発表してるか、発表先がちゃんとした学会を調べる
- 良さげな医者と名前が並列にでてる医者も調べてみる。
というわけで、理系な方はたぶん得意だと思うので、ぜひ良く調べて探してみましょう。もちろん、２人目の意見が必ずしも正しいとは限らないし、悪い結果になることもあると思います。それでも、選択肢が増えるので、良くなる確率は、確実に上がると思いますので、セカンドオピニオンおすすめします。
動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる
この記事は、Competitive Programming Advent Calendar Div2013（http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83）の8日目の記事です。
動的計画法(Dynamic Programming, DP)についての記事です。
12/9 前編にサンプルプログラム（http://ideone.com/2B7f4v）を追加しました
12/11 前編の図２つを差し替えました。
はじめに
まずは、本やネットの資料で、動的計画法についてのすばらしい解説はいろいろありますので、まずはそれらを参考に。
- プログラミングコンテストでの動的計画法
- 最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった
でも、苦手な人視点からのアドバイスはあまりない気がするので、敢えて書いてみることにしました。ただ、
- 自分以外は誰も悩まなかったポイントかもしれません。
- すこしはコツみたいなことも書いてますが、負け組の考え方である可能性は高いです。
- よって変な癖とかついてしまうかもしれません。
でも、そこはうまく取捨選択してください。というか、むしろ、良い考え方を教えてほしいですorz
対象の読者
- 動的計画法の基本的な問題（0-1ナップザックとか）は、何をやってるかは理解できる。
- プログラミングコンテストチャレンジブック第2版のP52-P55は理解できる
- 自力で動的計画法の問題を解くのは、ほぼ不可能。
- 動的計画法はイメージ？何をイメージしたらいいの？DPテーブルの値が決まってく様子？分からん！
- そもそも漸化式が思いつかないので、イメージ以前の問題
- DPテーブル、変数に何を使えばいいのか、さっぱり分からん
- 動的計画法は中学受験算数の出題範囲→そんなの一般人はやらない。来世に期待！
- 上位の人「DPに逃げました」→ハラスメント
お断り
- 基本的に、プログラミングコンテストチャレンジブックの用語を使います。
- 動的計画法での計算結果を保存する変数を「DPテーブル」と呼び、配列変数の名前をdpとします。
- 「メモ化再帰」「漸化式」等の用語も、そのまま使います。
前編：再帰のやり方とか知ってるのに、どうも「メモ化再帰」がしっくりこないあなたへ
※ 前編で登場する、「枝刈り探索」と「メモ化再帰」のサンプルプログラムです→（http://ideone.com/2B7f4v）あわせてご利用ください。
動的計画法の問題で求めるのは、たいてい次のA,Bだと思います。
| A. 最小値・最大値を求める B. 数え上げ。何個か何パターンかを求める |
自分の場合は、こういうのを求めるとき、仕事でも日常生活でも、以下のような手順で考えていました。
| (1) 選択肢を羅列する (2) 制約条件があるなら、選択肢が制約条件を満たすかチェックする。 (3) A. 制約条件を満たしたやつの中での最大値を求める。 B. 制約条件を満たしてたら+1して数えていく。 |
ただ、この手順は、動的計画法（≒メモ化再帰）的な考え方とは、かけ離れているのですよ…。例えば以下の問題を考えてみましょう。
| 0-1ナップザック問題（プログラミングコンテストチャレンジブックより） 重さと価値がそれぞれ、wi,viであるようなn個の品物があります。これらの品物から、重さの総和がWを超えないように選んだ時の価値の総和の最大値を求めなさい。 1≦n≦100, 1≦wi,vi≦100, 1≦W≦10000 入力例 n=3, (w,v)={(2,3), (3,4), (1,2)}, W=3 |
「全探索が基本」「樹形図をかけば分かる」というのは、知ってたので、自分は以下のように考えました。
これは「メモ化再帰」ではありませんし、ここから「メモ化再帰」に改良することすらできません。確かに最大値も求まっているし、これでも良い気もしますが、すぐにn≦100という条件をみて、
n=100のとき、2^100通り→こんな問題解けるわけがない→そっとじ
とやってました…。「メモ化再帰」のように、状態の少なさを生かした高速化ができなくなります。
あと、こんな発想をするタイプの人にとっては、「(2) 制約条件があるなら、選択肢が制約条件を満たすかチェックする。」は、単にひと手間を複雑にしているだけの邪魔者にしかみえないでしょう…。制約条件は、動的計画法のともだちなんですよ…。（後編で説明します。）
「メモ化再帰」とは、以下の図のようなかんじです。根のほうにデータを集めるような樹形図です。先ほどの図とはデータの流れが真逆なことが分かるでしょう。
ちなみに、「メモ化再帰でない全探索」のあと、少し成長しました。制約条件を破ってたら、以下の図のように、もう計算しないようにしましたが…
「メモ化再帰」では、枝先のほうをまとめて端折っているし、似たような樹形図を見かけますが、これでも「メモ化再帰」とは違います！！ これは、俗にいう「枝刈り探索」です。「メモ化再帰」と「枝刈り探索」を比較してみました。
「メモ化再帰」
-
- int func(int x, int y)のように、関数は値を返す
- 根のほうにデータを集める樹形図。
- 同じ入力値をこの関数の結果を返す、int memo[x][y]のようなメモ用の配列変数がある。
- 計算をはしょれるのは、入力x,yのときの出力（返り値）を、既に知ってるから。
- 計算量が予測しやすい。「メモ用の配列変数の要素数（入力するx,yのパターン数）」*「関数内の計算量」
「枝刈り探索」
-
- void func(int x, int y)のように、関数は値を返さなくてよい。
- 枝のほうにデータが流れていく樹形図、それを集計するかんじ。
- 今まで呼んできた関数（根のほう）での計算結果を、グローバル変数などに保存しておいて（上記の例だと、どの品物を今まで選んできたか）、それを生かすことが多い。
- 計算をはしょれるのは、制約条件を既に違反してたり、最大値・最小値をもう達成することが不可能なため、先の関数を呼ぶ必要がないから。
- 計算量が予測しにくい。
逆に、両者の共通点といえば、「深さ優先探索(Depth First Search)で全探索する」部分ですね。後はいろいろ違うのでごっちゃにしないようにしてください。どちらかが優秀という訳ではないです。同じように混乱したことがある人は、プログラミングコンテストチャレンジブック第２版のP54のCOLUMN、「全探索の書き方」もぜひ読んでください。
メモ化再帰については、先ほど示した資料も含め、良い資料がたくさんあるので、説明は省きます。Have fun and good luck!
後編：動的計画法の意味はわかるけど、問題は解けません！なあなたへ
動的計画法の嫌なところ
- バリエーションが豊富すぎて、手におえない。
- どこから手をつけたらいいか分からない。
バリエーションが豊富すぎて、手におえないのは、しょうがないです。ただ、そのバリエーションの多さに、基本的なことの検討を見逃して、動的計画法の割には簡単な問題をおとしてしまうのは、避けたいです。
あと、どこから手をつけたらいいか分からない問題について。DPで問題を解くためにクリアするべき点が3つあります。
- (1) DPテーブルの定義 dp[?][?]=?
- (2) 漸化式をたてる
- (3) 状態・計算量を減らしてみる
これらが、(1)→(2)→(3)のように、順番にクリアしていくことができればいいのですが、多くの問題の場合は(2)ができないので(1)を直すとか、(1)を変えたら(3)の計算量が増えたとか、3つとも複雑に絡み合うので、やっかいなんですよね…。まぁ、1つずつ見ていきたいと思います。
(1)DPテーブルの定義 dp[?][?]=?
- まずは基本的な形から検討しましょう。
- 一番の基本は、「dp[?][?]=問題で求めるもの（最大値とか個数とか）」です。まずは、これから検討しましょう。これが通用しない場合もあるのですが、それでも基本から検討しましょう。
- インデックスのほうで、dp[0番目〜i番目までの何か]のように、何かの番号がくることが多いです。
- DPテーブルの定義のバリエーションは、無限にあるわけではない
- 問題に出てくる変数の種類はせいぜい2種類〜5種類程度です。例えば、ナップサック問題だったら、重さ・価値・品物番号の３種類です。dp[番号][重さ]=価値とか、dp[番号][価値]=重さとか、いろいろつくれますが、それでも無限にあるわけではないです。がんばれ！
- 変数の定義はちゃんとしましょう。
- 動的計画法とは、直接関係ないのですが、変数の定義をちゃんとするのは、動的計画法では特に重要な気がします。結構、人によって、要素が1個ずれてたり（iがi+1になったりi-1になったり）ということはあるのですが、それは変数の定義が違うからですが、ちゃんと漸化式とつじつまがあってれば正解になります。
- 具体例1 ナップサック問題
- × dp[品物番号i][重さ]=価値
- ○ dp[品物番号i][0〜i-1番目までの重さ]=0〜i-1番目までの価値の合計 （特に0〜i-1とか範囲の部分が重要）
- 具体例2 SIRO Challenge http://jag2013autumn.contest.atcoder.jp/tasks/icpc2013autumn_c
- × dp[訪問都市（ビットで）][現在いる都市]=時間
- ○ dp[ラーメン屋のある訪問した都市（ビットで）][現在いる都市]=スタート地点から現在の都市までの移動時間＋現在いる都市でラーメン食べる時間も含めた合計時間
- 複数の解法がありうるので、ちょっと無駄な要素があってもOKな場合がある。
- O(n^2)のDPだけど、O(n^4)でもOKみたいな問題もあります。メモリ・計算量の許すのであれば、ちょっとぐらい無駄な要素があってもOKです。分かりやすい、書きやすいほうを選びましょう。
- DPの配列に慣れましょう。
- 動的計画法で、出てくる配列は、dp[100000][4][4][4]とか、dp[50][50][50][50]とか、日常プログラミング生活では、あまり見ないような配列がでてくることがあります。メモリ・計算量の許す限り、どんな形でもとりうるので、念頭に置いておきましょう。
(2) 漸化式をたてる
- まずは基本から
- kinabaさんの昔の記事にあるとおり、http://www.kmonos.net/wlog/90.html#_1712081024、dp[x][y]と定義したら、dp[x][y]とdp[x-1][y]、dp[x][y]とdp[x][y-1]にどういう関係があるかというのを着目したほうが良いと思います。例外は腐るほどあるのですが、例外から考えるとバリエーションがあまりに多すぎて死にます。まずは基本から検討しましょう。
- 確率のほうがやりやすい
- 確率問題は、わりと自然と漸化式がでてきやすい気がします。1/3の確率で+100点、2/3の確率で-50点だったら、dp[turn+1] = (dp[turn]+100)/3 + (dp[turn]-100)*2/3 のように、確率の公式そのものが漸化式になりうるので。
- 法則を見つけるコツ
- 小さいケースで考えてみる（n=1,n=2,n=3のときとか）
- 樹形図を書くと、法則が見えてくることもある。SRM531 DIV1 Easy NoRepeatPlaylistが好例
- 分割する。範囲DPや、グループ分けするようなビットDPでは、dp[全体]は、dp[分割した部分1]とdp[分割した部分2]の関係式で表せることが多いです。用語「最適性原理」も一度はチェックしてみてください
(3) 状態・計算量を減らしてみる
「状態」とは、DPテーブルでいったらdp[x][y]、再帰関数だったら int dfs(int x, int y)の(x,y)の組み合わせのことを指します。状態が多すぎると、計算時間が間に合わないので、解けません。どんな減らし方があるか書いてみました。
- 制約条件
- まず、制約条件が重要です。例えば、ナップサック問題で、「重さ≦1000000、価値≦100」という条件をみたら、「価値の範囲が狭い」→「dp[価値]のようにDPテーブルを定義したら、うまくいくのでは？」と思いましょう。
- 結果が同じになる状態はないか？
- 例えば、dp[100000000000]と、状態が無数にあるような場合でも、例えば、インデックスが奇数・偶数で値が同じになるなら（dp[0]=dp[2]=dp[4]=...、dp[1]=dp[3]=dp[5]=...）となるなら、dpテーブルはdp[2]で十分になります。
- 周期性、鳩の巣原理、偶数奇数のような法則があれば、結果が同じになる状態があるはずです。状態を減らすチャンス！
- もう古い状態は無視できるのではないか？
- 例えば、3手前以前に何の手をうったかは影響ないのであれば、dp[手数][2手前][1手前][現在]という風に削ることもできます。
- プログラミングコンテストチャレンジブックP177「ドミノ敷き詰め」のように、上から順番に埋めてって、もう下のドミノに影響を与えないような上部内側の部分も、無視できますね。
- 中は無視して、端だけで良いのでないか？
- 区間DPは典型例です。例えば文字列を使う問題なら、dp[左端][右端]としただけで、文字列が定まります。dp[左端][右端][上端][下端]とやれば、2次元の範囲が定まります。
- 「順序あり O(n!)」 → 「順序なし+現在位置O(n*2^n)」、「順序なしO(2^n)」→「個数・最大値・最小値 O(n)」と、計算量を落とせないか考える
- 「順序あり O(n!)」 → 「順序なし+現在位置O(n*2^n)」については、巡回セールスマン問題等で使うテクニックです。最小移動時間を求めるのに、dp[3→2→7→5]もdp[2→3→7→5]もdp[7→3→2→5]も、同じ状態とみなして良いです。なぜなら、これらから次の都市も含めた場合の最小移動時間を求めるときに、どうたどってきたかを知る必要はなく、すでに通過した都市（順序なし）と、現在いる都市が分かれば、次の都市を選べるからです。
- 「順序なしO(2^n)」→「個数・最大値・最小値 O(n)」で計算量を落とせることもありますが、見破るのはかなり難しいことも。例題としては、SRM511 DIV1 500pts FiveHundredEleven。
- (1)に戻って、dpテーブルの定義を見直せば、状態を減らせるかも。
- 「○○がX以下で，△△を最大化しなさい → △△がいくらまでなら，○○の最小値はX以下になるか？」の置き換えで、配列のインデックスと、配列の値を交換することができます。
おわりに
- メモ化再帰と枝刈り探索は、違います。普段、枝刈り探索っぽい考え方をしている人は、頭を切り替えましょう。
- 動的計画法は、問題のバリエーションが多いのですが、まずは基本的なところから検討しましょう。
- 企画倒れ感のある内容になってしまいました。超苦手な人向けになってない気がします。
- 他の方のフォロー記事に期待！
焼きなまし法のコツ Ver. 1.2
↓改訂版 Ver1.3はこちらから↓
shindannin.hatenadiary.com
2016年8月18日 Ver. 1.2 内容を更新しました。
4.遷移確率と温度の部分を全般的に修正
この記事は、Competitive Programming Advent Calendar Div2012の24日目の記事です。
http://partake.in/events/3fcea6d7-0bab-4597-82db-86439aadb1b9
素晴らしい企画をしていただいたtanzakuさん（https://twitter.com/_tanzaku_）、今年もどうもありがとうございます！
焼きなまし法そのものの解説は少しだけにして、焼きなまし法の使い方のコツをメインに書こうと思います。
焼きなまし法の概要
2015年5月26日 内容を更新しました。
最適化（=最大値か最小値を求める）の手法の１つです。以下は、てきとーな擬似コードです。
あらかじめ、計算する時間をTを決める。
以下のスコープ内のコードを時間T経過するまで繰り返す。
{
適当に、次の状態（近傍）を選ぶ。
(1) 次の状態のスコアが、今の状態のスコアより良くなった場合は、常に、状態を次の状態にする（遷移）。
(2) 次の状態のスコアが、今の状態のスコアより悪くなった場合でも、ある確率で、状態を次の状態にする。
確率は以下のように決める。
(2.A) 序盤(時刻t=0に近いとき)ほど高確率で、終盤(t=Tに近いとき)ほど低確率。
(2.B) スコアが悪くなった量が大きければ大きいほど、低確率。
}
最後に、今まで一番スコアのよかった状態を選ぶ。
次の状態が悪くてもそれを選ぶ可能性がある(2)の部分が、焼きなまし法の最大の特徴です。
「状態」「スコア」というのがピンとこないかもしれませんが、
- もし、巡回セールスマン問題であれば、
- 状態 →ルート
- 次の状態（近傍）→元のルートをちょっとだけかえてみたルート
- スコア →総距離
- もし、y=f(x)の最大値を求める問題であれば、
- 状態 →x
- 次の状態（近傍）→ x' = x + a (aは小さめの値)
- スコア →y
といったかんじです。
一応、参考までに、Marathon Match 60で使ったコードの断片を貼っておきます。全然難しくないです。
2015年4月20日 追加
以下のコード例は、上記の(2.B)の部分を無くした、スコアが悪くなった量は考慮しない焼きなまし法です。もっと効果的な方法「4. 遷移確率と温度」は必ず見てください。
vector <int> PolymerPacking::mirrorSequenceSI(ll msec) { vector <int> currentSeq; // 現在の状態。この問題では、vector <int>が状態だけど、問題によって大きく異なる。 // 現在の状態の初期化。この部分は問題によっていろいろなので、あまり気にしないでください。 const int L = 5; const int MAXMIR = 5; for (int i = 0; i < MAXMIR; i++) { currentSeq.push_back(0); } vector <int> bestSeq = currentSeq; // ベストの状態 double bestScore = getScore(currentSeq); // ベストスコア。getScoreは、状態からスコアを求める関数 double currentScore = bestScore; // 現在のスコア { const ll saTimeStart = getTime(); // 焼きなまし開始時刻。getTimeは、時間を返す関数 const ll saTimeEnd = m_startTime+msec; // 焼きなまし終了時刻。m_startTimeはこのプログラム自体の開始時間 ll saTimeCurrent = saTimeStart; // 現在の時刻 while ((saTimeCurrent = getTime()) < saTimeEnd) // 焼きなまし終了時刻までループ { vector <int> nextSeq(currentSeq); // 次の状態 nextSeq[rand()%MAXMIR] = rand()%(L-1); // 次の状態を求める。ランダムで1要素選んで、変えてみる。 const double nextScore = getScore(nextSeq); // 最初t=0のときは、スコアが良くなろうが悪くなろうが、常にnextを使用 // 最後t=Tのときは、スコアが改善したときのみ、nextを使用 const ll T = saTimeEnd-saTimeStart; // 焼きなましにかける時間 const ll t = saTimeCurrent-saTimeStart; // 焼きなまし法開始からの時間 const ll R = 10000; // スコアが悪くなったときでも、次の状態に移動する遷移する場合はtrue。１次関数を使用。 const bool FORCE_NEXT = R*(T-t)>T*(rand()%R); // スコアが良くなった or 悪くなっても強制遷移 if (nextScore>currentScore || (FORCE_NEXT && currentScore>0.0f) ) { currentScore = nextScore; currentSeq = nextSeq; printf("current Score=%.8f time=%lld\n",currentScore,t); } // ベストスコアは保存しておく。 if(currentScore>bestScore) { bestScore = currentScore; printf("New best Score=%.8f time=%lld\n",bestScore,t); bestSeq = currentSeq; } } } // ベストスコアをしたときの状態を返す。 return bestSeq; }
焼きなまし法のコツ
★が多いところほど、自分では重要だと思ってます。自信がないので、「こういうやり方もあるよ」「それはない…」「嘘乙」など、アドバイス大歓迎です！
1. 高速化
たくさんwhileループ内を回せば回すほど、スコアが伸びる可能性があります。基本的にはボトルネックを調べて、そこを高速化しましょう。だいたい以下のところがボトルネックになるでしょう。
★★★★ 変更がある変数だけを保存して、戻す
先ほどのコードだと、
vector <int> nextSeq(currentSeq); // 次の状態 nextSeq[rand()%MAXMIR] = rand()%(L-1); // 次の状態を求める。ランダムで1要素選んで、変えてみる。
とやっていますが、これでは時間がかかります。。次の状態を全てコピーしたのち、１つの要素を変えています（しかもvectorで動的にメモリ確保もしてます…）。高速化するなら、
const int index = rand()%MAXMIR; // 変更する要素 const int backup_value = currentSeq[index]; // 変更前の値 currentSeq[index] = rand()%(L-1); // 以下currentSeqをnextSeqとみなす。 const double nextScore = getScore(currentSeq); // 最初t=0のときは、スコアが良くなろうが悪くなろうが、常にnextを使用 // 最後t=Tのときは、スコアが改善したときのみ、nextを使用 const ll T = saTimeEnd-saTimeStart; // 焼きなましにかける時間 const ll t = saTimeCurrent-saTimeStart; // 焼きなまし法開始からの時間 const ll R = 10000; // スコアが悪くなったときでも、次の状態に移動する遷移する場合はtrue確率。この場合は単に１次関数を使用。 const bool FORCE_NEXT = R*(T-t)>T*(rand()%R); // スコアが良くなった or 悪くなっても強制遷移 if (nextScore>currentScore || (FORCE_NEXT && currentScore>0.0f) ) { currentScore = nextScore; // currentSeq = nextSeq; ←すでにnextSeqになってる。いらない。 printf("current Score=%.8f time=%lld\n",currentScore,t); } else { // アンドゥ。次の状態に移動しないので、バックアップしてた値に戻す currentSeq[index] = backup_value; }
とやりましょう。
★★ 逆の手で、戻す
逆の手をやれば、前の状態に高速に戻せるのであれば、そうしましょう。例えば、上下左右に駒をうごかせるというパズル問題であれば、左に動かした後、右に動かせば、戻せるかもしれません。
★★★★ スコア関数の高速化
スコア関数の求め方は問題によって大きく異なるので、計算時間も異なってきます。ボトルネックになってたら高速化しましょう。
また、スコア関数の正確さを犠牲にしてでも、高速化したほうが良い場合もあります。１つのコツとして覚えて置きましょう。
★★ C言語のrand()を使わない。
C言語のrand()は遅いので、高速なxor128を使いましょう。
unsigned int randxor() { static unsigned int x=123456789,y=362436069,z=521288629,w=88675123; unsigned int t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); }
★★ 時間計測の関数を呼びすぎない。
上にあげたコードは、時間計測の関数を呼びすぎです。。getTime関数は高速ではなく、それがボトルネックになる可能性もあります。例えば、最初のコードなら、以下のように100回に1回だけ時間を測るというようにできます。
while ((saTimeCurrent = getTime()) < saTimeEnd) // 焼きなまし終了時刻までループ { for(int loop=0; loop<100; ++loop) {
ただ、TopCoderだとループ回数を増やしすぎると、ループしている間に、制限時間オーバーしてしまうという可能性もあります。そういった点も考えて、適切な回数だけ時間をはかるようにしましょう。残り時間が少なくなったら、ループ回数を減らすといった安全策をとる方法もあります。
あと、高速化に夢中になる前に、
★★★★ 高速化がどれだけ効果的か検討する。
のも重要です。ためしに10秒だけやってる計算を、あえて100秒とかに伸ばしてみて、結果がどうなるか見てみましょう。
- 時間をかければかけるほどスコアが伸びる
- 高速化しよう＆スコアが素早く伸びるように次の状態を決めよう。山登り法に変えるのも良い。
- 時間をかけてもスコアが伸びない & スコアが高い
- 最適解がでてる可能性が高い。計算を打ち切って、余った時間を他に使う
- 時間をかけてもスコアが伸びない & スコアが低い
- 次の状態の決め方、スコア関数の見直しを再検討する。焼きなまし法を使わない法がよいときもあるのも忘れずに。
2. 次の状態（状態近傍）をどう決めるか？
ここは鍵になる部分ですが、コツとしてまとめるのは難しいところですね…。
★★★★ スコアが改善しやすくなるように、次の状態を選ぶ。
これは、問題ごとによく考えて対処しなければいけないので、あまり「コツ」というかんじではないのですが…。
[問題] タスク数aの仕事Aと、タスク数bの仕事Bがある。作業員はx人いて、それぞれ、1時間あたりにこなせる仕事Aのタスク数と、仕事Bのタスク数は決まっている。ただし、仕事Aの仕事Bのどちらかしか行うことができない。仕事Aと仕事Bの両方が終わるのに時間が最小になるように、作業員を仕事Aか仕事Bのどちらかに割り当てよ。
焼きなまし法で解くなら、まず最初にてきとーに作業員をA,Bに割り振り、ここからスコア＝作業時間として、改善させていきます。こういった問題を解くときに、次の状態として以下の２つを考えてみましょう。
- 移動：ある作業員をA→B または B→A に移動させる。
- 交換：Aの作業員の誰かと、Bの作業員の誰かを交換する。
移動２回は交換になることもあるので、とりあえず移動をさせておけば、交換もたまにしてくれるし良さそうに見えますが、そうとは限りません。この場合は、交換を主に行い、たまに移動させるぐらいがちょうど良いと思います。移動では、人数が偏り、片方の仕事の作業時間が増えやすくなります。２回移動すれば、交換になって、作業時間が減る可能性がありますが、
- 移動：良スコア → 悪いスコア → とても良いスコア
- 交換：良スコア → とても良いスコア
と考えると、移動だけだと、スコアが悪い状態を経由しないとダメなので、運がよくないと、とても良いスコアまで辿りつけません。その点、交換ならば、人員が偏った悪いスコアになりやすい状態をスキップできるので、スムーズにとても良いスコアまで改善できます。
もちろん、正しい人数割り当てもしなければいけないので、移動も少しは試したほうがいいですが、こういった点も考えて次の状態を決めると、スコアが改善しやすくなります。
★★ Greedyに、次の状態を選ぶ。
先ほどの問題であれば、「仕事Aと仕事Bそれぞれから、常に作業時間が一番多くかかっている人を1人ずつ選び、交換」とGreedyに、次の状態を選ぶことができます。こういう選び方をすると、ベストスコアは序盤はどんどん伸びていきますが、局所最適に陥りやすいです。また、ありがちなのが、Greedyに選ぶアルゴリズムが、計算時間のボトルネックになってしまうパターンです。複雑なアルゴリズムより、ランダムでとにかくいろいろ試すのが焼きなまし法の強みです。Greedyにやるにせよ、多少ランダムを入れたり、計算時間はかからない単純な選び方をしたりする工夫が必要です。
★★ 序盤は大きく変化、終盤は小さく変化させたほうがいい。
山登り法と同じ考えです。
単純にy=f(x)のyを最大化する問題なら、
- 序盤(t=0に近いとき) 次のx'は x'=x+rand()%1001 - 500
- 終盤(t=Tに近いとき) 次のx'は x'=x+rand()% 11 - 5
とか、
作業員割り当ての問題なら、
- 序盤(t=0に近いとき) 交換を100回やる
- 終盤(t=Tに近いとき) 交換を 1回やる
といったかんじです。スコアが局所最適でハマっている場合は有効です。ただ、焼きなまし法自体が、局所最適にはまりにくいアルゴリズムなので、あまり効果がない場合も多いです。
★★ 良い初期状態からスタートする
2015年5月26日 追加しました。
これは問題に大きく依存する項目です。初期状態はてきとーでも良い場合と、すこし時間をかけて計算して良い状態から始めたほうが良い場合があります。特に、初期状態が悪いと状態を改善する近傍の選択肢が少なすぎる、逆に言えば、状態を改善すればするほどさらに改善できる可能性が増えるタイプの問題は、初期状態に少し時間を書けて求めて、それから焼きなましたほうが良い結果がでる場合があります。
3. スコア関数
スコア関数（scoring function）とも、評価関数（evaluation function）とも呼びます。
★★★★★ 良い状態を正しく評価できるような、スコア関数を新たに用意する
問題のスコア関数をそのまま使うと、焼きなまし法がうまく行かないことがあります。良い状態を正しく評価できるような、新たなスコア関数を用意しましょう。
[問題] （大きく略）… i番目の人の満足値をs(i)とする。「満足度の最小値 min s(i) 」を、最大化しなさい。
この問題は「満足度の最小値 min s(i) 」を最大化する問題なので、素直に考えると、スコア＝「満足度の最小値 min s(i) 」としたくなりそうですが、これは良くありません。仮にそうした場合、
状態A s(0)= 10, s(1)=10, s(2)= 10 のとき、スコアはmin{s(0),s(1),s(2)} = 10
状態B s(0)=1000, s(1)=10, s(2)=1000 のとき、スコアはmin{s(0),s(1),s(2)} = 10と状態Aと状態Bのスコアは同じになってしまいます。これはスコアは同じといえ、状態Bのほうが明らかに良い状態です。なぜなら、s(1)の点が仮に300点に増えたとしたら
状態A' s(0)= 10, s(1)=300, s(2)= 10 のとき、スコアはmin{s(0),s(1),s(2)} = 10
状態B' s(0)=1000, s(1)=300, s(2)=1000 のとき、スコアはmin{s(0),s(1),s(2)} = 300と状態Bのほうは一気にスコアが増えます。しかし元のスコア関数のままだと状態Aと状態Bは同じスコアで、状態A→状態Bはスコア改善になりません。つまり焼きなまし法を行っても、状態A→状態Bには運が良くないと移動しません。
この問題であれば、例えば、
スコア＝1番小さいs(i) + 0.0001 * 2番目に小さいs(i)
とすれば
状態A s(0)= 10, s(1)=10, s(2)= 10 のとき、スコアは 10 + 0.0001 * 10 = 10.001 状態B s(0)=1000, s(1)=10, s(2)=1000 のとき、スコアは 10 + 0.0001 * 1000 = 10.1
と状態Bの方が好スコアになり、状態A→状態Bに移動しやすくなります。
ここは問題によって大きく有効かどうか大きく異なってきますが、必ず考慮に入れたほうがいいでしょう。結果に大差がつきやすいポイントです。
★★★スコアが改善しやすくなるようなスコア関数を決める。
2015年5月26日 追加しました
上記の言い換えともいえるのですが、わりと焼きなまし法のスコア関数をつくるときに、問題のスコア関数をそのまま使ったり、違う状態を正しく評価しなかったりすると、同じスコアになりがちで、青い線のような飛び飛びの平坦な関数になることが多いです。近傍に同じ値が続くと、焼きなまし法をやっても状態が行ったりきたりするだけで、解がなかなか改善しません。赤いように、山登りしやすいスコア関数を作れないか考えましょう。必ずしも、問題のスコア関数の最大値と、焼きなまし法で使うスコア関数の最大値が一致する必要はありません。最大値をとりうるような状態（argmax）を一致させることが重要です。
4. 遷移確率と温度
たいていの焼きなまし法の解説書には、expを使った方法が載っています。
焼きなまし法 - Wikipedia
遷移確率 P(e, e' , T) は e' < e の時に 1 を返すよう定義されている（すなわち下りの移動は必ず実行される）。
そうでない場合の確率はexp((e−e' )/T) と定義
注：wikipediaの引用なので、本文の設定と違います。
ここでのTは温度（=時間とともに減っていく値）です。
最小化問題なのでe−e'となってます（最大化問題ならe'-eです）。
★時刻tに置ける温度Tを調整する
最初の例の以下のコードの部分です。
const bool FORCE_NEXT = R*(T-t)>T*(rand()%R);
上の例だと、
- t=0のとき、常にtrue
- t=Tのとき、常にfalse
になるような線形関数にしています。だいたいの場合は、これで問題ありませんが、バリエーションはいろいろ考えられます。実際には、ベストスコアの更新状況をみて、更新があまりに序盤と終盤に固まっているときは、２乗してみるとか、ロジスティック曲線をつかうとか、その程度で良いと思います。
★★★★exp(e-e')/Tを使う。（e-e':スコアの悪化量）
2015年5月26日 重要度を★★★から上げました。全般的に内容を更新しました。
wikipediaでは以下のように書いていますが、exp(e-e')/Tの形にしたほうが良いでしょう。（理由は、次回の改定時に書きます）
関数 P は e' −e の値が増大する際には確率を減らす値を返すように設定される。 つまり、ちょっとしたエネルギー上昇の向こうに極小がある可能性の方が、 どんどん上昇している場合よりも高いという考え方である。しかし、この条件は 必ずしも必須ではなく、上記の必須条件が満たされていればよい。
ただ、このexpの式、分子はスコア差なので分かりますが、分母の温度をどう決めれば良いかは分かりづらいです。目安としては、たまには許容しても良いスコアの悪化量を温度とすると良いです。 最大の山を越えられるようにと考えると、考えられるスコアの最大値-最小値を初期温度を設定したほうが良いと思います。（理由は、次回の改定時に書きます）
double startTemp = 100; double endTemp = 10; double temp = startTemp + (endTemp - startTemp) * t / T; double probability = exp((nextScore - currentScore) / temp); // 最大化なので、分子はnextScore - currentScoreで良い。 bool FORCE_NEXT = probability > (double)(mXor.random() % R) / R;
時刻t=0（最初）でtemp=startTemp、時刻t=T（最後）でtemp=endTempとなります。
例えばスコアが100悪化したとき、nextScore - currentScore = -100なので、startTempを100にしてみます。endTempはとりあえず10にしてみましょう。
時間t=0であれば、exp(-100/100) = exp(- 1) = 0.36787944117と、3回に1回ぐらいは遷移します。
時間t=Tであれば、exp(-100/ 10) = exp(-10) = 0.00004539992と、まず遷移はしません。
このような感じでやると、良いと思います。
5. アレンジ
★★★★ 山登り
最初の例をFORCE_NEXT=0にすれば、山登り法になります。そもそも関数が凸であれば、山登り法も焼きなまし法も結果は一緒で、しかもrand()を使わない分、山登り法のほうが高速で、スコア改善のチャンスも多くなります。簡単に試せるので、試しましょう。
★ 多点スタート
2015年5月26日 重要度を★★から下げました。内容を更新しました。
焼きなまし法をつかっても、局所解にはまりやすい場合は、初期値を毎回かえた、多点スタートにする方法もあります。山登りと同時に使う方法もあります。ただ、多点スタートで結果がよくなるケースは、そもそもスコア関数や近傍が良くないので、そこを見直したほうがよいかもしれません。
★★★ 1変数ごとに焼きなまし
焼きなまし法で、たとえば、y = f(x1,x2,x3,x4,x5)と、状態変数が多いとき、次の状態のパターンが多くなり、結果的にあまり多くの状態を試せず、良い解が求められないときがあります。このような場合は、x2=x3=x4=x5を固定して、x1を焼きなまし、x1=x3=x4=x5を固定して、x2を焼きなまし、x1=x2=x4=x5を固定して、x3を焼きなましというふうに１変数ずつ焼きなまししていく方法があります。xの値がそれぞれ独立性が高い(?)場合は、この方法は有効です。 ←要検討…
