アカウント名:
パスワード:
・近似比保証のある解(近似解)が得られる場合(いわゆる近似アルゴリズム)・目的関数値の理論保証はないが,実用上それなりに良い解が得られる場合(ヒューリスティクス,D-waveなどの量子アニーリングはココ)
この二つの違いがわからないんですが。
「求まった解はおそらく最適ではないけど、最適解より高々x%しか悪くはないことは証明できる」ってやるのが近似解。xは好きに設定できて、小さくするとより大幅に計算に時間が掛かるようになる。もちろん、x=0にすると計算量が指数オーダーを超えるか、アルゴリズムの制約上そうはできないか。
保証がない方はそのまま。どんな値が求まってるんだか分からない。近似比保証のあるアルゴリズムとか他の方法とかで求めた結果と比べてみた範囲ではそんなに悪くは無さそう、というやり方。運が悪いととんでもなく悪い解になっているかも知れないけど、その分、計算は無茶苦茶速い。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
最初のバージョンは常に打ち捨てられる。
誰か教えてください (スコア:0)
・近似比保証のある解(近似解)が得られる場合(いわゆる近似アルゴリズム)
・目的関数値の理論保証はないが,実用上それなりに良い解が得られる場合(ヒューリスティクス,D-waveなどの量子アニーリングはココ)
この二つの違いがわからないんですが。
Re:誰か教えてください (スコア:0)
「求まった解はおそらく最適ではないけど、最適解より高々x%しか悪くはないことは証明できる」ってやるのが近似解。xは好きに設定できて、小さくするとより大幅に計算に時間が掛かるようになる。もちろん、x=0にすると計算量が指数オーダーを超えるか、アルゴリズムの制約上そうはできないか。
保証がない方はそのまま。どんな値が求まってるんだか分からない。近似比保証のあるアルゴリズムとか他の方法とかで求めた結果と比べてみた範囲ではそんなに悪くは無さそう、というやり方。運が悪いととんでもなく悪い解になっているかも知れないけど、その分、計算は無茶苦茶速い。