什么是p問題、np問題和npc問題-在線瀏覽
2024-09-15 18:58本頁面
【正文】 你總得用階乘級(jí)的時(shí)間打印出結(jié)果來。那么，根據(jù)這個(gè)定義，我也能舉出一個(gè)不大可能會(huì)有多項(xiàng)式級(jí)算法的問題 來：Hamilton回路。這個(gè)問題現(xiàn)在還沒有找到多項(xiàng)式級(jí)的算法。下面 引入P類問題的概念：如果一個(gè)問題可以找到一個(gè)能在多項(xiàng)式的時(shí)間里解決它的算法，那么這個(gè)問題就屬于P問題。哪些問題是 P類問題呢？通常NOI和NOIP不會(huì)出不屬于P類問題的題目。道理很簡(jiǎn)單，一個(gè)用窮舉換來的非多項(xiàng)式級(jí)時(shí)間 的超時(shí)程序不會(huì)涵蓋任何有價(jià)值的算法。這個(gè)就有點(diǎn)難理解了，或者說容易理解錯(cuò)誤。NP問題是指可以在多項(xiàng)式的時(shí)間里驗(yàn)證一個(gè)解的問題。比方說，我RP很好，在程序中需要枚舉時(shí)，我可以一猜一個(gè)準(zhǔn)。它根據(jù)數(shù)據(jù)畫好了圖，但怎么也算不出來，于是來問我：你看怎么選條路走得最少？我說，我RP很好，肯定能隨便給你指條很短的路出來。那人按我指的這條把權(quán)值加起來一看，嘿，神了，路徑長(zhǎng)度98，比100小。別人會(huì)問他這 題怎么做出來的，他就可以說，因?yàn)槲艺业搅艘粋€(gè)比100 小的解。驗(yàn)證一個(gè)解只需要O(n)的時(shí)間復(fù)雜度，也就是說我可以花O(n)的時(shí)間把我猜的路徑的長(zhǎng)度加 出來。我猜到的方案總是最優(yōu)的，不滿足題意的方案也不會(huì)來騙我去選它。當(dāng)然有不是NP問題的問題，即你猜到了解但是沒用，因?yàn)槟悴荒茉诙囗?xiàng)式的時(shí)間里去驗(yàn)證它。很顯然，前面所說的Hamilton回路是NP問題，因?yàn)轵?yàn)證一條路是否恰好經(jīng)過了每一個(gè)頂點(diǎn)非常容易。這樣問題就沒法在多項(xiàng)式的時(shí)間里進(jìn)行驗(yàn)證了，因?yàn)槌悄阍囘^所有的路，否則你不敢斷定它“沒 有Hamilton回路”。我們不會(huì)指望一個(gè)連多項(xiàng)式地驗(yàn)證一個(gè) 解都不行的問題存在一個(gè)解決它的多項(xiàng)式級(jí)的算法。很顯然，所有的P類問題都是NP問題。關(guān)鍵是，人們想知道，是否所有的NP問題都是P類問題。如果把所有P類 問題歸為一個(gè)集合P中，把所有 NP問題劃進(jìn)另一個(gè)集合NP中，那么，顯然有P屬于NP。NP問題一直都是信息學(xué)的巔峰。在信息學(xué)研究中，這是一個(gè)耗費(fèi)了很多時(shí)間和精力也沒有解決的終極問題，好比物理學(xué)中的大統(tǒng)一和數(shù)學(xué)中的歌德巴赫猜想等。但是，一個(gè)總的趨勢(shì)、一個(gè)大方向是有的。人們?nèi)绱藞?jiān)信P≠NP是有原因的，就是在研究NP問題的過程中找出了一類非常特殊的NP問題叫做NP完全問題，也即所謂的 NPC問題。正是NPC問題的存在，使人們相信P≠NP。為了說明NPC問題，我們先引入一個(gè)概念——約化(Reducibility，有的資料上叫“歸約”)。《算法導(dǎo)論》上舉了這么一個(gè)例子。那么我們說，前者可以約化為后者，意即知道如何解一個(gè)一元二次方程那么一定能解出一 元一次方程。這個(gè)規(guī)則即是：兩個(gè)方程的對(duì)應(yīng)項(xiàng)系數(shù)不變，一元二次方程的二次項(xiàng)系數(shù)為0。同樣地，我們可以說，Hamilton回路可以約化為TSP問題(Travelling Salesman Problem，旅行商問題)：在Hamilton回路問題中，兩點(diǎn)相連即這兩點(diǎn)距離為0，兩點(diǎn)不直接相連則令其距離為1，于是問題轉(zhuǎn)化為在TSP問題 中，是否存在一條長(zhǎng)為0的路徑?！皢栴}A可約化為問題B”有一個(gè)重要的 直觀意義：B的時(shí)間復(fù)雜度高于或者等于A的時(shí)間復(fù)雜度。這很容易理解。正如解一元二次方程比解一
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1