第12回木构造.ppt

FAN06 移動知OS FAN06 移動知OS * 第2回課題 解答?解説 やらせたい仕事：100個の点について，最も近い2点間距離を求める 点が6つの場合… 点 P0 と点 P3 の間の距離：dist(p[0], p[3]) P2 P0 P3 P1 P4 P5 * 第2回課題 解答?解説 2つの点の全ての組み合わせの距離を計算して，その中で最短の距離を求めればよい．つまり，100点から2点を取る組み合わせを総当たりで探さなくてはならない． 線分で結ぶときの1点目は0番から4番まで．2点目は1点目に選んだ点の次の点から5番までを選択 組み合わせの数： NUMC2 点が6つの場合… → これが距離計算の回数 P2 P0 P3 P1 P4 P5 * 第2回課題 解答?解説 では，これをプログラム上でどのように書けばよいだろうか？ まずはしらみつぶしで距離を計算する． 二重ループ：「1点目を選ぶループ」があり，その中に「2点目を選ぶループ」が回っているようにする． for (i = 0; i NUM-1; i++) for (j = i+1; j NUM; j++) 距離＝dist(p[i], p[j]); これで，全ての2点間の距離を計算することはできる． では次に，最小距離をどうやって求めるか？ 1点目を選ぶループ 2点目を選ぶループ * 第2回課題 解答?解説 「今のところの最短距離」を変数として保持しておき，2点間距離を計算するつどその距離をこの変数と比較して，計算した距離が変数の値未満であれば更新する． 注意：初期化を忘れない．変数を宣言した時点では変数にはでたらめな数が入っている．これを「あり得ないぐらい大きな値」あるいは1サンプルで初期化する． min = dist(p[0], p[1]); for (i = 0; i NUM-1; i++) for (j = i+1; j NUM; j++) if (min dist(p[i], p[j])) min = dist(p[i], p[j]); minの初期化 比較 更新 * 第2回課題 解答?解説 距離計算関数 dist() の呼出回数を更に減らすには このやり方では，更新が行われる場合，比較時と更新時で二重に関数を呼び出してしまっている．変数を新たに使って，これを1回にすることができる． さっきのやり方だと… min = dist(p[0], p[1]); for (i = 0; i NUM-1; i++) for (j = i+1; j NUM; j++) if (min dist(p[i], p[j])) min = dist(p[i], p[j]); min = dist(p[0], p[1]); for (i = 0; i NUM-1; i++) for (j = i+1; j NUM; j++) if (min dist(p[i], p[j])) min = dist(p[i], p[j]); * 第2回課題 解答?解説 距離計算関数 dist() の呼出回数を更に減らすには double d; min = dist(p[0], p[1]); for (i = 0; i NUM-1; i++) for (j = i+1; j NUM; j++) { d = dist(p[i], p[j]); if (min d) min = d; } 変数 d の宣言 まず d に代入 比較?更新には d を利用する * 第2回課題 解答?解説 関数 dist() は平方根の計算などがあり，重い．計算時間のボトルネックはこの関数となっている． 変数dを使えば，関数 dist() の呼出回数は，(初期化の1回)＋(100点から2点を選択する組み合わせの数)と等しく， 100C2 +1 = 100×99÷2 +1＝4951 (回) 変数dを使わなかった場合，minの更新が起こる回数だけ余分に呼出をするので，その余分な回数が最低で0回，最高だと毎回になり4949 (回)．従って全呼出回数は4951回から9900回になる． より一般的に，点の数が n であるときは， nC2 +1 = n(n-1)/2 + 1 (回) となる． * 第2回課題 解答?解説 まとめると… 「全ての2点間について」? 二重ループによる繰返し 「距離の最小値を」? 変数 min の初期化と更新 この左側が人間に指示するときの言い方，右側がコンピュータに対す