パスワードを忘れた? アカウント作成
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

組合せ最適化と量子コンピュータに関する怪しい言説に研究者が間違いを指摘」記事へのコメント

  • ・近似比保証のある解(近似解)が得られる場合(いわゆる近似アルゴリズム)
    ・目的関数値の理論保証はないが,実用上それなりに良い解が得られる場合(ヒューリスティクス,D-waveなどの量子アニーリングはココ)

    この二つの違いがわからないんですが。

    • by Anonymous Coward

      書いてあるまんまだと思いますが。。。
      例えば、極小値(くぼみ)が2か所(a,b(ただしab))ある曲面での最小値を見つける場合、
      近似アルゴリズムだとa付近の値が解として得られる(b付近の値が解として得られることは無い)。
      ヒューリスティクスやアニーリングだとb付近の値が解として得られる場合がある。

      • by Anonymous Coward

        それって単に局所解ですよね。
        ヒューリスティクスや量子アニーリングって局所解に(も)近似しちゃうの?

        • by Anonymous Coward on 2021年07月09日 15時15分 (#4067377)

          パラメータ次第ですね
          谷(局所解)から別の谷に行くためには、ポテンシャルの山を越える必要があるので、それを越えられるようなパラメータ(打切り条件)が必要です
          ただこの条件が緩すぎると収束せずにずっと探索して効率悪くなる
          # 遺伝的アルゴリズムだと突然変異でこれを越えるんだけど、その発想は面白いなと思ったし、自然界すげーとも思った

          なお量子ゲートを使った量子コンピュータだと、量子ビットが十分なら最適解が求まるはず

          親コメント

犯人は巨人ファンでA型で眼鏡をかけている -- あるハッカー

処理中...