组合优化 - 版本历史

2021年8月3日 (二) 13:49 唐糖糖

2021-08-03T13:49:26Z

唐糖糖：/* 特定问题 */

2021-08-03T13:47:13Z

特定问题

2021年8月1日 (日) 04:27 唐糖糖

2021-08-01T04:27:54Z

唐糖糖：/* 编者推荐 */

2021-08-01T04:26:51Z

编者推荐

唐糖糖：/* GCOMB：在上亿节点网络上学习带约束的组合优化算法法|Openlab内部读书会第十三期= */

2021-08-01T04:23:48Z

GCOMB：在上亿节点网络上学习带约束的组合优化算法法|Openlab内部读书会第十三期=

2021年8月1日 (日) 04:21 唐糖糖

2021-08-01T04:21:32Z

2021年7月31日 (六) 15:52 唐糖糖

2021-07-31T15:52:44Z

2021年7月31日 (六) 15:50 唐糖糖

2021-07-31T15:50:43Z

2021年7月31日 (六) 15:48 唐糖糖

2021-07-31T15:48:15Z

2021年7月31日 (六) 15:46 唐糖糖

2021-07-31T15:46:44Z

显示更改

@@ 第86行： / 第86行： @@
 * ''NPO(I)''：等价于'''完全多项式时间近似方案 Fully Polynomial-time approximation scheme | PTAS '''。包含背包问题。
-* ''NPO(II)''：等价于'''多项式时间近似方案  Polynomial-time approximation scheme | PTAS ''' 。包含分批调度问题。
+* ''NPO(II)''：等价于'''多项式时间近似方案  Polynomial-time approximation scheme'''。包含分批调度问题。
-* ''NPO(III)''：具有多项式时间算法的NPO问题类，其计算的解的成本最多为最优成本的“c”倍（对于最小化问题），或成本至少为最优成本的<math>1/c</math>（对于最大化问题）。在尤拉·赫罗姆科维奇 Juraj Hromkovic 的书中，除了P=NP之外，所有的NPO(II)问题都被排除在这个类之外。如果没有排除，则等于APX（approximable）。包含'''最大可满足性问题 MAX-SAT '''和标准的旅行商问题| TSP。
+* ''NPO(III)''：具有多项式时间算法的NPO问题类，其计算的解的成本最多为最优成本的“c”倍（对于最小化问题），或成本至少为最优成本的<math>1/c</math>（对于最大化问题）。在尤拉·赫罗姆科维奇 Juraj Hromkovic 的书中，除了P=NP之外，所有的NPO(II)问题都被排除在这个类之外。如果没有排除，则等于APX（approximable）。包含'''最大可满足性问题 MAX-SAT '''和标准的旅行商问题 | TSP。
 * ''NPO(IV)''：多项式时间算法的一类NPO问题，以比率为输入大小的对数多项式来逼近最优解。在Hromkovic的书中，除非P=NP，否则所有的NPO(III)-问题都不属于此类。包含集合覆盖问题。
-* ''NPO(V)''：多项式时间算法的一类NPO问题，以某个函数限定的比率来逼近最优解。在Hromkovic的书中，除非P=NP，否则所有NPO(IV)-问题都不属于这类问题。包含旅行商问题| TSP和'''团问题|最大团问题  Clique problem|Max Clique problems '''。
+* ''NPO(V)''：多项式时间算法的一类NPO问题，以某个函数限定的比率来逼近最优解。在Hromkovic的书中，除非P=NP，否则所有NPO(IV)-问题都不属于这类问题。包含旅行商问题和'''团问题|最大团问题  Clique problem|Max Clique problems'''。

@@ 第98行： / 第98行： @@
 [[Image:300px-TSP_Deutschland_3.png|thumb|200px|德国15个最大城市的最佳旅行推销员之旅。最优的旅行商途经德国15个最大的城市。在43,589,145,600个可能的游览每个城市的旅行团中，这是最短的一个。]]
-* '''指派问题 Assignment Problem'''
+* 指派问题 Assignment Problem
-* '''封闭性问题 Closure Problem'''
+* 封闭性问题 Closure Problem
-* '''约束满足问题 Constraint Satisfaction Problem'''
+* 约束满足问题 Constraint Satisfaction Problem
-* '''切割问题 Cutting Stock Problem'''
+* 切割问题 Cutting Stock Problem
-* '''控制集问题 Dominating Set'''
+* 控制集问题 Dominating Set
-* '''整数规划 Integer Programming'''
+* 整数规划 Integer Programming
-* '''背包问题 Knapsack Problem'''
+* 背包问题 Knapsack Problem
-* '''线性系统中的最小相关变量 Minimum Relevant Variables In Linear System'''
+* 线性系统中的最小相关变量 Minimum Relevant Variables In Linear System
-* '''最小[[生成树]] Minimum Spanning Tree'''
+* 最小[[生成树]] Minimum Spanning Tree
-* '''护士调度问题 Nurse Scheduling Problem'''
+* 护士调度问题 Nurse Scheduling Problem
-* '''集合覆盖问题 Set Cover Problem'''
+* 集合覆盖问题 Set Cover Problem
-* '''旅行商问题 Traveling Salesman Problem'''
+* 旅行商问题 Traveling Salesman Problem
-* '''车辆重新调度问题 Vehicle Rescheduling Problem'''
+* 车辆重新调度问题 Vehicle Rescheduling Problem
-* '''车辆线路优化问题 Vehicle Routing Problem'''
+* 车辆线路优化问题 Vehicle Routing Problem
-* '''武器目标分配问题 Weapon Target Assignment Problem'''
+* 武器目标分配问题 Weapon Target Assignment Problem
 ==参见==

@@ 第347行： / 第347行： @@
 ----
-本中文词条由信白初步编译，Flipped审校，糖糖编辑，如有问题，欢迎在讨论页面留言。
+本中文词条由信白初步编译，Flipped审校，[[用户：唐糖糖|糖糖]]编辑，如有问题，欢迎在讨论页面留言。
 '''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''

@@ 第315行： / 第315行： @@
 ==编者推荐==
 ====集智视频====
 =====[https://campus.swarma.org/mobile/course/1994 张量网络与组合优化]=====
 本课程是由王磊在集智凯风研读营“张量网络与机器学习专题”中的分享。在此分享中，王磊介绍了如何在张量网络中引入 Tropic 代数，直接将自旋玻璃零温的配分函数映射到张量网络缩并问题上，并利用 GPU，Yao以及 NiLang 进行有效的计算。
@@ 第325行： / 第327行： @@
-=====[https://campus.swarma.org/mobile/course/1086 结合图卷积网络的组合优化和树搜索——图网络读书会第 3 期]
+=====[https://campus.swarma.org/mobile/course/1086 结合图卷积网络的组合优化和树搜索——图网络读书会第3期]=====
 本课程来自集智第 3 期图网络论文解读活动。本课程是对论文《Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search》的解读。
-=====[https://campus.swarma.org/mobile/course/2200 GCOMB：在上亿节点网络上学习带约束的组合优化算法法|Openlab内部读书会第十三期]=====
+=====[https://campus.swarma.org/mobile/course/2200 GCOMB：在上亿节点网络上学习带约束的组合优化算法法|Openlab内部读书会第13期]=====
 本文提出监督学习+强化学习两阶段的框架：监督学习部分利用GCN学习出节点的作为候选解的优劣，强化学习部分在比较好的节点中选出问题的解。
 年的S2V-DQN是第一篇尝试学习如何求解图上组合优化问题的工作，它以及后续的工作主要都集中于如何提升算法的逼近程度，而没有特别考虑在大图上的效率和扩展性，这次介绍的工作GCOMB主要关注这个问题。本文的能够扩展到上亿节点的核心是，计算密集型的步骤只在比较“好”的节点上进行计算。本文提出监督学习+强化学习两阶段的框架：监督学习部分利用GCN学习出节点的作为候选解的优劣，强化学习部分在比较好的节点中选出问题的解。在实际应用中，第一阶段筛除了图上的大部分“无用”节点，使得计算密集型的第二阶段所需考虑的备选节点大大减少，从而完成加速。
 ====CSDN社区====
 =====[https://blog.csdn.net/Xurui_Luo/article/details/107371115?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162779109416780274133497%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=162779109416780274133497&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~baidu_landing_v2~default-7-107371115.pc_search_result_control_group&utm_term=%E7%BB%84%E5%90%88%E4%BC%98%E5%8C%96&spm=1018.2226.3001.4187 连续优化、离散优化、组合优化、整数优化和凸优化]=====
 =====[https://blog.csdn.net/m0_37407587/article/details/87169128?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162779109416780274133497%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=162779109416780274133497&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-2-87169128.pc_search_result_control_group&utm_term=%E7%BB%84%E5%90%88%E4%BC%98%E5%8C%96&spm=1018.2226.3001.4187 组合优化中的P问题，NP问题，NP-complete问题和NP-hard问题]=====
 ----

@@ 第330行： / 第330行： @@
-=====[https://campus.swarma.org/mobile/course/2200 GCOMB：在上亿节点网络上学习带约束的组合优化算法法|Openlab内部读书会第十三期]======
+=====[https://campus.swarma.org/mobile/course/2200 GCOMB：在上亿节点网络上学习带约束的组合优化算法法|Openlab内部读书会第十三期]=====
 本文提出监督学习+强化学习两阶段的框架：监督学习部分利用GCN学习出节点的作为候选解的优劣，强化学习部分在比较好的节点中选出问题的解。
 年的S2V-DQN是第一篇尝试学习如何求解图上组合优化问题的工作，它以及后续的工作主要都集中于如何提升算法的逼近程度，而没有特别考虑在大图上的效率和扩展性，这次介绍的工作GCOMB主要关注这个问题。本文的能够扩展到上亿节点的核心是，计算密集型的步骤只在比较“好”的节点上进行计算。本文提出监督学习+强化学习两阶段的框架：监督学习部分利用GCN学习出节点的作为候选解的优劣，强化学习部分在比较好的节点中选出问题的解。在实际应用中，第一阶段筛除了图上的大部分“无用”节点，使得计算密集型的第二阶段所需考虑的备选节点大大减少，从而完成加速。
 ====CSDN社区====
 =====[https://blog.csdn.net/Xurui_Luo/article/details/107371115?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162779109416780274133497%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=162779109416780274133497&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~baidu_landing_v2~default-7-107371115.pc_search_result_control_group&utm_term=%E7%BB%84%E5%90%88%E4%BC%98%E5%8C%96&spm=1018.2226.3001.4187 连续优化、离散优化、组合优化、整数优化和凸优化]=====

←上一版本		2021年8月1日 (日) 04:21的版本
第315行：		第315行：

	==编者推荐==		==编者推荐==
		+	====集智视频====
		+	=====[https://campus.swarma.org/mobile/course/1994 张量网络与组合优化]=====
		+	[[File:68295f9a845c4ac75c19f4c9a39912ac.jpg\|thumb\|right\|200px\|王磊，中国科学院理论物理研究所研究员，主要研究方向是深度学习、量子算法、量子多体计算。]]

		+	本课程是由王磊在集智凯风研读营“张量网络与机器学习专题”中的分享。在此分享中，王磊介绍了如何在张量网络中引入 Tropic 代数，直接将自旋玻璃零温的配分函数映射到张量网络缩并问题上，并利用 GPU，Yao以及 NiLang 进行有效的计算。


		+	张量网络可以用来计算有限温度下统计物理模型的配分函数，但一般无法处理零温的基态问题，即组合优化问题。在这个报告中，中科院物理研究所的王磊研究员将介绍如何在张量网络中引入 Tropic 代数，直接将自旋玻璃零温的配分函数映射到张量网络缩并问题上，并利用 GPU，Yao以及 NiLang 进行有效的计算。
		+
		+
		+	=====[https://campus.swarma.org/mobile/course/1086 结合图卷积网络的组合优化和树搜索——图网络读书会第 3 期]
		+	本课程来自集智第 3 期图网络论文解读活动。本课程是对论文《Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search》的解读。
		+	[[File:76e2fb148f086e4bb4b435e5691e27fc.png\|thumb\|right\|300px\|集智俱乐部图网络论文读书会第3期]]
		+
		+
		+	=====[https://campus.swarma.org/mobile/course/2200 GCOMB：在上亿节点网络上学习带约束的组合优化算法法\|Openlab内部读书会第十三期]======
		+	本文提出监督学习+强化学习两阶段的框架：监督学习部分利用GCN学习出节点的作为候选解的优劣，强化学习部分在比较好的节点中选出问题的解。
		+
		+	18年的S2V-DQN是第一篇尝试学习如何求解图上组合优化问题的工作，它以及后续的工作主要都集中于如何提升算法的逼近程度，而没有特别考虑在大图上的效率和扩展性，这次介绍的工作GCOMB主要关注这个问题。本文的能够扩展到上亿节点的核心是，计算密集型的步骤只在比较“好”的节点上进行计算。本文提出监督学习+强化学习两阶段的框架：监督学习部分利用GCN学习出节点的作为候选解的优劣，强化学习部分在比较好的节点中选出问题的解。在实际应用中，第一阶段筛除了图上的大部分“无用”节点，使得计算密集型的第二阶段所需考虑的备选节点大大减少，从而完成加速。
		+	====CSDN社区====
		+	=====[https://blog.csdn.net/Xurui_Luo/article/details/107371115?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162779109416780274133497%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=162779109416780274133497&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~baidu_landing_v2~default-7-107371115.pc_search_result_control_group&utm_term=%E7%BB%84%E5%90%88%E4%BC%98%E5%8C%96&spm=1018.2226.3001.4187 连续优化、离散优化、组合优化、整数优化和凸优化]=====
		+	=====[https://blog.csdn.net/m0_37407587/article/details/87169128?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162779109416780274133497%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=162779109416780274133497&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-2-87169128.pc_search_result_control_group&utm_term=%E7%BB%84%E5%90%88%E4%BC%98%E5%8C%96&spm=1018.2226.3001.4187 组合优化中的P问题，NP问题，NP-complete问题和NP-hard问题]=====

←上一版本		2021年7月31日 (六) 15:52的版本
第313行：		第313行：
	{{DEFAULTSORT:Combinatorial Optimization}}		{{DEFAULTSORT:Combinatorial Optimization}}

−	~~类别: 计算复杂性理论~~	+
		+	==编者推荐==


−	~~类别: 理论计算机科学~~

@@ 第59行： / 第59行： @@
 : <math>
 m(x, y) = g \{ m(x, y') \mid y' \in f(x) \} .
 </math>

←上一版本		2021年7月31日 (六) 15:48的版本
第32行：		第32行：
	==方法==		==方法==

−	对于某些特殊的离散优化问题，有大量的文献是关于'''多项式时间算法 Polynomial-Time Algorithm '''的，其中相当一部分是通过'''线性规划 Linear Programming '''理论统一起来的。属于这个框架的组合优化问题的一些例子包括'''最短路径 Shortest paths '''和'''最短路径树 Shortest-path Tree '''、'''流和循环 Flows And Circulations '''、[[生成树]]、'''匹配和拟阵 Matching And Matroid Problems '''问题。	+	对于某些特殊的离散优化问题，有大量的文献是关于'''多项式时间算法 Polynomial-Time Algorithm'''的，其中相当一部分是通过'''线性规划 Linear Programming'''理论统一起来的。属于这个框架的组合优化问题的一些例子包括'''最短路径 Shortest paths'''和'''最短路径树 Shortest-path Tree'''、'''流和循环 Flows And Circulations'''、[[生成树]]、'''匹配和拟阵 Matching And Matroid Problems'''问题。