《NP完全问题学习.pptx》由会员分享，可在线阅读，更多相关《NP完全问题学习.pptx（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、12.1 P类和NP类问题类问题类问题第1页/共53页第一页，编辑于星期六：十点 四十二分。类问题第2页/共53页第二页，编辑于星期六：十点 四十二分。类问题第3页/共53页第三页，编辑于星期六：十点 四十二分。类问题第4页/共53页第四页，编辑于星期六：十点 四十二分。类问题第5页/共53页第五页，编辑于星期六：十点 四十二分。类问题第6页/共53页第六页，编辑于星期六：十点 四十二分。类问题第7页/共53页第七页，编辑于星期六：十点 四十二分。类问题第8页/共53页第八页，编辑于星期六：十点 四十二分。类问题第9页/共53页第九页，编辑于星期六：十点 四十二分。类问题第10页/共53页第十
2、页，编辑于星期六：十点 四十二分。类问题第11页/共53页第十一页，编辑于星期六：十点 四十二分。类问题第12页/共53页第十二页，编辑于星期六：十点 四十二分。类问题第13页/共53页第十三页，编辑于星期六：十点 四十二分。12.2 NP完全问题完全问题的定义几个典型的NP完全问题其他的NP完全问题第14页/共53页第十四页，编辑于星期六：十点 四十二分。完全问题的定义第15页/共53页第十五页，编辑于星期六：十点 四十二分。完全问题的定义第16页/共53页第十六页，编辑于星期六：十点 四十二分。第17页/共53页第十七页，编辑于星期六：十点 四十二分。第18页/共53页第十八页，编辑于星期
3、六：十点 四十二分。几个典型的NP完全问题可满足性问题（SATISFIABILITY）三元可满足性问题（3_SATISFIABILITY）图的着色问题（COLORING）集团问题（CLIQUE）顶点覆盖问题（VERTEX COVER）第19页/共53页第十九页，编辑于星期六：十点 四十二分。可满足性问题（SATISFIABILITY）第20页/共53页第二十页，编辑于星期六：十点 四十二分。可满足性问题（SATISFIABILITY）第21页/共53页第二十一页，编辑于星期六：十点 四十二分。可满足性问题（SATISFIABILITY）第22页/共53页第二十二页，编辑于星期六：十点 四十二分
4、。三元可满足性问题（3_SATISFIABILITY）第23页/共53页第二十三页，编辑于星期六：十点 四十二分。三元可满足性问题（3_SATISFIABILITY）第24页/共53页第二十四页，编辑于星期六：十点 四十二分。三元可满足性问题（3_SATISFIABILITY）第25页/共53页第二十五页，编辑于星期六：十点 四十二分。三元可满足性问题（3_SATISFIABILITY）第26页/共53页第二十六页，编辑于星期六：十点 四十二分。三元可满足性问题（3_SATISFIABILITY）第27页/共53页第二十七页，编辑于星期六：十点 四十二分。图的着色问题（COLORING）第28
5、页/共53页第二十八页，编辑于星期六：十点 四十二分。图的着色问题（COLORING）第29页/共53页第二十九页，编辑于星期六：十点 四十二分。图的着色问题（COLORING）第30页/共53页第三十页，编辑于星期六：十点 四十二分。图的着色问题（COLORING）第31页/共53页第三十一页，编辑于星期六：十点 四十二分。图的着色问题（COLORING）第32页/共53页第三十二页，编辑于星期六：十点 四十二分。图的着色问题（COLORING）第33页/共53页第三十三页，编辑于星期六：十点 四十二分。集团问题（CLIQUE）第34页/共53页第三十四页，编辑于星期六：十点 四十二分。团问
6、题（CLIQUE）第35页/共53页第三十五页，编辑于星期六：十点 四十二分。集团问题（CLIQUE）第36页/共53页第三十六页，编辑于星期六：十点 四十二分。集团问题（CLIQUE）第37页/共53页第三十七页，编辑于星期六：十点 四十二分。集团问题（CLIQUE）第38页/共53页第三十八页，编辑于星期六：十点 四十二分。顶点覆盖问题（VERTEX COVER）第39页/共53页第三十九页，编辑于星期六：十点 四十二分。顶点覆盖问题（VERTEX COVER）第40页/共53页第四十页，编辑于星期六：十点 四十二分。顶点覆盖问题（VERTEX COVER）第41页/共53页第四十一页，编
7、辑于星期六：十点 四十二分。顶点覆盖问题（VERTEX COVER）第42页/共53页第四十二页，编辑于星期六：十点 四十二分。顶点覆盖问题（VERTEX COVER）第43页/共53页第四十三页，编辑于星期六：十点 四十二分。其他的NP完全问题第44页/共53页第四十四页，编辑于星期六：十点 四十二分。其他的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页第五十三页，编辑于星期六：十点 四十二分。