[過去ﾛｸﾞ] プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net (1002ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
321(5): 318 2017/07/06(木)00:31 ID:iCfNzc8Y(1/4) AAS
>>320
誤解です。
枝刈りは、ある探索中の枝において始点から既に経過した秒数が
それまでの別の枝における探索で最後まで食べた最小秒数を超過したら、
現在の枝の探索はもうこれ以上進んでも秒数が増える一方なので打ち切って
別の枝の探索に移るというものなので大丈夫です。
"3324" の最短秒数を探索すると 15秒になります。
323(2): 318 2017/07/06(木)01:20 ID:iCfNzc8Y(2/4) AAS
>>322
同じコードをideoneに張りなおして3324を入力して実行してみました。
外部ﾘﾝｸ:ideone.com
ソースを一箇所編集しています。
31 die if $hit >= 20; # 一定以上同じ最小値が繰り返し計算されたら収束と判定し脱出
の繰り返し回数上限判定地を10から20に増やしています。
3324は15になりますが、15が登場するのは11回目以降でそれまで16が出続けます。
3364も20が10回繰り返した後19が出て続きます。
省3
324: 318 2017/07/06(木)01:35 ID:iCfNzc8Y(3/4) AAS
>>323
3324と3364の解を見ていて気が付いた点があります。
一定以上同じ最小値が繰り返し計算されたかの判定値を20にしていますが、
3324の15や3364の19は20ではなくて13回しか現れず、これが最小値のため
解として表示されています。
これは、3324の15や3364が4桁しかないので、
最小値が20回現れる前に全探査が完了し、その中で見つかった最小値を
解として表示していることによります。
>>318の一定回数繰り返したら収束とみなすという判定方法は、
ニュートン法のような数値計算では有効ですが、
省1
326(1): 318 2017/07/06(木)02:06 ID:iCfNzc8Y(4/4) AAS
>>325
延々探索を続けないと解に至らないかもしれない入力については
定数で打ち切りを決めるこの解法じゃ解に至りにくいかもしれない。
887654329がそういったカテゴリーに属する入力かというと
ﾁｮｯﾄ分からない。
なので適切な閾値はこれだと断言しにくいです。
さーせん
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.043s