第1页 / 共116页
第2页 / 共116页
第3页 / 共116页
第4页 / 共116页
第5页 / 共116页
第6页 / 共116页
第7页 / 共116页
第8页 / 共116页
NP完全问题 相关.pdf
1. 计算复杂性理论（Computational complexity theory）
1.1. 问题描述
1.2. 历史
1.3. 基本概念和工具
1.3.1. 计算模型与计算资源
1.3.2. 判定性问题和可计算性
1.3.3. 算法分析
1.3.4. 复杂性类
1.3.5. 归约
1.4. P与P关系问题及相关理论
1.4.1. NP和P的定义
1.4.2. NP与P关系问题
1.4.3. NP完备理论
1.4.4. 电路复杂性
1.4.5. 其它NP与P关系问题相关的理论
1.5. 理论与实践
1.6. 参考
2. NP完全问题
1.1. 问题描述
1.2. 子集合加总问题
1.3. NPC的正式定义
1.4. 范例问题
1.5. 折衷的解法
1.6. 其他变换法
1.7. 参阅
1.8. 注释
1.9. 参考资料
3. 背包问题：（Knapsack problem）
3.1. 问题描述
3.2. 定义
3.3. 计算复杂度
3.4. 动态规划解法
3.4.1. 无界背包问题
3.4.2. 0-1背包问题
3.5. 二次背包问题
3.6. 外部链接
4. 最短路径问题
4.1. 问题描述
5. 旅行推销员问题（Travelling Salesman Problem, TSP）
5.1. 问题描述
5.2. 计算的复杂性
5.3. NP困难（NP-hard）
5.4. 解法
5.5. 参考来源
5.6. 外部链接
6. 约束补偿问题（CSP）
6.1. 问题描述
6.2. 形式的定义
6.3. CSPs的解决方案
6.4. CSPs的理论方面
6.4.1. 判定问题
6.4.2. 功能问题
6.5. CSPs的变型
6.5.1. 动态CSPs
6.5.2. 灵活的CSPs
6.6. 参见
6.7. 参考文献
6.8. 扩展阅读
6.9. 超链接
7. 最优化（optimization）
7.1. 问题描述
7.2. 数学表述
7.3. 符号表示
7.4. 主要分支
7.5. 算法
7.6. 人工智能和最优化
7.7. 参见
7.8. 参考文献
7.9. 外部链接
8. 动态规划（Dynamic programming，DP）
8.1. 问题描述
8.2. 概述
8.3. 步骤
8.4. 实例
8.4.1. 斐波那契数列(Fibonacci polynomial)
8.4.2. 背包问题
8.5. 使用动态规划的算法
8.6. 参考
9. 线性规划问题（Linear Programming ,LP）
9.1. 问题描述
9.2. 标准型
9.3. 增广矩阵（松弛型）
9.4. 对偶
9.5. 理论
9.6. 算法
9.7. 整数规划(IP)
9.8. 参见
9.9. 参考
9.10. 外部链接
9.11. 求解软件包
10. 迪科斯彻算法（Dijkstra's algorithm）
10.1. 描述
10.2. 算法描述
10.3. 伪代码
10.4. 时间复杂度
10.5. 相关问题及算法
10.6. 参考
10.7. 外部链接
11. A*搜索算法
11.1. 描述
11.2. 伪代码
11.3. 外部链接
12. 遗传算法
12.1. 描述
12.2. 启发式算法与最短路径问题
12.3. 启发式算法对运算效能的影响
12.4. 找寻新的启发式算法
12.5. 参阅
13. 遗传算法
13.1. 描述
13.2. 遗传算法的机理
13.2.1. 算法
13.2.2. GA参数
13.2.3. 模式定理
13.2.4. 积木块假设
13.2.5. 在线交互式演示与学习
13.2.6. 特点
13.3. 变量
13.4. 适用的问题
13.5. 遗传算法的不足之处
13.6. 改进的遗传算法
13.7. 发展历史
13.8. 应用领域
13.9. 相关技术
13.10. 参见
13.11. 参考文献
13.12. 外部链接
14. 局部搜索算法
14.1. 描述
14.2. 应用
14.3. 描述
14.4. 参见
14.5. 参考资料
15. 禁忌搜索（Tabu Search，TS）
15.1. 描述
16. 模拟退火算法
16.1. 描述
16.2. 简介
16.3. 演算步骤
16.4. 虚拟码
16.5. 参见
16.6. 外部链接
17. 蚁群算法（Ant Colony Optimization, ACO）
17.1. 描述
17.2. 常见的扩展
17.2.1. 精英蚂蚁系统
17.2.2. 最大最小蚂蚁系统（MMAS）
17.2.3. 蚁群系统
17.2.4. 基于排序的蚂蚁系统（ASrank）
17.2.5. 连续正交蚁群（COAC）
17.3. 收敛
17.4. 应用
17.4.1. 调度问题
17.4.2. 车辆路径问题
17.4.3. 分配问题
17.4.4. 设置问题
17.4.5. 其他
17.5. 相关的方法[编辑]
17.6. 历史[编辑]
18. 贪婪算法（Greedy algorithm）
18.1. 描述
18.2. 细节
18.3. 应用
18.4. 参见
18.5. 参考文献
19. 粒子群优化(Particle Swarm Optimization, PSO)
19.1. 描述
19.2. 算法原理
19.3. 算法参数
19.4. 外部链接
20. 支持向量机（Support Vector Machine,SVM）
20.1. 描述
20.2. 介绍
20.3. 动机
20.3.1. 问题定义
20.3.2. 原型(Primal form)
20.3.3. 对偶型（Dual Form）
20.3.4. 后验svm
20.4. 软间隔(Soft margin)
20.5. 回归
20.6. 应用
20.7. 参见
20.8. 参考书目
20.9. 外部链接[
20.9.1. 概念
20.9.2. 软件
20.9.3. 互动SVM应用
21. 人工神经网络（Artificial Neural Network，ANN）
21.1. 描述
21.2. 神经元
21.3. 神经元网络
21.3.1. 单层神经元网络
21.3.2. 多层神经元网络
21.4. 人工神经网络的使用性
21.5. 人工神经元网络模型
21.6. 基本结构
21.7. 学习过程
21.8. 种类
21.9. 理论性质
21.9.1. 计算能力
21.9.2. 容量
21.9.3. 收敛性
21.9.4. 综合统计
21.10. 参考条目
21.11. 外部链接
21.12. 参考文献
22. 人工智能（Artificial Intelligence, AI）
22.1. 描述
22.2. 概论
22.3. 发展史
22.4. 研究课题
22.4.1. 演绎、推理和解决问题
22.4.2. 知识表示法
22.4.3. 规划
22.4.4. 学习
22.4.5. 自然语言处理
22.4.6. 运动和控制
22.4.7. 知觉
22.4.8. 社交
22.4.9. 创造力
22.4.10. 多元智能
22.5. 强人工智能和弱人工智能
22.5.1. 强人工智能
22.5.2. 弱人工智能
22.5.3. 对强人工智能的哲学争论
22.6. 研究方法
22.6.1. 控制论与大脑模拟
22.6.2. 符号处理
22.6.3. 子符号方法
22.6.4. 统计学方法
22.6.5. 集成方法
22.7. 实际应用
22.8. 学科范畴
22.8.1. 涉及学科
22.8.2. 研究范畴
22.9. 应用领域
22.10. 参见
22.11. 参考文献
22.11.1. 教材
22.11.2. 人工智能历史
22.11.3. 其他
22.11.4. 扩展阅读
23. 多智能体multi-agent system (M.A.S.)
23.1. 描述
23.2. Concept
23.2.1. Characteristics
23.2.2. Self-organization and self-steering
23.2.3. Systems paradigms
23.2.4. Properties
23.3. The study of multi-agent systems
23.4. Frameworks
23.5. Applications in the real world
23.6. See also
23.7. Further reading
23.8. External links
目 录
计算复杂性问题-NP 完全问题-
最优化-动态规划-经典算法
基于维基百科整理
目 录
1. 计算复杂性理论（Computational complexity theory） ........................................................ 1
1.1. 问题描述 .......................................................................................................................... 1
1.2. 历史 .................................................................................................................................. 1
1.3. 基本概念和工具 .............................................................................................................. 2
1.3.1. 计算模型与计算资源 ........................................................................................... 2
1.3.2. 判定性问题和可计算性........................................................................................ 2
1.3.3. 算法分析 ............................................................................................................... 3
1.3.4. 复杂性类 ............................................................................................................... 3
1.3.5. 归约 ....................................................................................................................... 4
1.4. P 与 P 关系问题及相关理论 ........................................................................................... 5
1.4.1. NP 和 P 的定义 ..................................................................................................... 5
1.4.2. NP 与 P 关系问题 ................................................................................................. 6
1.4.3. NP 完备理论 ......................................................................................................... 6
1.4.4. 电路复杂性 ........................................................................................................... 7
1.4.5. 其它 NP 与 P 关系问题相关的理论 .................................................................... 7
1.5. 理论与实践 ...................................................................................................................... 8
1.6. 参考 .................................................................................................................................. 8
2. NP 完全问题 ........................................................................................................................... 9
1.1. 问题描述 .......................................................................................................................... 9
1.2. 子集合加总问题 .............................................................................................................. 9
1.3. NPC 的正式定义 ........................................................................................................... 10
1.4. 范例问题 ........................................................................................................................ 11
1.5. 折衷的解法 .................................................................................................................... 13
1.6. 其他变换法 .................................................................................................................... 13
1.7. 参阅 ................................................................................................................................ 14
1.8. 注释 ................................................................................................................................ 14
1.9. 参考资料 ........................................................................................................................ 14
3. 背包问题：（Knapsack problem） ..................................................................................... 16
3.1. 问题描述 ........................................................................................................................ 16
3.2. 定义 ................................................................................................................................ 16
3.3. 计算复杂度 .................................................................................................................... 17
3.4. 动态规划解法 ................................................................................................................ 17
3.4.1. 无界背包问题 ..................................................................................................... 18
3.4.2. 0-1 背包问题 ....................................................................................................... 19
3.5. 二次背包问题 ................................................................................................................ 19
3.6. 外部链接 ........................................................................................................................ 19
4. 最短路径问题 ....................................................................................................................... 20
4.1. 问题描述 ........................................................................................................................ 20
5. 旅行推销员问题（Travelling Salesman Problem, TSP） ................................................... 21
目 录
5.1. 问题描述 ........................................................................................................................ 21
5.2. 计算的复杂性 ................................................................................................................ 21
5.3. NP 困难（NP-hard） ..................................................................................................... 21
5.4. 解法 ................................................................................................................................ 21
5.5. 参考来源 ........................................................................................................................ 22
5.6. 外部链接 ........................................................................................................................ 22
6. 约束补偿问题（CSP） ........................................................................................................ 23
6.1. 问题描述 ........................................................................................................................ 23
6.2. 形式的定义 .................................................................................................................... 23
6.3. CSPs 的解决方案 ........................................................................................................... 23
6.4. CSPs 的理论方面 ........................................................................................................... 24
6.4.1. 判定问题 ............................................................................................................. 24
6.4.2. 功能问题 ............................................................................................................. 24
6.5. CSPs 的变型 .................................................................................................................. 24
6.5.1. 动态 CSPs ............................................................................................................ 24
6.5.2. 灵活的 CSPs ........................................................................................................ 25
6.6. 参见 ................................................................................................................................ 25
6.7. 参考文献 ........................................................................................................................ 25
6.8. 扩展阅读 ........................................................................................................................ 26
6.9. 超链接 ............................................................................................................................ 26
7. 最优化（optimization） ....................................................................................................... 27
7.1. 问题描述 ........................................................................................................................ 27
7.2. 数学表述 ........................................................................................................................ 27
7.3. 符号表示 ........................................................................................................................ 27
7.4. 主要分支 ........................................................................................................................ 28
7.5. 算法 ................................................................................................................................ 29
7.6. 人工智能和最优化 ........................................................................................................ 29
7.7. 参见 ................................................................................................................................ 30
7.8. 参考文献 ........................................................................................................................ 30
7.9. 外部链接 ........................................................................................................................ 30
8. 动态规划（Dynamic programming，DP） ......................................................................... 30
8.1. 问题描述 ........................................................................................................................ 30
8.2. 概述 ................................................................................................................................ 31
8.3. 步骤 ................................................................................................................................ 31
8.4. 实例 ................................................................................................................................ 31
8.4.1. 斐波那契数列(Fibonacci polynomial) ................................................................ 31
8.4.2. 背包问题 ............................................................................................................. 32
8.5. 使用动态规划的算法 .................................................................................................... 33
8.6. 参考 ................................................................................................................................ 33
目 录
9. 线性规划问题（Linear Programming ,LP） ....................................................................... 34
9.1. 问题描述 ........................................................................................................................ 34
9.2. 标准型 ............................................................................................................................ 34
9.3. 增广矩阵（松弛型） .................................................................................................... 35
9.4. 对偶 ................................................................................................................................ 36
9.5. 理论 ................................................................................................................................ 37
9.6. 算法 ................................................................................................................................ 38
9.7. 整数规划(IP) .................................................................................................................. 39
9.8. 参见 ................................................................................................................................ 40
9.9. 参考 ................................................................................................................................ 40
9.10. 外部链接 ........................................................................................................................ 40
9.11. 求解软件包 .................................................................................................................... 40
10. 迪科斯彻算法（Dijkstra's algorithm） ................................................................................ 42
10.1. 描述 ................................................................................................................................ 42
10.2. 算法描述 ........................................................................................................................ 42
10.3. 伪代码 ............................................................................................................................ 43
10.4. 时间复杂度 .................................................................................................................... 44
10.5. 相关问题及算法 ............................................................................................................ 44
10.6. 参考 ................................................................................................................................ 45
10.7. 外部链接 ........................................................................................................................ 45
11. A*搜索算法 .......................................................................................................................... 46
11.1. 描述 ................................................................................................................................ 46
11.2. 伪代码 ............................................................................................................................ 46
11.3. 外部链接 ........................................................................................................................ 47
12. 遗传算法 ............................................................................................................................... 48
12.1. 描述 ................................................................................................................................ 48
12.2. 启发式算法与最短路径问题 ........................................................................................ 48
12.3. 启发式算法对运算效能的影响 .................................................................................... 48
12.4. 找寻新的启发式算法 .................................................................................................... 49
12.5. 参阅 ................................................................................................................................ 49
13. 遗传算法 ............................................................................................................................... 51
13.1. 描述 ................................................................................................................................ 51
13.2. 遗传算法的机理 ............................................................................................................ 51
13.2.1. 算法 ..................................................................................................................... 52
13.2.2. GA 参数 ............................................................................................................... 53
13.2.3. 模式定理 ............................................................................................................. 53
13.2.4. 积木块假设 ......................................................................................................... 53
13.2.5. 在线交互式演示与学习...................................................................................... 54
13.2.6. 特点 ..................................................................................................................... 54
目 录
13.3. 变量 ................................................................................................................................ 55
13.4. 适用的问题 .................................................................................................................... 55
13.5. 遗传算法的不足之处 .................................................................................................... 55
13.6. 改进的遗传算法 ............................................................................................................ 56
13.7. 发展历史 ........................................................................................................................ 57
13.8. 应用领域 ........................................................................................................................ 57
13.9. 相关技术 ........................................................................................................................ 58
13.10. 参见 ............................................................................................................................. 58
13.11. 参考文献 ..................................................................................................................... 58
13.12. 外部链接 ..................................................................................................................... 59
14. 局部搜索算法 ....................................................................................................................... 59
14.1. 描述 ................................................................................................................................ 59
14.2. 应用 ................................................................................................................................ 60
14.3. 描述 ................................................................................................................................ 60
14.4. 参见 ................................................................................................................................ 60
14.5. 参考资料 ........................................................................................................................ 61
15. 禁忌搜索（Tabu Search，TS） ....................................................................................... 61
15.1. 描述 ................................................................................................................................ 61
16. 模拟退火算法 ....................................................................................................................... 61
16.1. 描述 ................................................................................................................................ 61
16.2. 简介 ................................................................................................................................ 62
16.3. 演算步骤 ........................................................................................................................ 62
16.4. 虚拟码 ............................................................................................................................ 62
16.5. 参见 ................................................................................................................................ 63
16.6. 外部链接 ........................................................................................................................ 63
17. 蚁群算法（Ant Colony Optimization, ACO） ............................................................. 63
17.1. 描述 ................................................................................................................................ 63
17.2. 常见的扩展 .................................................................................................................... 64
17.2.1. 精英蚂蚁系统 ..................................................................................................... 64
17.2.2. 最大最小蚂蚁系统（MMAS） ......................................................................... 64
17.2.3. 蚁群系统 ............................................................................................................. 64
17.2.4. 基于排序的蚂蚁系统（ASrank） ..................................................................... 64
17.2.5. 连续正交蚁群（COAC） .................................................................................. 64
17.3. 收敛 ................................................................................................................................ 64
17.4. 应用 ................................................................................................................................ 65
目 录
17.4.1. 调度问题 ............................................................................................................. 65
17.4.2. 车辆路径问题 ..................................................................................................... 65
17.4.3. 分配问题 ............................................................................................................. 66
17.4.4. 设置问题 ............................................................................................................. 66
17.4.5. 其他 ..................................................................................................................... 66
17.5. 相关的方法[编辑] .......................................................................................................... 67
17.6. 历史[编辑] ..................................................................................................................... 67
18. 贪婪算法（Greedy algorithm） ...................................................................................... 69
18.1. 描述 ................................................................................................................................ 69
18.2. 细节 ................................................................................................................................ 69
18.3. 应用 ................................................................................................................................ 70
18.4. 参见 ................................................................................................................................ 70
18.5. 参考文献 ........................................................................................................................ 70
19. 粒子群优化(Particle Swarm Optimization, PSO) ........................................................ 71
19.1. 描述 ................................................................................................................................ 71
19.2. 算法原理 ........................................................................................................................ 71
19.3. 算法参数 ........................................................................................................................ 72
19.4. 外部链接 ........................................................................................................................ 73
20. 支持向量机（Support Vector Machine,SVM） ........................................................... 74
20.1. 描述 ................................................................................................................................ 74
20.2. 介绍 ................................................................................................................................ 74
20.3. 动机 ................................................................................................................................ 74
20.3.1. 问题定义 ............................................................................................................. 75
20.3.2. 原型(Primal form) ............................................................................................... 76
20.3.3. 对偶型（Dual Form） ........................................................................................ 77
20.3.4. 后验 svm .............................................................................................................. 77
20.4. 软间隔(Soft margin) ....................................................................................................... 77
20.5. 回归 ................................................................................................................................ 78
20.6. 应用 ................................................................................................................................ 78
20.7. 参见 ................................................................................................................................ 78
20.8. 参考书目 ........................................................................................................................ 78
20.9. 外部链接[ ....................................................................................................................... 79
20.9.1. 概念 ..................................................................................................................... 79
20.9.2. 软件 ..................................................................................................................... 80
20.9.3. 互动 SVM 应用 ................................................................................................... 81
21. 人工神经网络（Artificial Neural Network，ANN） ................................................... 82
目 录
21.1. 描述 ................................................................................................................................ 82
21.2. 神经元 ............................................................................................................................ 82
21.3. 神经元网络 .................................................................................................................... 83
21.3.1. 单层神经元网络 ................................................................................................. 83
21.3.2. 多层神经元网络 ................................................................................................. 84
21.4. 人工神经网络的使用性 ................................................................................................ 84
21.5. 人工神经元网络模型 .................................................................................................... 84
21.6. 基本结构 ........................................................................................................................ 84
21.7. 学习过程 ........................................................................................................................ 85
21.8. 种类 ................................................................................................................................ 85
21.9. 理论性质 ........................................................................................................................ 86
21.9.1. 计算能力 ............................................................................................................. 86
21.9.2. 容量 ..................................................................................................................... 86
21.9.3. 收敛性 ................................................................................................................. 86
21.9.4. 综合统计 ............................................................................................................. 86
21.10. 参考条目 ..................................................................................................................... 86
21.11. 外部链接 ..................................................................................................................... 87
21.12. 参考文献 ..................................................................................................................... 87
22. 人工智能（Artificial Intelligence, AI） .......................................................................... 88
22.1. 描述 ................................................................................................................................ 88
22.2. 概论 ................................................................................................................................ 88
22.3. 发展史 ............................................................................................................................ 88
22.4. 研究课题 ........................................................................................................................ 89
22.4.1. 演绎、推理和解决问题...................................................................................... 89
22.4.2. 知识表示法 ......................................................................................................... 90
22.4.3. 规划 ..................................................................................................................... 90
22.4.4. 学习 ..................................................................................................................... 90
22.4.5. 自然语言处理 ..................................................................................................... 91
22.4.6. 运动和控制 ......................................................................................................... 91
22.4.7. 知觉 ..................................................................................................................... 91
22.4.8. 社交 ..................................................................................................................... 91
22.4.9. 创造力 ................................................................................................................. 91
多元智能 ................................................................................................ 92
22.4.10.
22.5. 强人工智能和弱人工智能 ............................................................................................ 92
22.5.1. 强人工智能 ......................................................................................................... 92
22.5.2. 弱人工智能 ......................................................................................................... 92
22.5.3. 对强人工智能的哲学争论 .................................................................................. 93
22.6. 研究方法 ........................................................................................................................ 93
目 录
22.6.1. 控制论与大脑模拟 ............................................................................................. 93
22.6.2. 符号处理 ............................................................................................................. 94
22.6.3. 子符号方法 ......................................................................................................... 94
22.6.4. 统计学方法 ......................................................................................................... 95
22.6.5. 集成方法 ............................................................................................................. 95
22.7. 实际应用 ........................................................................................................................ 95
22.8. 学科范畴 ........................................................................................................................ 95
22.8.1. 涉及学科 ............................................................................................................. 95
22.8.2. 研究范畴 ............................................................................................................. 96
22.9. 应用领域 ........................................................................................................................ 96
22.10. 参见 ............................................................................................................................. 97
22.11. 参考文献 ..................................................................................................................... 97
教材 ........................................................................................................ 97
人工智能历史......................................................................................... 98
其他 ........................................................................................................ 98
扩展阅读 .............................................................................................. 101
22.11.1.
22.11.2.
22.11.3.
22.11.4.
23. 多智能体 multi-agent system (M.A.S.) ........................................................................ 102
23.1. 描述 .............................................................................................................................. 102
23.2. Concept ......................................................................................................................... 102
23.2.1. Characteristics .................................................................................................... 103
23.2.2. Self-organization and self-steering .................................................................... 103
23.2.3. Systems paradigms ............................................................................................ 103
23.2.4. Properties ........................................................................................................... 104
23.3. The study of multi-agent systems ................................................................................. 105
23.4. Frameworks .................................................................................................................. 105
23.5. Applications in the real world ....................................................................................... 105
23.6. See also ......................................................................................................................... 106
23.7. Further reading ............................................................................................................. 106
23.8. External links ................................................................................................................ 107
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
