## NP闂�棰樺強鍏舵眰瑙ｆ敾鐣�
### 浠�涔堟槸NP闂�棰橈紵
鍦ㄨ�＄畻鏈虹�戝�︿腑锛孨P锛圢ondeterministic Polynomial time锛夐棶棰樻槸涓�绫婚噸瑕佺殑澶嶆潅鎬ч棶棰樸�傜畝鍗曟潵璇达紝NP闂�棰樿兘澶熷湪澶氶」寮忔椂闂村唴楠岃瘉缁欏畾瑙ｇ殑姝ｇ‘鎬с�傛崲鍙ヨ瘽璇达紝灏界�℃垜浠�鍙�鑳芥棤娉曢珮鏁堝湴鎵惧埌瑙ｅ喅鏂规�堬紝浣嗗�傛灉缁欏畾涓�涓�鍊欓�夎В锛屾垜浠�鍙�浠ュ揩閫熼獙璇佽繖涓�瑙ｆ槸鍚︽�ｇ‘銆�
甯歌�佺殑NP闂�棰樺寘鎷�鏃呰�屽晢闂�棰橈紙TSP锛夈�佽儗鍖呴棶棰樸�佸浘鐨勫搱瀵嗛】鍥炶矾闂�棰樼瓑銆傚叾涓�锛孴SP闂�棰樼殑鐩�鏍囨槸鎵惧嚭涓�鏉℃渶鐭�鐨勮矾寰勶紝浣垮緱鏃呰�岃�呰兘澶熻�块棶姣忎釜鍩庡競涓�娆″苟杩斿洖璧风偣銆�
### NP瀹屽叏涓嶯P鍥伴毦
鍦∟P闂�棰樹腑锛屾湁涓�绫荤壒鍒�閲嶈�佺殑闂�棰樼О涓篘P瀹屽叏闂�棰橈紙NP-Complete锛夛紝瀹冧滑涓嶄粎鏄疦P闂�棰橈紝鍚屾椂涔熷叿鏈変互涓嬬壒寰侊細浠讳綍涓�涓狽P闂�棰橀兘鍙�浠ラ�氳繃澶氶」寮忔椂闂村唴鐨勫綊绾﹁浆鍖栦负杩欎釜闂�棰樸�傚�傛灉涓�涓狽P瀹屽叏闂�棰樿兘澶熷湪澶氶」寮忔椂闂村唴瑙ｅ喅锛岄偅涔堟墍鏈夌殑NP闂�棰樹篃鑳藉�熷湪澶氶」寮忔椂闂村唴瑙ｅ喅銆�
鍦ㄨ繖绫婚棶棰樹腑锛屾槸鍚﹀瓨鍦ㄥ�氶」寮忔椂闂寸畻娉曚粛鐒舵槸璁＄畻鏈虹�戝�︿腑鐨勪竴涓�閲嶈�佹湭瑙ｉ棶棰橈紝鍗砅 vs NP闂�棰樸��
### NP闂�棰樼殑姹傝В绛栫暐
铏界劧NP闂�棰樻病鏈夊凡鐭ョ殑澶氶」寮忔椂闂寸畻娉曪紝浣嗘湁澶氱�嶇瓥鐣ュ彲浠ユ湁鏁堝湴澶勭悊杩欎簺闂�棰樸�備互涓嬫槸涓�浜涘父鐢ㄧ殑姹傝В鏂规硶锛�
#### 1. 绌蜂妇鎼滅储
绌蜂妇鎼滅储鏄�鏈�鍩烘湰鐨勬柟娉曚箣涓�锛岄�傜敤浜庡皬瑙勬ā闂�棰樸�傚畠閫氳繃灏濊瘯鎵�鏈夊彲鑳界殑瑙ｆ潵鎵惧埌涓�涓�鏈�浼樿В銆傝櫧鐒惰繖绉嶆柟娉曢�氬父闈炲父鑰楁椂锛屼絾瀹冨湪鏌愪簺鎯呭喌涓嬭兘澶熶繚璇佹壘鍒版渶浼樿В銆�
#### 2. 鍥炴函绠楁硶
鍥炴函绠楁硶鏄�涓�绉嶉�氳繃閫愭�ユ瀯寤鸿В鐨勬柟寮忥紝灏濊瘯鎵�鏈夊彲鑳介�夐」骞跺湪涓嶆弧瓒虫潯浠舵椂鍙婃椂鍥為��鐨勬柟娉曘�傝繖绉嶆柟寮忓湪瑙ｅ喅缁勫悎浼樺寲闂�棰樻椂闈炲父鏈夋晥锛屾瘮濡傝儗鍖呴棶棰樸��
#### 3. 鍔ㄦ�佽�勫垝
鍔ㄦ�佽�勫垝鏄�涓�绉嶆妸澶嶆潅闂�棰樺垎瑙ｆ垚鏇寸畝鍗曞瓙闂�棰樼殑绛栫暐銆傚畠閫氳繃淇濆瓨宸茶В鍐崇殑瀛愰棶棰樼粨鏋滀互閬垮厤閲嶅�嶈�＄畻锛屽疄鐜版晥鐜囩殑鎻愬崌銆傚姩鎬佽�勫垝鍦ㄦ煇浜汵P闂�棰橈紙濡�0-1鑳屽寘闂�棰樸�佹渶闀垮叕鍏卞瓙搴忓垪锛変腑闈炲父鏈夋晥銆�
#### 4. 杩戜技绠楁硶
瀵逛簬鏌愪簺NP闂�棰橈紝灏界�℃壘鍒版渶浼樿В鐨勬椂闂村�嶆潅搴﹂珮锛屼絾鍙�浠ヤ娇鐢ㄨ繎浼肩畻娉曞湪澶氶」寮忔椂闂村唴鎵惧埌涓�涓�鎺ヨ繎鏈�浼樼殑瑙ｃ�備緥濡傦紝璐�蹇冪畻娉曟槸甯哥敤鐨勮繎浼肩畻娉曚箣涓�銆�
#### 5. 闅忔満鍖栫畻娉�
闅忔満鍖栫畻娉曞紩鍏ラ殢鏈哄厓绱犳潵鎻愰珮绠楁硶鏁堢巼銆傞�氬父鎯呭喌涓嬶紝杩欑�嶆柟娉曞彲浠ュ湪杈冪煭鏃堕棿鍐呮壘鍒颁竴涓�瑙ｅ喅鏂规�堬紝铏界劧涓嶈兘淇濊瘉鏄�鏈�浼樿В銆備緥濡傦紝闅忔満鍖栫殑K杩戦偦绠楁硶鍦ㄥ�勭悊鏌愪簺NP闂�棰樻椂琛ㄧ幇鍑鸿壊銆�
#### 6. 鍚�鍙戝紡绠楁硶
鍚�鍙戝紡绠楁硶濡傞仐浼犵畻娉曘�佹ā鎷熼��鐏�銆佽殎缇ょ畻娉曠瓑妯℃嫙鑷�鐒剁幇璞℃潵鎼滅储瑙ｇ┖闂淬�傚畠浠�閫氬父鑳藉湪鍚堢悊鐨勬椂闂村唴鎵惧埌闈炲父鎺ヨ繎鏈�浼樿В鐨勮В鍐虫柟妗堛��
### 搴斿�筃P闂�棰樼殑灏忔妧宸�
1. **闂�棰樼畝鍖�**锛氭湁鏃跺�欙紝灏嗕竴涓�澶嶆潅鐨凬P闂�棰樼畝鍖栦负澶氫釜杈冨皬鐨勫瓙闂�棰橈紝鍙�鑳戒細鏇村�规槗瑙ｅ喅銆傚湪鍒嗘瀽闂�棰樻椂锛屽彲浠ュ皾璇曡瘑鍒�鏄捐�屾槗瑙佺殑绾︽潫鏉′欢銆�
2. **鏁版嵁缁撴瀯浼樺寲**锛氶�夋嫨鍚堥�傜殑鏁版嵁缁撴瀯鍙�浠ュ姞蹇�绠楁硶鐨勬墽琛岄�熷害銆備緥濡傦紝浣跨敤鍝堝笇琛ㄦ潵瀛樺偍宸茬粡璁＄畻鐨勫瓙闂�棰樼粨鏋滐紝浠ュ疄鐜板揩閫熸煡鎵俱��
3. **骞惰�岃�＄畻**锛氬湪鍙�琛岀殑鎯呭喌涓嬪埄鐢ㄥ苟琛岃�＄畻灏嗛棶棰樼殑瑙ｅ喅鍒嗛厤鍒板�氫釜澶勭悊鍣ㄤ笂锛岃兘澶熸樉钁楁彁楂樿�＄畻鏁堢巼銆�
### 鎬荤粨
鍦ㄩ潰瀵筃P闂�棰樻椂锛岀悊瑙ｉ棶棰樼殑鎬ц川鍙婂叾澶嶆潅鎬ф槸鍏抽敭銆傝櫧鐒舵病鏈夊凡鐭ョ殑澶氶」寮忔椂闂寸畻娉曡兘澶熻В鍐虫墍鏈塏P闂�棰橈紝浣嗘槸閫氳繃杩愮敤鍚勭�嶇畻娉曞拰绛栫暐锛屾垜浠�鍙�浠ュ湪鍙�鎺ュ彈鐨勬椂闂村唴鎵惧埌寰堝ソ鐨勮繎浼艰В鎴栧噯纭�瑙ｃ�傚笇鏈涙湰鏂囪兘涓烘偍甯︽潵NP闂�棰樼殑鍩虹��璁ょ煡鍙婃湁鏁堢殑姹傝В鎬濊矾銆�