[過去ﾛｸﾞ] プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
321(5): 318 2017/07/06(木)00:31 ID:iCfNzc8Y(1/4) AAS
>>320
誤解です。
枝刈りは、ある探索中の枝において始点から既に経過した秒数が
それまでの別の枝における探索で最後まで食べた最小秒数を超過したら、
現在の枝の探索はもうこれ以上進んでも秒数が増える一方なので打ち切って
別の枝の探索に移るというものなので大丈夫です。
"3324" の最短秒数を探索すると 15秒になります。
322(1): 2017/07/06(木)00:52 ID:ywrsmrRJ(1/3) AAS
>>321
あれ、変だな
>>318のリンク先のコードで"3324"を計算すると 16 になるんだけどこっちの環境が変なのかな？
同様に"3328"、"3364"は最短19秒だけど>>318だと20になった
327(1): 2017/07/06(木)21:08 ID:ywrsmrRJ(2/3) AAS
>>326
結局>>321は大嘘だったし、閾値20の>>323にしたところで
例えば"14432"は最短にならないし
閾値が決められないならその解法はやはり駄目だな
328(1): 318 2017/07/06(木)22:03 ID:0agEc1HZ(1/4) AAS
>>327
閾値20で打ち切ると最小に至らない入力もあるのはそうだけど、
計算しても最小を更新しない枝に降りずに切り上げてくる>>321は嘘ではないよ。
330(1): 2017/07/06(木)23:01 ID:ywrsmrRJ(3/3) AAS
>>328
閾値20で打ち切るのは枝切りじゃないという主張のようだけど
打ち切るという動作は枝切り以外の何物でもない
>>318は”3324”の最短に到達しないから>>321の
> "3324" の最短秒数を探索すると 15秒になります。
というのも嘘
331: 318 2017/07/06(木)23:19 ID:0agEc1HZ(3/4) AAS
>>330
絡むね。そんな暇あったらコードでも書けばいいのにｗ
閾値20でその入力については解の探査を止めて
別の枝に移らず次の入力データに移るのはどちらかといえば中断で、
枝かりではないでしょ。
>319
> >>318
> 書き忘れたけど、食事秒数を探索中に、それまでに見つかっている最小病数を超えたら
> 打ち切るという、簡単な枝刈りを取り入れてあります。
にかいてあるでしょうに。
省5
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.044s