「不正確だが楽に解ける」解法のある数学的問題を教えてください。


たとえば「1〜10の玉の非復元抽出」という問題に対し、
乱数を割り当て、乱数順に玉を並び替える方法は、
「正しい」方法だと思いますが、
途中のソートのプログラムが、初心者には厄介です。

で、たとえば最初は1〜10まで順番に並べ、
ランダムに2つを抜き取って入れ替える、という作業を十分な回数、行う
という方法は、本当はズルですけど、玉の数が少ない場合、
十分、実用的で、シロウトにもわかりやすいですよね。

この例のように、

 [1] 問題を無駄なく正確に解こうとすると、混みいったアルゴリズムが必要だが
 [2] ある程度の無駄や、わずかな確率のミスを許すなら、ものすごく単純なアルゴリズムが存在し
 [3] 状況によっては十分、実用的で
 [4] 素人にもわかりやすい
 [5] ある程度・数学的もしくはコンピュータ的な

問題と、その楽ちんな解法を教えてください。そのような問題を紹介しているHPでもOKです。

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2005/07/16 22:42:03
  • 終了:--

回答(3件)

id:yasyas No.1

yas回答回数117ベストアンサー獲得回数02005/07/16 23:42:07

ポイント30pt

GA(遺伝的アルゴリズム)によるTSP(巡回セールスマン問題)なんていかがでしょうか?


あるセールスマンが数十箇所の拠点を営業する際にもっとも短距離で回る経路はどれか?

という問題で、以下の条件があります。


・すべての拠点から任意の拠点へ移ることが出来る(すべての拠点からすべての拠点へ移ることが出来る)

・ただし拠点は一度通ると、2度と通れない。

たとえば拠点数がNとした場合、通る経路のパターンは(N-1)!/2(スタートの拠点が決まっていて、逆の進路を認めない場合)となり、

Nが数十を超える場合、すべてのパターンを調べようとすると、コンピュータでも数年かかってしまう場合があります。

そのときにGAを用いると、比較的現実的な時間で経路を探索することができます。ただし、GAは最適経路を保障するものではありません(そのため”現実的な”という文言が入ります)。

URLはその遺伝的アルゴリズムを解説したもので、途中にあるフローを見ていただくとわかるとおり、生物の進化を模倣した単純なアルゴリズムで計算されます。

このGAはTSPに限らず、無数と言えるような組み合わせの中からもっとも最適な解を探し出す方法として知られています(スケジューリング問題等)。


ちょっと有名すぎたでしょうか?

そのたGAを代表とするソフトコンピューティング(カオス・ニューラル・強化学習)をまとめたサイトをご紹介します。

id:lionfan

yasyasさん、ありがとうございます!!

ただ・・・なんと不運なことに、たまたま昔、僕はGAを専門にしていたのですな。

あと、TSP問題は、問題そのものは単純ですが、「GAでの解法」は、数行〜数十行で簡潔に、正確に(素人でも手順を再現できる、という意味で)説明することは難しいですよね。

解法も単純に説明できるものがいいのです。

たとえば迷路でしたら、離れ小島がない限り、

「右側の壁に手をつけてとにかく歩けば、いつかは出口に着く」と言えますよね。

それ的な、もう少しだけ数学っぽいものがいいです。

というわけで、すみません申し訳ございませんが、続行させてください。

なかなかいいお答えですし、Gaを知っている方がいるとはうれしいので、ポイントは最低でも平均分は差し上げます。

あと以後の方、10個もしくは1日くらいは待ちます。あせらずゆっくりどうぞ。

2005/07/16 23:54:32
id:masasan No.2

masasan回答回数143ベストアンサー獲得回数22005/07/17 00:52:00

ポイント30pt

形の決まった図形の、面積や体積を求める方法。


などはどうでしょう。上記URLでは球なので各球の位置と大きささえ分かれば手計算でも求められますが、ベジェ曲線や他複雑な形を規定された図形は数学的にあるいはコンピュータで正確な数値を求めるのは困難です。

乱数と、該当図形境界の内外判定だけで、楽ちんに求めちゃいましょ。

id:lionfan

ありがとうございます。いわゆる「モンテカルロ・シミュレーション」ですね。

紹介のURLにあった

>統計解析フリーソフト R では,一様乱数を求めるアルゴリズムに

>メルセンヌ・ツイスターが用いられている

という説明が面白かったです。満足です。

まだまだ募集します。ごゆっくりどうぞ。

2005/07/17 01:00:22
id:shampoohat No.3

shampoohat回答回数347ベストアンサー獲得回数02005/07/17 01:39:17

ポイント100pt

何か、ずばりと来るものが頭の片隅にあったような気がし(多分、f(x+dx) の dx が小さいときはf(x+dx) = f(x) + f’(x)*dx と近似できることを利用した何かの計算を思い出そうとしていただけのような気がします)、違う違うと思いながら列挙したものが下記です。


ブレインストーミング的で未整理な点について申し訳なく思いますが、参考になりましたら幸いです。

http://www.geocities.jp/turtle_wide/softcomp/al/p03.htm

モンテカルロシミュレーションで円周率を求める

モンテカルロ法で円周率を求める


for(int i=0; i<times; i++){

//落とす位置を乱数で決定

x = rnd.nextDouble();

y = rnd.nextDouble();

//落とした点の原点からの距離を測る

dist = Math.sqrt( x*x + y*y );

//円の内側ならcinを加算

if(dist < 1){

cin++;

}

}


http://www.rikkyo.ne.jp/~susa/comp_intro/9th.htm

���X���FFortran-���l�ϕ�

数値積分(とくに台形公式)


不定積分を求めるのは大変で、なおかつ、求まらないかもしれないので。微分についても同様ですよね。

→ これは類似したものを2番の方が回答に入れてくださっていますね。

組み合わせ最適化問題(ここではknapsack問題)の貪欲法での解法


1番目の方の回答を拝見して、ふと思いましたが、「適当にランダムで組み合わせを変えることを組み合わせて、最小記録を採用する」ことで例題と同じになりますね。また、「ランダムサーチをもっと上手にやるとGAになりますね」と書くと怒られますでしょうか?

http://e-words.jp/w/E8A5BFE69AA62000E5B9B4E5958FE9A18C.html

西暦2000年問題とは 【Y2K】 ─ 意味・解説 : IT用語辞典 e-Words

これは微妙ですけど、どうでしょうか?

http://www2.starcat.ne.jp/~fussy/algo/algo5-4.htm

$B%=!<%H!&%k!<%A%s(B (4)$B%/%$%C%/!&%=!<%H(B

分布数えソート


も該当するような気がします。

CGでアンチエイリアス付でのレンダリングを行う際に、「2倍解像度でレンダリングしてから縮小する」アルゴリズムがあります。


以前、某るパソコン雑誌で「安易エイリアス」として紹介されてしたものです。

# URLは、「アンチエイリアス」の用語の紹介です。

思い出そうとしていたのは、これかもしれません。


画像の誤差拡散用のアルゴリズムについて、厳密に誤差を最小化しようとすると意外に大変なのですが、経験的に作られた下記のものが非常に有名です:


-----------------------

Er(i,j)を位置(i,j)における誤差と呼び、これを注目点の右隣(i+1,j)、右下(i+1,j+1)および下(i,j+1)の各点に次のように配分する。

  f’(i+1,j)=f(i+1,j)+Er(i,j)×3/8 (2)

  f’(i+1,j+1)=f(i+1,j+1)+Er(i,j)×1/4 (3)

  f’(i,j+1)=f(i,j+1)+Er(i,j)×3/8 (4)

-----------------------


誤差拡散をきちとしようとした場合の、「組織ディザ法」と、

簡便に類似の結果を得ることが出来るFloyd & Steinberg型の、誤差の分配の手続きです。


言い方としては、「組織ディザ法」に相当する最適化したいが、プログラミングが大変なので、近似的な結果が得られるFloyd & Steinberg型の、誤差の分配の手続きで代用してしまう、という形です。

id:lionfan

shampoohatさん、「分布数えソート」「安易エイリアス」「誤差拡散法 」は、はじめて見ました。とても面白いです。

こんなにたくさん、ありがとうございます。うれしかったです。

2005/07/17 01:46:54

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません