「大人の教養・知識・気付き」を伸ばすブログ

※今月(8月)は一部コンテンツを隔週更新にします(夏休みです…)。 一流の大人(ビジネスマン、政治家、リーダー…)として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。

MENU

Pythonで学ぶアルゴリズム(15/18)

 アルゴリズムを学ぶのにPythonの学習も兼ねて

を参照していく。

8. 問題の難しさ

 さまざまなアルゴリズムの計算量を改めて検討する*1

8.1 計算に掛かるコスト

8.1.1 計算時間の変化
1. 定数時間 \mathcal{O}(1) 要素の数に寄らずに一定時間しかかからない計算量
2. 対数時間 \mathcal{O}(\log n) ソートされた配列内の目的値を二分探索で探索する際などで掛かる計算量
3. 線形時間 \mathcal{O}(n) 素数の定数倍のステップ数を必要とする計算量
4. 線形対数時間 \mathcal{O}(n\log n) 線形時間と対数時間の積だけ掛かる計算量
5. 多項式時間 \mathcal{O}(n^k) 素数多項式で表される計算量。


8.1.4 メモリに関するコスト

 アルゴリズムの実行に際して必要となるメモリを空間複雑性という。一般に計算の複雑性を考える場合、時間と空間(メモリ)の双方を考える必要がある。
 \mathrm{Python}のリストはそのサイズを任意に変更できるため、\mathrm{C}言語よりはメモリを気にしなくともよいが、大規模なプログラムや速度を求められる場合にはこうした要素を考慮しなければならない。

8.2 難しさの分類

8.2.1 コンピュータのモデル

 プログラムを実行して問題を解く現代のコンピュータはチューリング機械(\mathrm{Turing\ machine})と呼ばれる数学的なモデルを基盤としている。ここでは詳述しないが、プログラムを実行し、分岐がある場合はいずれか1つの道筋を選んで計算を続ける機械を指す。
 多項式時間で解けるアルゴリズムを持たない問題を難しい問題(\mathrm{intractable\ problem})と呼ぶことにする。チューリング機械を拡張して計算途中にある分岐を1回の実行ですべて計算できる理論的なものを非決定的チューリング機械と呼ぶ*2

8.2.2 PとNP

 配列のソートやグラフの最短距離を求める問題は、多項式時間で解くことができる。こうした多項式時間で解ける問題をクラス\boldsymbol{\mathrm{P}}というこれに対して普通のコンピュータでは多項式時間で解けないものの、非決定的チューリング機械では多項式時間で解ける問題をクラス\boldsymbol{\mathrm{NP}}という。
 問題がクラス\mathrm{NP}であるためには判定問題である必要がある。すなわちその問いに対する解答が\mathrm{Yes}または\mathrm{No}であるようなものでなければならない。

8.2.3 3SAT

 クラス\mathrm{NP}である例として\mathrm{3SAT}を考える。\mathrm{True}または\mathrm{False}を保持する変数がいくつかあるとする。またそれらの否定を考え、これらをまとめてリテラルと呼ぶこととする。リテラルを複数並べて論理和でつなげたものを節と呼ぶ。この節をいくつか並べて論理積で繋げたもののうち、全体で\mathrm{True}となる変数の組み合わせが存在するかを判定する問題を\mathrm{3SAT}という。

############
### kSAT ###
############


import random
random.seed(8)

class kSAT:
    
    @classmethod
    def generate(cls, k, var_num, clause_num):
        """変数の数(var_num)と節の数(clause_num)からkSAT問題を作る"""
        ksat = cls()
        var_list = list(range(var_num))
        
        # 問題の本体を格納するための変数
        res = []
        
        while len(res) < clause_num:
            clause = []
            
            # 高々k個の変数が含まれる
            clause_size = random.randint(1, k)
            
            for i in random.sample(var_list, clause_size):
                # 1ならばnotで変数を否定する
                prefix = random.choice((0, 1))
                clause.append((prefix, i))
            # 同一の節を判定できるように変数の添え字でソート
            clause.sort(key = lambda x: x[1])
            
            if clause not in res: res.append(clause)
        # kSATのインスタンスに格納
        ksat.body = res
        return ksat
    
    def test(self, var_list):
        """受け取ったvar_listのTrue, Falseを用いて論理式を評価する"""
        res = []
        for clause in self.body:
            clause_data =[not var_list[i] if p else var_list[i] for p,i in clause]
            
            res.append(any(clause_data))
        return all(res)
    
    def __str__(self):
        res = []
        for clause in self.body:
            clause_str = [f'¬x{i}' if p else f'x{i}' for p,i in clause]
            res.append('(' + '∧'.join(clause_str) + ')')
        return '∧'.join(res)

#####
ksat = kSAT.generate(3, 4, 3)

print(ksat)
#####
while True:
    cand = random.choices([True, False], k=4)
    
    if ksat.test(cand):
        print(cand)
        break

8.3 NP完全とNP困難

 クラス\mathrm{NP}が本当に多項式時間で解けないのかという問題を\mathrm{P}=\mathrm{NP}問題という。未だ未解決である。
 他方であるクラス\mathrm{NP}な問題X多項式時間しかかからない手間で問題Yに変形できるとき、XY多項式時間還元可能という。クラス\mathrm{NP}に属するあらゆる問題の変換先になり得るような問題があることが分かりつつあり、こうした問題を\mathrm{NP}困難と呼ぶ。
 \mathrm{NP}困難かつクラス\mathrm{NP}に属する問題を\mathrm{NP}完全という。

*1:実際のPC内への書き出しの時間などマシンに依存するものは考慮しない。

*2:これへの対比として前述したチューリング機械を決定的チューリング機械と呼ぶこともある。

プライバシーポリシー お問い合わせ