《NP完全问题详解.pptx》由会员分享，可在线阅读，更多相关《NP完全问题详解.pptx（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、12.1 P类和NP类问题12.1.1 P类问题12.1.2 NP类问题第1页/共53页12.1.1 P类问题第2页/共53页12.1.1 P类问题第3页/共53页12.1.1 P类问题第4页/共53页12.1.1 P类问题第5页/共53页12.1.1 P类问题第6页/共53页12.1.1 P类问题第7页/共53页12.1.2 NP类问题第8页/共53页12.1.2 NP类问题第9页/共53页12.1.2 NP类问题第10页/共53页12.1.2 NP类问题第11页/共53页12.1.2 NP类问题第12页/共53页12.1.2 NP类问题第13页/共53页12.2 NP完全问题12.2.1
2、NP完全问题的定义12.2.2 几个典型的NP完全问题12.2.3 其他的NP完全问题第14页/共53页12.2.1 NP完全问题的定义第15页/共53页12.2.1 NP完全问题的定义2第16页/共53页第17页/共53页第18页/共53页12.2.2 几个典型的NP完全问题12.2.2.1 可满足性问题（SATISFIABILITY）12.2.2.2 三元可满足性问题（3_SATISFIABILITY）12.2.2.3 图的着色问题（COLORING）12.2.2.4 集团问题（CLIQUE）12.2.2.5 顶点覆盖问题（VERTEX COVER）第19页/共53页12.2.2.1 可满
3、足性问题（SATISFIABILITY）第20页/共53页12.2.2.1 可满足性问题（SATISFIABILITY）第21页/共53页12.2.2.1 可满足性问题（SATISFIABILITY）第22页/共53页12.2.2.2 三元可满足性问题（3_SATISFIABILITY）第23页/共53页12.2.2.2 三元可满足性问题（3_SATISFIABILITY）第24页/共53页12.2.2.2 三元可满足性问题（3_SATISFIABILITY）第25页/共53页12.2.2.2 三元可满足性问题（3_SATISFIABILITY）第26页/共53页12.2.2.2 三元可满足性
4、问题（3_SATISFIABILITY）第27页/共53页12.2.2.3 图的着色问题（COLORING）第28页/共53页12.2.2.3 图的着色问题（COLORING）第29页/共53页12.2.2.3 图的着色问题（COLORING）第30页/共53页12.2.2.3 图的着色问题（COLORING）第31页/共53页12.2.2.3 图的着色问题（COLORING）第32页/共53页12.2.2.3 图的着色问题（COLORING）第33页/共53页12.2.2.4 集团问题（CLIQUE）第34页/共53页12.2.2.4 团问题（CLIQUE）第35页/共53页12.2.2.4
5、 集团问题（CLIQUE）第36页/共53页12.2.2.4 集团问题（CLIQUE）第37页/共53页12.2.2.4 集团问题（CLIQUE）第38页/共53页12.2.2.5 顶点覆盖问题（VERTEX COVER）第39页/共53页12.2.2.5 顶点覆盖问题（VERTEX COVER）第40页/共53页12.2.2.5 顶点覆盖问题（VERTEX COVER）第41页/共53页12.2.2.5 顶点覆盖问题（VERTEX COVER）第42页/共53页12.2.2.5 顶点覆盖问题（VERTEX COVER）第43页/共53页12.2.3 其他的NP完全问题第44页/共53页12.2.3 其他的NP完全问题第45页/共53页12.3 co_NP类和NPI类问题第46页/共53页12.3 co_NP类和NPI类问题第47页/共53页12.3 co_NP类和NPI类问题第48页/共53页12.3 co_NP类和NPI类问题第49页/共53页12.3 co_NP类和NPI类问题第50页/共53页12.3 co_NP类和NPI类问题第51页/共53页12.3 co_NP类和NPI类问题第52页/共53页感谢您的观看！第53页/共53页