アカウント名:
パスワード:
・近似比保証のある解(近似解)が得られる場合(いわゆる近似アルゴリズム)・目的関数値の理論保証はないが,実用上それなりに良い解が得られる場合(ヒューリスティクス,D-waveなどの量子アニーリングはココ)
この二つの違いがわからないんですが。
書いてあるまんまだと思いますが。。。例えば、極小値(くぼみ)が2か所(a,b(ただしab))ある曲面での最小値を見つける場合、近似アルゴリズムだとa付近の値が解として得られる(b付近の値が解として得られることは無い)。ヒューリスティクスやアニーリングだとb付近の値が解として得られる場合がある。
違います。その理解だと、「近似アルゴリズム」で最適解まで到達できちゃいませんか? aのくぼみの近くに居るならそこから単純に坂を下ればaの底に到達できるので。くぼみが無数にある場合でも、a<b<c<d<…だったら、こっちの方が小さい、を繰り返してaに到達できそうですし。
a、b、c、…と無数にくぼみがあって究極のくぼみがzだった時に、zの定数倍以内に収まるくぼみが必ず選ばれる、というような保証があるものが近似アルゴリズムです。他にも設定した以上の確率で必ずzに到達できる近似アルゴリズム、とか、保証される内容は色々です。
要は、どのくぼみにハマるか分からないものがヒューリスティックなアルゴリズムと呼ばれ、何かしら「絶対こうなる事が保証される」という部分があるのが近似アルゴリズムです。そして保証する分、計算により多くの時間が掛かるので実用性で言うとヒューリスティックなものに大抵軍配が上がるという数学者の玩具なジャンルです。
何が保証されるのかは数学者の腕の見せ所で、まだ誰も見つけてない部分を保障する方法を見つけたら良い業績になります。裏を返すと、ちょっと思いつく程度のやつはだいたい網羅されてます。
解が有理数であればね。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
開いた括弧は必ず閉じる -- あるプログラマー
誰か教えてください (スコア:0)
・近似比保証のある解(近似解)が得られる場合(いわゆる近似アルゴリズム)
・目的関数値の理論保証はないが,実用上それなりに良い解が得られる場合(ヒューリスティクス,D-waveなどの量子アニーリングはココ)
この二つの違いがわからないんですが。
Re: (スコア:0)
書いてあるまんまだと思いますが。。。
例えば、極小値(くぼみ)が2か所(a,b(ただしab))ある曲面での最小値を見つける場合、
近似アルゴリズムだとa付近の値が解として得られる(b付近の値が解として得られることは無い)。
ヒューリスティクスやアニーリングだとb付近の値が解として得られる場合がある。
Re:誰か教えてください (スコア:0)
違います。その理解だと、「近似アルゴリズム」で最適解まで到達できちゃいませんか? aのくぼみの近くに居るならそこから単純に坂を下ればaの底に到達できるので。くぼみが無数にある場合でも、a<b<c<d<…だったら、こっちの方が小さい、を繰り返してaに到達できそうですし。
a、b、c、…と無数にくぼみがあって究極のくぼみがzだった時に、zの定数倍以内に収まるくぼみが必ず選ばれる、というような保証があるものが近似アルゴリズムです。他にも設定した以上の確率で必ずzに到達できる近似アルゴリズム、とか、保証される内容は色々です。
要は、どのくぼみにハマるか分からないものがヒューリスティックなアルゴリズムと呼ばれ、何かしら「絶対こうなる事が保証される」という部分があるのが近似アルゴリズムです。そして保証する分、計算により多くの時間が掛かるので実用性で言うとヒューリスティックなものに大抵軍配が上がるという数学者の玩具なジャンルです。
何が保証されるのかは数学者の腕の見せ所で、まだ誰も見つけてない部分を保障する方法を見つけたら良い業績になります。裏を返すと、ちょっと思いつく程度のやつはだいたい網羅されてます。
Re: (スコア:0)
解が有理数であればね。