アカウント名:
パスワード:
・近似比保証のある解(近似解)が得られる場合(いわゆる近似アルゴリズム)・目的関数値の理論保証はないが,実用上それなりに良い解が得られる場合(ヒューリスティクス,D-waveなどの量子アニーリングはココ)
この二つの違いがわからないんですが。
答え知ってて聞いてるんでしょ
だいたいあってることが保証されてるのが前者。(あってると言った)だいたいあってるつもりなのが後者。(あってるとは言ってない)
書いてあるまんまだと思いますが。。。例えば、極小値(くぼみ)が2か所(a,b(ただしab))ある曲面での最小値を見つける場合、近似アルゴリズムだとa付近の値が解として得られる(b付近の値が解として得られることは無い)。ヒューリスティクスやアニーリングだとb付近の値が解として得られる場合がある。
ただしab→ただしa<b
それって単に局所解ですよね。ヒューリスティクスや量子アニーリングって局所解に(も)近似しちゃうの?
パラメータ次第ですね谷(局所解)から別の谷に行くためには、ポテンシャルの山を越える必要があるので、それを越えられるようなパラメータ(打切り条件)が必要ですただこの条件が緩すぎると収束せずにずっと探索して効率悪くなる# 遺伝的アルゴリズムだと突然変異でこれを越えるんだけど、その発想は面白いなと思ったし、自然界すげーとも思った
なお量子ゲートを使った量子コンピュータだと、量子ビットが十分なら最適解が求まるはず
違います。その理解だと、「近似アルゴリズム」で最適解まで到達できちゃいませんか? aのくぼみの近くに居るならそこから単純に坂を下ればaの底に到達できるので。くぼみが無数にある場合でも、a<b<c<d<…だったら、こっちの方が小さい、を繰り返してaに到達できそうですし。
a、b、c、…と無数にくぼみがあって究極のくぼみがzだった時に、zの定数倍以内に収まるくぼみが必ず選ばれる、というような保証があるものが近似アルゴリズムです。他にも設定した以上の確率で必ずzに到達できる近似アルゴリズム、とか、保証される内容は色々です。
要は、
解が有理数であればね。
「求まった解はおそらく最適ではないけど、最適解より高々x%しか悪くはないことは証明できる」ってやるのが近似解。xは好きに設定できて、小さくするとより大幅に計算に時間が掛かるようになる。もちろん、x=0にすると計算量が指数オーダーを超えるか、アルゴリズムの制約上そうはできないか。
保証がない方はそのまま。どんな値が求まってるんだか分からない。近似比保証のあるアルゴリズムとか他の方法とかで求めた結果と比べてみた範囲ではそんなに悪くは無さそう、というやり方。運が悪いととんでもなく悪い解になっているかも知れないけど、その分、計算は無茶苦茶速い。
これが学会で皆が戦慄するという、「わたくしこの分野は専門外なのですが」か。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
ハッカーとクラッカーの違い。大してないと思います -- あるアレゲ
誰か教えてください (スコア:0)
・近似比保証のある解(近似解)が得られる場合(いわゆる近似アルゴリズム)
・目的関数値の理論保証はないが,実用上それなりに良い解が得られる場合(ヒューリスティクス,D-waveなどの量子アニーリングはココ)
この二つの違いがわからないんですが。
Re: (スコア:0)
答え知ってて聞いてるんでしょ
Re: (スコア:0)
だいたいあってることが保証されてるのが前者。(あってると言った)
だいたいあってるつもりなのが後者。(あってるとは言ってない)
Re: (スコア:0)
書いてあるまんまだと思いますが。。。
例えば、極小値(くぼみ)が2か所(a,b(ただしab))ある曲面での最小値を見つける場合、
近似アルゴリズムだとa付近の値が解として得られる(b付近の値が解として得られることは無い)。
ヒューリスティクスやアニーリングだとb付近の値が解として得られる場合がある。
Re: (スコア:0)
ただしab→ただしa<b
Re: (スコア:0)
それって単に局所解ですよね。
ヒューリスティクスや量子アニーリングって局所解に(も)近似しちゃうの?
Re: (スコア:0)
パラメータ次第ですね
谷(局所解)から別の谷に行くためには、ポテンシャルの山を越える必要があるので、それを越えられるようなパラメータ(打切り条件)が必要です
ただこの条件が緩すぎると収束せずにずっと探索して効率悪くなる
# 遺伝的アルゴリズムだと突然変異でこれを越えるんだけど、その発想は面白いなと思ったし、自然界すげーとも思った
なお量子ゲートを使った量子コンピュータだと、量子ビットが十分なら最適解が求まるはず
Re: (スコア:0)
違います。その理解だと、「近似アルゴリズム」で最適解まで到達できちゃいませんか? aのくぼみの近くに居るならそこから単純に坂を下ればaの底に到達できるので。くぼみが無数にある場合でも、a<b<c<d<…だったら、こっちの方が小さい、を繰り返してaに到達できそうですし。
a、b、c、…と無数にくぼみがあって究極のくぼみがzだった時に、zの定数倍以内に収まるくぼみが必ず選ばれる、というような保証があるものが近似アルゴリズムです。他にも設定した以上の確率で必ずzに到達できる近似アルゴリズム、とか、保証される内容は色々です。
要は、
Re: (スコア:0)
解が有理数であればね。
Re: (スコア:0)
「求まった解はおそらく最適ではないけど、最適解より高々x%しか悪くはないことは証明できる」ってやるのが近似解。xは好きに設定できて、小さくするとより大幅に計算に時間が掛かるようになる。もちろん、x=0にすると計算量が指数オーダーを超えるか、アルゴリズムの制約上そうはできないか。
保証がない方はそのまま。どんな値が求まってるんだか分からない。近似比保証のあるアルゴリズムとか他の方法とかで求めた結果と比べてみた範囲ではそんなに悪くは無さそう、というやり方。運が悪いととんでもなく悪い解になっているかも知れないけど、その分、計算は無茶苦茶速い。
Re: (スコア:0)
これが学会で皆が戦慄するという、
「わたくしこの分野は専門外なのですが」か。