-
hirokazu1020
- 28086
- 6
- 18
- 9
-
- いいね！9
コルン
@colun
https://t.co/ZmjsHqamFn これについて１つ補足しておきますが、与えられた「解」の評価関数と、「解のクラスタ」に適した評価関数とは、必ずしも一致するとは限らないので、マラソンマッチにおいて評価関数が楽というのは、たぶん嘘じゃないかなと。。。
2013-12-27 02:03:28
chokudai(高橋 直大)@AtCoder社長
@chokudai
まぁ、前回のMM82なんかだと、解の評価値そのまま使って失敗している人が多分たくさんいたのだけれども（前半はペナルティだけを評価値として見たほうが良い）、大抵の場合はそのまま使っても有効な場合が多いと思うなぁ。
2013-12-27 02:05:32
コルン
@colun
たとえばA～Zのアルファベットから、３つのアルファベットを選べという問題があったとします。ここで、アルファベットを１つだけ選んだ状態……これは「解」ではありませんが、すべての解から部分的に制限がかかっている解の集合であると見なせます。
2013-12-27 02:06:14
chokudai(高橋 直大)@AtCoder社長
@chokudai
評価関数と距離でなんか混同している人がいるっぽいので、適当な例を出そうなんかフィールドが与えられるから、トの字型のブロックを出来るだけ敷き詰める問題。 http://t.co/sSGJf806bP
2013-12-27 02:06:35
拡大
chokudai(高橋 直大)@AtCoder社長
@chokudai
これは、近傍の設定方法超大量にあるわけで。 たとえば、あんまり有効じゃなさそうだけど、この図のように、適当に３×３を選んで、そこに被っているブロックを取り除いて http://t.co/DiHbO1kOTM
2013-12-27 02:10:14
拡大
chokudai(高橋 直大)@AtCoder社長
@chokudai
再配置してみる、みたいな近傍の取り方とかあるわけですよ。良いかどうかは別問題ね。 http://t.co/h9C3xqpT5c
2013-12-27 02:10:40
拡大
chokudai(高橋 直大)@AtCoder社長
@chokudai
んで、こんな感じで解を作った時に、例えば以下の２つは、評価値は両方７だし、おそらく両方正解なのだけれども、今回の定義において、解同士が近いか、と言われたら、多分かなり遠いよね。 http://t.co/bPRbZbvqsu
2013-12-27 02:14:58
拡大
chokudai(高橋 直大)@AtCoder社長
@chokudai
ただまぁ、距離が近いところに同じ評価値７のものも存在するわけだ。たとえばここの赤と青を変えただけとか、今回の定義だと、むっちゃ距離近そうだよね。 http://t.co/CmY7BIZPuQ
2013-12-27 02:22:46
拡大
chokudai(高橋 直大)@AtCoder社長
@chokudai
んじゃ、今度は別の近傍の定義をしてみよう。ランダムに２つのブロックを選択し、除去。 http://t.co/ndoGtnZ1tl
2013-12-27 02:25:41
拡大
chokudai(高橋 直大)@AtCoder社長
@chokudai
その後、同じように再配置するような近傍の取り方をしてみるとしよう。 http://t.co/5a8qLA4L6U
2013-12-27 02:27:06
拡大
chokudai(高橋 直大)@AtCoder社長
@chokudai
やってること自体は、除去するブロックの選び方だけなんだけど、これで、さっきのと、「近い状態」「遠い状態」がそこそこ変わってるのが、イメージしてもらえると解ると思います。たとえば、「離れているの３つの向きが入れ替わった」とか「５０＊５０の領域の中で、７＊７の中のみ入れ替わった」とか
2013-12-27 02:29:08
chokudai(高橋 直大)@AtCoder社長
@chokudai
まぁそうなった時に、「どっちの探索空間の方が、解が纏まってるか？解に辿り着きやすいか？」ってのを考えるわけです。 近くを一気に動かして探索するべきなのか、それともばらばらにたくさん変えてみるべきなのか。
2013-12-27 02:31:44
chokudai(高橋 直大)@AtCoder社長
@chokudai
まぁこうなった時に、手法はいくつかあって、「両方組んで両方試してみる」というのが一番簡単。「どっちの方が良い」という根拠があれば、とりあえずそっちを優先してやってみる。って話です。
2013-12-27 02:33:51
chokudai(高橋 直大)@AtCoder社長
@chokudai
例えばこの２択を迫られたら、自分としては、「詰まり具合が十分担保された状態を端から伝搬させていきたい」という理由で、３＊３の範囲で除去再配置、というのをまず選択します。「どういう風になるのが良いかな？」「どういう風にすれば良い解が固まるかな？」みたいなのを考えてあげましょう。
2013-12-27 02:34:35
chokudai(高橋 直大)@AtCoder社長
@chokudai
まぁ経験則として、「ランダムに２つ変える」というのは論外で、それをやるならほぼ「ランダムに１つ変える」の方が良いと思っていて、それだと嵌るパターンが出るので、やっぱりこの方針は微妙なんじゃないのかな？固まって変えないとだめじゃないのかな？みたいな思考の流れになるかな。
2013-12-27 02:35:44
chokudai(高橋 直大)@AtCoder社長
@chokudai
だからまぁ、こういう問題に関しては、ほんとに「どういうところに良い解があるか？」ってのを自分でイメージして考えてあげないといけないので、常に使える一般的なテクニック、ってのは、ある程度感覚としてはあるところもあるけど、やっぱ毎回考えてあげるしかないんじゃないのかなぁ、と思ってます
2013-12-27 02:36:53