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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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++;

}

}

数値積分（とくに台形公式）

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

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

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

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

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

分布数えソート

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

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

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

# 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型の、誤差の分配の手続きで代用してしまう、という形です。