アカウント名:
パスワード:
・近似比保証のある解(近似解)が得られる場合(いわゆる近似アルゴリズム)・目的関数値の理論保証はないが,実用上それなりに良い解が得られる場合(ヒューリスティクス,D-waveなどの量子アニーリングはココ)
この二つの違いがわからないんですが。
書いてあるまんまだと思いますが。。。例えば、極小値(くぼみ)が2か所(a,b(ただしab))ある曲面での最小値を見つける場合、近似アルゴリズムだとa付近の値が解として得られる(b付近の値が解として得られることは無い)。ヒューリスティクスやアニーリングだとb付近の値が解として得られる場合がある。
違います。その理解だと、「近似アルゴリズム」で最適解まで到達できちゃいませんか? aのくぼみの近くに居るならそこから単純に坂を下ればaの底に到達できるので。くぼみが無数にある場合でも、a<b<c<d<…だったら、こっちの方が小さい、を繰り返してaに到達できそうですし。
a、b、c、…と無数にくぼみがあって究極のくぼみがzだった時に、zの定数倍以内に収まるくぼみが必ず選ばれる、というような保証があるものが近似アルゴリズムです。他にも設定した以上の確率で必ずzに到達できる近似アルゴリズム、とか、保証される内容は色々です。
要は、
解が有理数であればね。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
192.168.0.1は、私が使っている IPアドレスですので勝手に使わないでください --- ある通りすがり
誰か教えてください (スコア: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)
解が有理数であればね。