dポイントプレゼントキャンペーン実施中!

PNP問題というミレニアム問題があります。世の中にはNP問題が溢れているということですが、4色問題、即ち、「与えられた地図上の隣接する国を異なる色に塗り分けよ、ただし4色以内で」という問題というか課題はどうなのでしょうか?この課題を実行するのにP時間=多項式時間(コンピュータでやるとするならステップ数となりましょうが)で済むのか、それ以上かかるのか?

A 回答 (3件)

ちょいと調べてみたけど「証明」が正しければ O(n^2) 時間 (n は「国」の数) でいいみたい.



「3色で塗れるグラフを 3色で塗ってみろ」は NP 完全だったかな?
    • good
    • 0
この回答へのお礼

ありがとうございます。

お礼日時:2022/11/03 11:43

考え直してみました。


地図の四色塗り分けを見つけるときに、時間がかかるのは、
色を塗り替える時間よりも、不可避集合の中のどのパターンが
地図のどこにあてはまるのかを検索する作業かと思います。
それにどの程度の時間がかかるのかは、地図やパターンを保管する
データ構造とか検索アルゴリズムとかに依存するでしょうが、
ナイーブに片っ端から突合していったとすると、地図が n 国
不可避集合中の最大のパターンが p 国からなるとして
nCp に比例する時間がかかってしまいます。
No.1 に書いた評価よりはかなり多い計算量になりますが、
まあそれでも多項式時間であることにはかわりありません。
    • good
    • 0
この回答へのお礼

ありがとうございます。

お礼日時:2022/11/01 12:18

四色問題自体は、既に証明が完成しているので有限時間です。


数学的帰納法を含むけれど、帰納法というのは
実際に帰納を行わなくても帰納できることが判る
という論法ですからね。証明の長さは国数に依存しません。
定数時間なので多項式時間に含まれます。

証明ではなくて、与えられた n 国地図の四色塗り分けを
見つける時間のことを言っているのだとしても、多項式時間です。
アッペル・ハーケンのアルゴリズムは、次の国を塗るために
既に塗った国を塗り変える場合がありますが、
塗った所を無かったことにしてやり直すわけではなく
塗り替えが済んだら予定通り次の国が塗れるので、
バックトラックは生じません。
最悪見積もりで、一国塗る度にほぼ毎回、それまで塗った国を
ほぼ全て塗り替えるとしても、色を塗る回数は ∑[k=1..n]k
で見積もることができ、アルゴリズムは多項式時間(二次式)です。
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!