HSPポータル
サイトマップ お問い合わせ


HSPTV!掲示板


未解決 解決 停止 削除要請

2015
0413
スペース二分探索アルゴリズムについて2解決


スペース

リンク

2015/4/13(Mon) 14:51:34|NO.68530

こちらのサイトで、二分探索アルゴリズムについての説明がありました。
http://gakuen.gifu-net.ed.jp/~contents/museum/golden/page62.html
(ページ一番下です。)

黄金比(1:1.618)で分割すると最も効率がいいと書いてありますが、
中心で分割するほうが効率がいいのではないでしょうか?

試しに、プログラムを組んでみました。
ですがやはり、中心で分割したほうが効率がいいという結果が出ました。
皆さんの意見を聞かせていただけないでしょうか?


Screen 0,1100,150 randomize repeat//繰り返し行う為にルームを二重に ct = double(cnt+1)//試行回数を記録する 目標点 = rnd(1000)//探索するポイントを設定 地点A = 0//探索開始地点 地点B = 1000//探索終了地点 repeat 20 //中心点=( double(地点B-地点A) *0.382)+地点A//地点AとBの"黄金比"を計算 中心点=( double(地点B-地点A) /2.0)+地点A//地点AとBの中心点を計算 gosub*描画:await 500//描画 if 中心点<目標点 : { 地点A=中心点 } else{ 地点B=中心点 }//中心点より左or右に目標点があるのか判定 gosub*描画:await 500//描画 if (地点B-地点A) <= 10 : { 合計cnt + cnt:title "平均探索回数(cnt)="+(double(合計cnt)/ct)+"":await 500:break }//地点AとBの範囲が一定の値以下になったら終了 loop await loop *描画//なんやかんや描画 color 150,150,150 : boxf color 255,0,200 : pos 中心点,100 : mes "P" color 255,255,0 : pos 目標点,120 : mes"★" color 255,0,0 : pos 地点A,120 : mes "●" color 0,0,255 : pos 地点B,120 : mes "●" color 0,0,0 : pos 10,10 : mes "地点A="+int(地点A)+"\n地点B="+int(地点B)+"\n中心点="+int(中心点)+"\n目標点="+int(目標点)+""//左上に情報を表示 return



この記事に返信する


沢渡

リンク

2015/4/14(Tue) 17:37:02|NO.68564

「黄金分割法」についてはちょっと調べただけなので、トンチンカンな事を言ってたら申し訳ないのですが、
そのページに載っているたとえ話は、「黄金分割法」のたとえ話としては不適切なのではないでしょうか?

どうも、そのページは古いページのようで、同じ「岐阜県まるごと学園」のサイト内で
新しいページを見つけたのですが、こちらはたとえ話の内容がより適切なものになっているようです。
http://gakuen.gifu-net.ed.jp/~contents/museum/golden/page62_5.html

二分法の説明に「この方法のポイントは、『目標物がそのどちらに属するかが判断できるとき』に
大変有効な方法であり」とありますので、古いページに載っているような例(水道管云々)の場合は、
やはり二分法の方が適切なのではないでしょうか。



スペース

リンク

2015/4/15(Wed) 10:58:00|NO.68568

>沢渡さん
やはりページの例えの問題でしたか。
新しいページの方もあったとは知りませんでした・・・
色々と調べていただき、本当にありがとうございますm(__)m



ONION software Copyright 1997-2021(c) All rights reserved.