アカウント名:
パスワード:
・近似比保証のある解(近似解)が得られる場合(いわゆる近似アルゴリズム)・目的関数値の理論保証はないが,実用上それなりに良い解が得られる場合(ヒューリスティクス,D-waveなどの量子アニーリングはココ)
この二つの違いがわからないんですが。
書いてあるまんまだと思いますが。。。例えば、極小値(くぼみ)が2か所(a,b(ただしab))ある曲面での最小値を見つける場合、近似アルゴリズムだとa付近の値が解として得られる(b付近の値が解として得られることは無い)。ヒューリスティクスやアニーリングだとb付近の値が解として得られる場合がある。
それって単に局所解ですよね。ヒューリスティクスや量子アニーリングって局所解に(も)近似しちゃうの?
パラメータ次第ですね谷(局所解)から別の谷に行くためには、ポテンシャルの山を越える必要があるので、それを越えられるようなパラメータ(打切り条件)が必要ですただこの条件が緩すぎると収束せずにずっと探索して効率悪くなる# 遺伝的アルゴリズムだと突然変異でこれを越えるんだけど、その発想は面白いなと思ったし、自然界すげーとも思った
なお量子ゲートを使った量子コンピュータだと、量子ビットが十分なら最適解が求まるはず
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
犯人は巨人ファンでA型で眼鏡をかけている -- あるハッカー
誰か教えてください (スコア:0)
・近似比保証のある解(近似解)が得られる場合(いわゆる近似アルゴリズム)
・目的関数値の理論保証はないが,実用上それなりに良い解が得られる場合(ヒューリスティクス,D-waveなどの量子アニーリングはココ)
この二つの違いがわからないんですが。
Re: (スコア:0)
書いてあるまんまだと思いますが。。。
例えば、極小値(くぼみ)が2か所(a,b(ただしab))ある曲面での最小値を見つける場合、
近似アルゴリズムだとa付近の値が解として得られる(b付近の値が解として得られることは無い)。
ヒューリスティクスやアニーリングだとb付近の値が解として得られる場合がある。
Re: (スコア:0)
それって単に局所解ですよね。
ヒューリスティクスや量子アニーリングって局所解に(も)近似しちゃうの?
Re:誰か教えてください (スコア:0)
パラメータ次第ですね
谷(局所解)から別の谷に行くためには、ポテンシャルの山を越える必要があるので、それを越えられるようなパラメータ(打切り条件)が必要です
ただこの条件が緩すぎると収束せずにずっと探索して効率悪くなる
# 遺伝的アルゴリズムだと突然変異でこれを越えるんだけど、その発想は面白いなと思ったし、自然界すげーとも思った
なお量子ゲートを使った量子コンピュータだと、量子ビットが十分なら最適解が求まるはず