文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 机器学习算法
侵权投诉

机器学习算法

机器学习算法

    本文由侯国英贡献

    ppt1。

    第七章 NP问题选讲 NP问题选讲

    邹权(博士) 邹权(博士) 计算机科学系

    提要

    7.1 概念 7.2 规约 7.3 最大独立集问题

    7.1 概念

    判定问题 ? P是所有可在多项式时间内用确定算法求解 是所有可在多项式时间内用确定算法求解 判定问题的集合 的集合。 的判定问题的集合。 ? NP问题是所有可用多项式时间算法验证其 NP问题是所有可用多项式时间算法验证其 问题是所有可用多项式时间算法验证 猜测准确性的判定问题的集合。 判定问题的集合 猜测准确性的判定问题的集合。 ? P ?NP ? P = NP ? P≠NP!

    http://gregbaker.ca/blog/2010/08/07/p-n-np/ http://gregbaker.ca/blog/2010/08/07/p-

    多项式时间规约

    – 问题A能够多项式时间规约到B 问题A能够多项式时间规约到B – 说明:B比A难! 说明:

    NP完全问题,满足: NP完全问题,满足: 完全问题

    – 该问题是NP问题 该问题是NP NP问题 – 所有其他的NP问题都可以多项式时间规约到该问题 所有其他的NP NP问题都可以多项式时间规约到该问题

    NP P NPC

    NP-hard

    7.2 规约

    3-CNF可满足性问题 CNF可满足性问题

    – CNF(合取范式):如果一个布尔公式是 CNF(合取范式):如果一个布尔公式 ):如果一个布尔公式是 一些子句的合取 一些子句的合取(与),而且子句是一 合取( 个文字或多个文字的析取 析取( 个文字或多个文字的析取(或),则该 公式是CNF CNF。 公式是CNF。 – 如果CNF中每个子句都有且只有3个不同 如果CNF中每个子句都有且只有3 CNF中每个子句都有且只有 的文字,则该公式称为3-CNF。 的文字,则该公式称为3 CNF。 – 例:(x1 ∨ ?x1 ∨ ?x2) ∧(x3 ∨ x2 ∨ x4) ∧(?x1 ∨ ?x3∨ ?x4)

    7.2 规约

    最大团问题

    – 对于无向图G,一个团即图G的一个完全 对于无向图G 一个团即图G 子图 – 最大团问题即是否可以找出一个团,使 最大团问题即是否可以找出一个团, 得其包含的顶点个数大于k 得其包含的顶点个数大于k

    顶点覆盖问题

    – 对于无向图G=(V,E),是否可以找出子集 对于无向图G=(V,E) G=(V,E), V’,使得如果边(u,v) V’或 V’,使得如果边(u,v) ∈E,则u ∈V’或v V’, ∈V’,且|V’|<k

    已知3-CNF可满足问题是一个NPC问题, 已知3 CNF可满足问题是一个NPC问题 可满足问题是一个NPC问题, 试证明最大团问题也是NPC NPC问题 试证明最大团问题也是NPC问题

    – – – 首先易证最大团是一个NP问题。 首先易证最大团是一个NP问题。 NP问题 构造一个图G 为3-CNF φ构造一个图G。 然后欲证3 然后欲证3-CNF φ可满足当且仅当图G有一个 可满足当且仅当图G 大小为k的团。 大小为k的团。 – 多项式规约说明:如果最大团问题可以多项 多项式规约说明: 式时间解决,那么3 CNF亦可以 也就是说: 亦可以。 式时间解决,那么3-CNF亦可以。也就是说: 最大团不会比3 CNF容易 容易! 最大团不会比3-CNF容易!

    已知最大团问题是一个NPC问题,试证明 已知最大团问题是一个NPC问题, NPC问题 顶点覆盖问题也是NPC NPC问题 顶点覆盖问题也是NPC问题

    – – – 首先易证顶点覆盖是一个NP问题。 首先易证顶点覆盖是一个NP问题。

第1页

你可能喜欢

  • 数据挖掘十大算法
  • 机器学习数据
  • 产业布局规划
  • 参数估计
  • 贝叶斯决策

热门文档

相关文档

  • 机器学习十大算法的每个算法的核心思想、工作原理、适...

    机器学习十大算法的每个算法的核心思想、工作原理、适用情况及优缺点_互联网_IT/计算机_专业资料。机器学习十大算法的每个算法的核心思想、工作原理、适用情况及优...

  • 机器学习算法

    (2010) 01 - 0043 - 05 基于相关向量机的机器学习算法研究与应用杨树仁 ,沈洪远 ( 湖南科技大学 信息与电气工程学院 ,湖南 湘潭 411201) 摘要— 相关向量机 ...

  • 机器学习算法总结

    机器学习算法总结_计算机软件及应用_IT/计算机_专业资料。机器学习算法总结 C4.5, k-Means, SVM, Apriori, EM, PageRank,AdaBoost, kNN,Naive Bayes, and ...

  • 机器学习算法简介

    第八章 机器学习算法简介邹权(博士) 计算机科学系 提要 8.1 机器学习问题 8.2 机器学习算法 8.3 机器学习应用 8.4 WEKA平台简介 8.1 机器学习问题 ? ...

  • 机器学习10大经典算法

    机器学习10大经典算法_IT/计算机_专业资料。一份总结~1、C4.5 机器学习中,决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。 树中每个...

  • 机器学习算法:J48和JRip

    机器学习; 分类算法: 入侵检测 中图分类号 :I0.r31 ’P6 文献标识码 :A 文章编号 :17-48(o)6-7—46256240-02o o0 Anlssadcmprsno lsictnagrtmsayi n ...

  • 机器学习十大算法的每个算法的核心思想、工作原理、适...

    5-1 简述机器学习十大算法的每个算法的核心思想、工作原理、适用情况及优缺点等。 1)C4.5 算法: ID3 算法是以信息论为基础,以信息熵和信息增益度为衡量标准,...

  • 机器学习算法

    机器学习算法_互联网_IT/计算机_专业资料。机器学习算法总结1. C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继承了...

  • 机器学习算法分类

    机器学习算法分类_计算机软件及应用_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 机器学习算法分类_计算机软件及应用_IT/计算机_专业资料。...

  • 大数据下的机器学习算法综述

    第27 卷第 4 期 2014 年 4 月 模式识别与人工智能 PR & AI Vol. 27 Apr. No. 4 2014 大数据下的机器学习算法综述何 1 * 清 1 李 宁 1, 2, 3...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email