[過去ﾛｸﾞ] プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
318(12): デフォルトの名無しさん [sage] 2017/07/04(火)21:28 ID:QK6Kginy(1/2)
>>296 >>299 Perl5
http://ideone.com/0yJ5U9

リスト処理ではなく、先ずは正規表現と文字列処理を使って書いてみた。

3１…の3のように、食べているうちに後続の数値皿が通り過ぎてしまうような、
取りこぼしを起こし得る皿では、その数値を食べるか、あるいはスルーするか、
再帰的に両方に分岐し、木構造で計算しているが、
逆に食べている間に飛び越しを起こさないところでは、分岐が不要なので
来た順に直ちに食べることによって、枝分かれの過剰な細分化を抑制した。

それでも全探査すると、サンプルデータの三つ目まではすぐ解けるが、
四つめ以降は時間がかかりいつ終わるか分からない。

そこで、検索された食事秒数の最小値の更新状況を記録し、
同じ最小値が一定回数以上連続して繰り返し検出されるようになったら
最短値に収束したと見なし、探索を打ち切ることによって短時間で
解を出力できるようにした。打ち切り上限は10をハードコードしてあるが
今回のサンプルデータについては4か5で十分そうだ。

なお、23_ のような、2を食べることによって飛び越しを起こすポイントの
一番最後のものは,食べずにスルーして先に2を食べた方が、
次の周で早く食べ終わることは明らかだ。
これを演繹的に繰り返して、遡ってゆけば、上記のように木構造に
わたって動的に計算して探索しなくても、静的に求解できそうな気がしたが
難しそうなので、見送った。
319(2): デフォルトの名無しさん [sage] 2017/07/04(火)21:31 ID:QK6Kginy(2/2)
>>318
書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら
打ち切るという、簡単な枝刈りを取り入れてあります。

連投ｽﾏｿ
320(1): デフォルトの名無しさん [sage] 2017/07/04(火)23:51 ID:sQGcZTdy(1)
>>318
枝刈りで最短を刈り取ってしまったら駄目じゃないか
例えば "3324" -> 15秒 にならないな
321(5): 318 [sage] 2017/07/06(木)00:31 ID:iCfNzc8Y(1/4)
>>320
誤解です。
枝刈りは、ある探索中の枝において始点から既に経過した秒数が
それまでの別の枝における探索で最後まで食べた最小秒数を超過したら、
現在の枝の探索はもうこれ以上進んでも秒数が増える一方なので打ち切って
別の枝の探索に移るというものなので大丈夫です。
"3324" の最短秒数を探索すると 15秒になります。
322(1): デフォルトの名無しさん [sage] 2017/07/06(木)00:52 ID:ywrsmrRJ(1/3)
>>321
あれ、変だな
>>318のリンク先のコードで"3324"を計算すると 16 になるんだけどこっちの環境が変なのかな？
同様に"3328"、"3364"は最短19秒だけど>>318だと20になった
323(2): 318 [sage] 2017/07/06(木)01:20 ID:iCfNzc8Y(2/4)
>>322
同じコードをideoneに張りなおして3324を入力して実行してみました。
http://ideone.com/vXrTp8

ソースを一箇所編集しています。

31 die if $hit >= 20; # 一定以上同じ最小値が繰り返し計算されたら収束と判定し脱出

の繰り返し回数上限判定地を10から20に増やしています。

3324は15になりますが、15が登場するのは11回目以降でそれまで16が出続けます。
3364も20が10回繰り返した後19が出て続きます。

お手数おかけしますが
一定以上同じ最小値が繰り返し計算されたかの判定値を10より多くして
評価してください。
324: 318 [sage] 2017/07/06(木)01:35 ID:iCfNzc8Y(3/4)
>>323
3324と3364の解を見ていて気が付いた点があります。

一定以上同じ最小値が繰り返し計算されたかの判定値を20にしていますが、
3324の15や3364の19は20ではなくて13回しか現れず、これが最小値のため
解として表示されています。
これは、3324の15や3364が4桁しかないので、
最小値が20回現れる前に全探査が完了し、その中で見つかった最小値を
解として表示していることによります。

>>318の一定回数繰り返したら収束とみなすという判定方法は、
ニュートン法のような数値計算では有効ですが、
>>296の問題の解の判定方法としては適切とは言えないかもしれませんね…orz
326(1): 318 [sage] 2017/07/06(木)02:06 ID:iCfNzc8Y(4/4)
>>325
延々探索を続けないと解に至らないかもしれない入力については
定数で打ち切りを決めるこの解法じゃ解に至りにくいかもしれない。
887654329がそういったカテゴリーに属する入力かというと
ﾁｮｯﾄ分からない。
なので適切な閾値はこれだと断言しにくいです。
さーせん
328(1): 318 [sage] 2017/07/06(木)22:03 ID:0agEc1HZ(1/4)
>>327
閾値20で打ち切ると最小に至らない入力もあるのはそうだけど、
計算しても最小を更新しない枝に降りずに切り上げてくる>>321は嘘ではないよ。
329: 318 [sage] 2017/07/06(木)22:08 ID:0agEc1HZ(2/4)
見込みの無い枝をもっと早めに切り上げらる方法がありそうだと気が付いた。
それによって20で打ち切るようなやり方を改善できればいいんだけれども…
それでも計算量が増えていくと、真の解に至るまでにかかる時間が増大して
とけなくなる
330(1): デフォルトの名無しさん [] 2017/07/06(木)23:01 ID:ywrsmrRJ(3/3)
>>328
閾値20で打ち切るのは枝切りじゃないという主張のようだけど
打ち切るという動作は枝切り以外の何物でもない

>>318は”3324”の最短に到達しないから>>321の
> "3324" の最短秒数を探索すると 15秒になります。
というのも嘘
331: 318 [sage] 2017/07/06(木)23:19 ID:0agEc1HZ(3/4)
>>330
絡むね。そんな暇あったらコードでも書けばいいのにｗ

閾値20でその入力については解の探査を止めて
別の枝に移らず次の入力データに移るのはどちらかといえば中断で、
枝かりではないでしょ。

>319
> >>318
> 書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら
> 打ち切るという、簡単な枝刈りを取り入れてあります。
にかいてあるでしょうに。

>>318は”3324”の最短に到達しないから>>321の
> "3324" の最短秒数を探索すると 15秒になります。
>というのも嘘

これは10回の打ち切りの緩和を書きもらしたんだよ。

何が狙いで、こだわって絡んでくるやらねぇ。
332: 318 [sage] 2017/07/06(木)23:37 ID:0agEc1HZ(4/4)
「打ち切る」という言葉を

>318
>…
>同じ最小値が一定回数以上連続して繰り返し検出されるようになったら
>最短値に収束したと見なし、探索を打ち切ることによって短時間で
>解を出力できるようにした。打ち切り上限は10をハードコードしてあるが

では「その入力に対する求解を中断する」ところで使い、

>319
> >>318
> 書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら
> 打ち切るという、簡単な枝刈りを取り入れてあります。

では「その枝の下の方への探索をせず、別の枝の探索に移る」枝刈りの
ところで使ったのが誤解を招いてしまったのかな…
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.051s