巡回セールスマン問題: mos blog

漸近的計算量（ぜんきんてき・けいさんりょう）

O記法と呼ぶ。Orderの「O」

例：F(n)=n^2+n → O(n^2)

O記法は計算量の関数を定数や係数を除外して、最も増加率の大きい変数だけで表したもの。

O(log2N) < O(n) < O(n・log2N) < O(n^C) < O(C^n) < O(n!)　　ｎは入力サイズ、Cは定数

　　　　　　　　　多項式時間アルゴリズム← | →指数関数時間アルゴリズム

べき乗は多重ループの処理回数を表し、log2Nは２分割の処理回数を表す。 多項式時間アルゴリズムは実用的だが、指数関数時間アルゴリズムは実用的でない。

アルゴリズムとは問題を解く手順である。

アルゴリズムの計算量は、問題の複雑性を示す尺度である。

計算量クラス：　計算量理論において、計算量の大きさから問題の複雑さを分類したもの

「クラスP」　・・・決められた手順通りに処理を進めれば解ける問題の集合。これに属する問題を「P問題」という。

「クラスNP」・・・処理の手順に膨大な選択肢があり、その中から１つの手順を選んで、運がよければ解けるというような問題の集合。これに属する問題を「NP問題」という。特に簡単には解けないものを「NP完全問題」という。

※「P」はPolynomial（多項式）　「NP」はNon-deterministic Polynomial

「NP完全問題」の例：

　「巡回セールスマン問題」、「ナップザック問題」、「ハミルトン閉路問題」、「箱詰め問題」、「彩色数問題」、「論理式の充足可能性問題」

「巡回セールスマン問題」は、セールスマンが複数の訪問先を巡回する場合に、最短距離で巡回できる「順序」を導き出す問題である。計算量は、O(n!)

「決定性アルゴリズム」 　・・・P問題を解くアルゴリズム　→プログラミングで使うもの

「意思決定アルゴリズム」・・・NP問題を解くアルゴリズム