p類演算法

1. 能夠被計算機解決的問題的特點是

1、分析問題。

用電腦來解決問題時，首先電腦要對問題進行定性、定量的分析，然後才能設計演算法。定性分析法是對問題進行「質」的方面的分析，確定問題的性質，定量分析法，是對要解決的問題的數量特徵、數量關系與數量變化進行分析的方法。

2、設計演算法。

演算法（Algorithm）是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。

不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。

3、編寫程序。

設計完演算法後，就要使用某種程序設計語言編寫程序代碼，並最終得到相應結果。編程的語言包括匯編語言、機器語言和高級語言。高級語言中最簡單、最常用的是Visual Basic語言和Pascal語言。

(1)p類演算法擴展閱讀：

人類解決問題：靠知識、見識、常識、經驗、直覺、甚至賭博；

計算機解決問題：靠知識庫、推理、推演、演繹、計算和預測以及概率分析。

人類會受外界因素和個人情感的干擾，導致同樣的條件不同的結果；計算機則不受干擾，滿足某個或某些條件，就會執行預先設定的命令。

利用計算機程序解決問題的基本過程：

了解利用計算機解決問題的基本過程。

了解問題分析與演算法設計之間的關系。

2. 什麼是P和NP

首先說明一下問題的復雜性和演算法的復雜性的區別，下面只考慮時間復雜性。演算法的復雜性是指解決問題的一個具體的演算法的執行時間，這是演算法的性質；問題的復雜性是指這個問題本身的復雜程度，是問題的性質。比如對於排序問題，如果我們只能通過元素間的相互比較來確定元素間的相互位置，而沒有其他的附加可用信息，則排序問題的復雜性是O(nlgn)，但是排序演算法有很多，冒泡法是O(n^2)，快速排序平均情況下是O(nlgn)等等，排序問題的復雜性是指在所有的解決該問題的演算法中最好演算法的復雜性。問題的復雜性不可能通過枚舉各種可能演算法來得到，一般都是預先估計一個值，然後從理論上證明。 為了研究問題的復雜性，我們必須將問題抽象，為了簡化問題，我們只考慮一類簡單的問題，判定性問題，即提出一個問題，只需要回答yes或者no的問題。任何一般的最優化問題都可以轉化為一系列判定性問題，比如求圖中從A到B的最短路徑，可以轉化成：從A到B是否有長度為1的路徑？從A到B是否有長度為2的路徑？。。。從A到B是否有長度為k的路徑？如果問到了k的時候回答了yes，則停止發問，我們可以說從A到B的最短路徑就是k。如果一個判定性問題的復雜度是該問題的一個實例的規模n的多項式函數，則我們說這種可以在多項式時間內解決的判定性問題屬於P類問題。P類問題就是所有復雜度為多項式時間的問題的集合。然而有些問題很難找到多項式時間的演算法（或許根本不存在），比如找出無向圖中的哈米爾頓迴路問題，但是我們發現如果給了我們該問題的一個答案，我們可以在多項式時間內判斷這個答案是否正確。比如說對於哈米爾頓迴路問題，給一個任意的迴路，我們很容易判斷他是否是哈米爾頓迴路（只要看是不是所有的頂點都在迴路中就可以了）。這種可以在多項式時間內驗證一個解是否正確的問題稱為NP問題。顯然，所有的P類問題都是屬於NP問題的，但是現在的問題是，P是否等於NP?這個問題至今還未解決。注意，NP問題不一定都是難解的問題，比如簡單的數組排序問題是P類問題，但是P屬於NP，所以也是NP問題，你能說他很難解么？剛才說了，現在還不知道是否有P=NP或者P<>NP，但是後來人們發現還有一系列的特殊NP問題，這類問題的特殊性質使得很多人相信P<>NP，只不過現在還無法證明。這類特殊的NP問題就是NP完全問題（NPC問題，C代表complete）。NPC問題存在著一個令人驚訝的性質，即如果一個NPC問題存在多項式時間的演算法，則所有的NP問題都可以在多項式時間內求解，即P=NP成立！！這是因為，每一個NPC問題可以在多項式時間內轉化成任何一個NP問題。比如前面說的哈米爾頓迴路問題就是一個NPC問題。NPC問題的歷史並不久，cook在1971年找到了第一個NPC問題，此後人們又陸續發現很多NPC問題，現在可能已經有3000多個了。所以，我們一般認為NPC問題是難解的問題，因為他不太可能存在一個多項式時間的演算法（如果存在則所有的NP問題都存在多項式時間演算法，這太不可思議了，但是也不是不可能）。類似哈米爾頓迴路/路徑問題，貨郎擔問題，集團問題，最小邊覆蓋問題（注意和路徑覆蓋的區別），等等很多問題都是NPC問題，所以都是難解的問題。

3. 舉例說明演算法領域的P類問題和NP類問題。為什麼說現代計算機只能解決確

P:多項式時間內可以解決，太多了，如排序問題
NP:多項式時間內可以驗證，如大數分解問題，隨便給你一個非常大的數(該數由兩個非常大的素數相乘得來)，你沒法很快將其分解為兩個素數的乘積，但若是把這兩個素數告訴你，你可以很快的驗證它是由這兩個素數相乘得來（即多項式時間可驗證）
上述兩個概念一開始是用來描述判定問題的，後來被拓展到其他問題（如優化問題）上

現代計算機一就是馮洛伊曼結構，哪怕改成哈佛結構，也依舊只是一台圖靈機，其表述能力無法超過圖靈機范疇，所以只能解決確定性圖靈機問題(這個名詞我沒聽過，所以只能猜測其表示的意思)

4. 什麼是P問題NP問題NPC問題三者關系如何

1、P問題
P是一個判定問題類,這些問題可以用一個確定性演算法在多項式時間內判定或解出。如果一個判定性問題的復雜度是該問題的一個實例的規模n的多項式函數，則我們說這種可以在多項式時間內解決的判定性問題屬於P類問題。P類問題就是所有復雜度為多項式時間的問題的集合。

NP是一個判定問題類,這些問題可以用一個確定演算法在多項式時間內檢查或驗證出它們的解;P事實上很直觀,我們通常在編程中求解的問題大多都是P類問題.比如說排序,找最短路徑等.
2、NP問題
然而有些問題很難找到多項式時間的演算法（或許根本不存在），比如找出無向圖中的哈米爾頓迴路問題，但是我們發現如果給了我們該問題的一個答案，我們可以在多項式時間內判斷這個答案是否正確。比如說對於哈米爾頓迴路問題，給一個任意的迴路，我們很容易判斷他是否是哈米爾頓迴路（只要看是不是所有的頂點都在迴路中就可以了）。這種可以在多項式時間內驗證一個解是否正確的問題稱為NP問題。顯然，所有的P類問題都是屬於NP問題的，但是現在的問題是，P是否等於NP?這個問題至今還未解決。
NP這個類事實上也很有趣,它並不要求給出一個演算法來求解問題本身,而只是要求給出一個確定性演算法在多項式時間內驗證它的解.

3、NP完全問題
此外請注意，NP問題不一定都是難解的問題，比如，簡單的數組排序問題是P類問題，但是P屬於NP，所以也是NP問題，你能說他很難解么？剛才說了，現在還不知道是否有P=NP或者P<>NP，但是後來人們發現還有一系列的特殊NP問題，這類問題的特殊性質使得很多人相信P<>NP，只不過現在還無法證明。這類特殊的NP問題就是NP完全問題（NPC問題，C代表complete）。
NP完全問題是求NP中判定問題的一個子類.NPC問題存在著一個令人驚訝的性質，即如果一個NPC問題存在多項式時間的演算法，則所有的NP問題都可以在多項式時間內求解，即P=NP成立！！這是因為，每一個NPC問題可以在多項式時間內轉化成任何一個NP問題。比如前面說的哈米爾頓迴路問題就是一個NPC問題。NPC問題的歷史並不久，cook在1971年找到了第一個NPC問題，此後人們又陸續發現很多NPC問題，現在可能已經有3000多個了。所以，我們一般認為NPC問題是難解的問題，因為他不太可能存在一個多項式時間的演算法（如果存在則所有的NP問題都存在多項式時間演算法，這太不可思議了，但是也不是不可能）。類似哈米爾頓迴路/路徑問題，貨郎擔問題，集團問題，最小邊覆蓋問題（注意和路徑覆蓋的區別），等等很多問題都是NPC問題，所以都是難解的問題。

5. 什麼是G-p演算法

遺傳編程（GP）屬於進化計算（Evolutionary Computation，EC）模型的一種。EC是一種借鑒自然界進化機制而產生的並行隨機搜索演算法。進化演算法的基本原理是選擇和改變，它區別於其他搜索方法有兩個顯著特徵：首先這些演算法都是基於種群（population）的；其次在種群中個體（indvial）之間存在競爭。 為搜索特定的（感興趣的）查詢需要一種工具，這種工具可智能生成一組查詢並以它們是否能導出與用戶給定的同樣的對象集來進行評價。GP演算法對這一類問題是很實用的。
1 函數集與端點集
一般GP中可生成的程序集是使用者定義的函數集和端點集。表1給出了相應的函數集和端點集，其中函數集由1.3中定義的查詢運算元、邏輯運算運算元以及比較運算元所組成。
函數集 {SEL，REL，G-REL，RES}，{UNI，INT，DIF}，{AND，OR，NOT}， {>，>=，=，<，<=} 端點集類集，屬性集，值集
表1 函數集和端點集
在我們的應用中還有一些具有不同句法的查詢運算元。每個運算元具有不同的句法且假定的資料庫是面向對象的。因此，它具有為創建個體而使用的特別的函數集（或運算元集）和端點集。從而，構成種群的所有個體的創建必然受到每個運算元的約束[3]。約束可以是運算元的句法和查詢的類型，或者是為創建查詢選擇適當屬性值的領域知識。比較運算元和邏輯運算元只使用於查詢的謂詞。當比較符號操作數時，僅使用'='。
端點集由CLASS-SET、SLOT-SET和VALUE-SET組成。CLASS-SET由1.2中定義的類名組成，SLOT-SET由每個類的所有屬性構成，VALUE-SET由數值和符號值所構成（它們均為屬性值）。數值由整型或實型數構成，其數值范圍由所用資料庫模式定義。符號值由字元串表示的符號屬性值構成。
[編輯本段]
2 創建初始種群
為了創建一個個體（查詢），首先必須確定特定查詢所返回的對象類型。結果類型被選擇後，從所選類型返回例子的運算元集中隨機地選擇一個運算元，這個過程對查詢的每個參數遞歸地進行。最初，那些句法正確的預定義數量的查詢被隨機地產生，形成初始種群。
[編輯本段]
3 選擇屬性值
由於可選擇范圍大，要從某個查詢的值集中選擇一個屬性值（數值或符號常數）是相當困難的。對於一個范圍為[1，10000]的整數集，隨機選到一個特定整數的概率僅為1/10000。而對於符號常數，則需要很強的背景知識。因此，我們僅就發生在資料庫里的范圍選擇屬性值。
[編輯本段]
4 繁殖新一代種群
每個個體用預定義的適應函數來進行評價。較適應的查詢有較高的概率被選來繁殖新種群，這個過程用三個遺傳運算元：選擇、雜交和變異來完成。為了產生下一代，選擇運算元根據個體的適應值來選擇個體。我們用一個樹來表示一個查詢，雜交運算元用交換兩個父輩的子樹來創建兩個後代。變異運算元用一個新的子樹來代替一個父輩的子樹，從而產生一個新的後代。選擇-雜交-變異循環反復地進行直到終止標准被滿足。
[編輯本段]
5 評價（適應函數測量）
我們使用如下的適應函數f來評價種群中的個體查詢i ：
f ( ni , hi ) = T - ( hi * hi ) / ni ,
其中：ni > 0 ， T ≥ hi ， 且 i = 1 ，2 ，… ，種群的大小（T是被確定的對象集的勢，hi是一個個體查詢i 被選中的次數，ni是查詢 i 結果集的勢）。
上述適應函數依賴於hi和ni ，如果一個查詢沒有被選中（hi=0），則函數的值為T，這是最差的一個適應值。另一方面，如果查詢結果能夠很好地匹配提交給系統的對象集，那麼它的適應值為0（在這種情況下hi = ni = T ）。如果種群中出現個體適應值遠遠超過種群平均適應值，該個體很快就會在群體中佔有絕對的比例，從而出現過早收斂的現象。另一方面，在搜索過程的後期，群體的平均適應值可能會接近群體的最優適應值，從而導致搜索目標難以得到改善，出現停滯現象[4]。為了防止上述情況的發生，我們將對一個個體查詢的例子個數 ni 作為分母。

6. P類問題和NP類問題的定義和區別

如果一個問題可以找到一個能在多項式的時間里解決它的演算法，那麼這個問題就屬於P問題。P是英文單詞多項式的第一個字母。通常NOI和NOIP不會出不屬於P類問題的題目。我們常見到的一些信息奧賽的題目都是P問題。道理很簡單，一個用窮舉換來的非多項式級時間的超時程序不會涵蓋任何有價值的演算法。
NP問題不是非P類問題。NP問題是指可以在多項式的時間里驗證一個解的問題。NP問題的另一個定義是，可以在多項式的時間里猜出一個解的問題。
所有的P類問題都是NP問題。也就是說，能多項式地解決一個問題，必然能多項式地驗證一個問題的解——既然正解都出來了，驗證任意給定的解也只需要比較一下就可以了。關鍵是，人們想知道，是否所有的NP問題都是P類問題。我們可以再用集合的觀點來說明。如果把所有P類問題歸為一個集合P中，把所有 NP問題劃進另一個集合NP中，那麼，顯然有P屬於NP。

7. 世界七大數學難題之首是什麼

NP 完全問題是世界七大數學難題之首。NP完全問題，是世界七大數學難題之一，排在百萬美元大獎的首位。

NP的英文全稱是Non-deterministic Polynomial的問題，即多項式復雜程度的非確定性問題。簡單的寫法是 NP=P？，問題就在這個問號上，到底是NP等於P，還是NP不等於P。

P類問題：所有可以在多項式時間內求解的判定問題構成P類問題。判定問題：判斷是否有一種能夠解決某一類問題的能行演算法的研究課題。

NP類問題：所有的非確定性多項式時間可解的判定問題構成NP類問題。

NP完全問題介紹：

有些計算問題是確定性的，比如加減乘除之類，你只要按照公式推導，按部就班一步步來，就可以得到結果。但是，有些問題是無法按部就班直接地計算出來。比如，找大質數的問題，這種問題的答案，是無法直接計算得到的，只能通過間接的「猜算」來得到結果。

人們發現，所有的完全多項式非確定性問題，都可以轉換為一類叫做滿足性問題的邏輯運算問題。既然這類問題的所有可能答案，都可以在多項式時間內計算，人們於是就猜想，是否這類問題存在一個確定性演算法，可以在多項式時間內直接算出或是搜尋出正確的答案呢？這就是著名的NP=P？的猜想。

8. 什麼是p類問題什麼是np類問題

P對NP問題是克雷數學研究所高額懸賞的七個千禧年難題之一，同時也是計算機科學領域的最大難題，關繫到計算機完成一項任務的速度到底有多快。P對NP問題是Steve Cook於1971年首次提出。
「P/NP問題」，這里的P指多項式時間(Polynomial)，一個復雜問題如果能在多項式時間內解決，那麼它便被稱為P問題，這意味著計算機可以在有限時間內完成計算;
NP指非確定性多項式時間(nondeterministic polynomial)，一個復雜問題不能確定在多項式時間內解決，假如NP問題能找到演算法使其在多項式時間內解決，也就是證得了P=NP。
比NP問題更難的則是NP完全和NP-hard，如圍棋便是一個NP-hard問題。2010年8月7日，來自惠普實驗室的科學家Vinay Deolalikar聲稱已經解決了「P/NP問題」，並公開了證明文件。