forked from sailist/AdAlgo
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathREADME.html
236 lines (231 loc) · 9.83 KB
/
README.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>高级算法</title>
<style>
</style>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
body {
font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
font-size: 14px;
line-height: 1.6;
}
</style>
<style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
</head>
<body class="vscode-body vscode-light">
<h1 id="高级算法">高级算法</h1>
<p>点此进入：<a href="https://sailist.github.io/AdAlgo/">学习链接</a>（下方link因为部署需要无法直接查看）</p>
<h2 id="图论离散基础">图论/离散基础</h2>
<ul>
<li><a href="GraphTheory/1.html">平面图</a></li>
<li><a href="GraphTheory/2.html">哈密顿图</a></li>
<li><a href="GraphTheory/3.html">独立集</a></li>
<li><a href="GraphTheory/4.html">对集/匹配（matching）</a></li>
<li><a href="GraphTheory/5.html">补图</a></li>
<li><a href="GraphTheory/bg.html">二分图</a></li>
</ul>
<h2 id="算法分析设计">算法分析设计</h2>
<p>该部份比较简单，因此不做详细介绍，仅提供一个目录和部份知识点。</p>
<ul>
<li>复杂度分析</li>
<li>分治
<ul>
<li><a href="algo/1.html">归并算法</a></li>
</ul>
</li>
<li>贪心</li>
<li>动规
<ul>
<li>划分问题</li>
</ul>
</li>
<li>回溯</li>
<li>局搜</li>
</ul>
<h2 id="图灵机与pnpnpc">图灵机与P/NP/NPC</h2>
<ul>
<li><a href="./turing/1.html">图灵机</a>
<ul>
<li><a href="./turing/2.html">确定型图灵机与非确定性图灵机</a></li>
<li><a href="./turing/3.html">神谕图灵机</a></li>
</ul>
</li>
<li><a href="./turing/prob.html">问题形式</a></li>
<li><a href="./turing/4.html">P/NP/NPC/NPH</a></li>
<li><a href="turing/5.html">多项式归约和图灵归约</a></li>
</ul>
<h2 id="npc-问题证明按照归约顺序排序">NPC 问题证明（按照归约顺序排序）</h2>
<blockquote>
<p>列表项中带有 <code>未完成</code> 前缀的问题只描述了问题，没有说明具体证明过程；带有 <code>完成</code> 前缀的问题描述了问题和核心解决思路，但省略了具体证明过程的；没有符号的问题同时包含了问题和具体证明过程，其中部份额外附注了核心思路。（下同）</p>
</blockquote>
<ul class="contains-task-list">
<li class="task-list-item"><input class="task-list-item-checkbox" checked="" disabled="" type="checkbox"> <a href="doc/sat.html">SAT（布尔可满足性问题，Cook定理）</a></li>
</ul>
<hr>
<ul class="contains-task-list">
<li class="task-list-item"><input class="task-list-item-checkbox" disabled="" type="checkbox"> <a href="doc/3dm.html">3DM（三对集问题）</a>
<ul>
<li><a href="doc/x3c.html">X3C</a>
<ul>
<li><a href="doc/3.html">X3C-Y</a></li>
<li><a href="doc/mc.html">最小集合覆盖问题</a></li>
</ul>
</li>
<li><a href="doc/partri.html">划分三角形问题</a></li>
</ul>
<!-- - *最小测试集问题 -->
</li>
<li><a href="doc/3sat.html">3SAT</a>
<ul class="contains-task-list">
<li class="task-list-item"><input class="task-list-item-checkbox" checked="" disabled="" type="checkbox"> <a href="doc/vc.html">VC（顶点覆盖问题）</a>
<ul class="contains-task-list">
<li><a href="doc/ivs.html">独立集问题</a>
<ul>
<li><a href="doc/clique.html">团问题</a>
<ul>
<li><a href="doc/sgi.html">子图同构问题</a></li>
<li><a href="doc/mds.html">最小迟序排工问题</a></li>
</ul>
</li>
</ul>
</li>
<li class="task-list-item"><input class="task-list-item-checkbox" checked="" disabled="" type="checkbox"> <a href="doc/hc.html">HC（哈密顿回路问题）</a>
<ul>
<li><a href="doc/tsp.html">TSP（货郎问题）</a></li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><a href="doc/par.html">划分问题</a>
<ul>
<li><a href="doc/2.html">广义划分问题归约</a></li>
<li><a href="doc/knapsack.html">背包问题</a></li>
<li><a href="doc/mts.html">多任务排工问题</a></li>
<li><a href="doc/swi.html">区间排工问题</a></li>
</ul>
</li>
</ul>
<h2 id="npc-问题证明按照证明方法排序">NPC 问题证明（按照证明方法排序）</h2>
<ul>
<li>限制技术
<ul>
<li><a href="doc/mc.html">最小集合覆盖问题</a></li>
<li><a href="doc/sgi.html">子图同构问题</a></li>
<li><a href="doc/knapsack.html">背包问题</a></li>
<li><a href="doc/mts.html">多任务排工问题</a></li>
</ul>
</li>
<li>局部替换技术
<ul>
<li><a href="doc/partri.html">划分三角形问题</a></li>
<li><a href="doc/swi.html">区间排工问题</a></li>
<li>*最小测试集问题</li>
<li>*总体计算问题</li>
</ul>
</li>
<li>分支设计技术
<ul>
<li><a href="doc/mds.html">最小迟序排工问题</a></li>
<li>.........</li>
</ul>
</li>
</ul>
<h2 id="npc-问题证明按照证明难度排序">NPC 问题证明（按照证明难度排序）</h2>
<p>以下为分级后的题目难度，可能略有出入，建议掌握所有<strong>2分及以下</strong>的题目，同时了解所有分数题目的实例形式：</p>
<ul>
<li>0分
<ul>
<li><a href="doc/x3c.html">X3C</a></li>
<li><a href="doc/mc.html">最小集合覆盖问题</a></li>
<li><a href="doc/ivs.html">独立集问题</a></li>
<li><a href="doc/clique.html">团问题</a></li>
<li><a href="doc/sgi.html">子图同构问题</a></li>
<li><a href="doc/knapsack.html">背包问题</a></li>
<li><a href="doc/mts.html">多任务排工问题</a></li>
</ul>
</li>
<li>1分
<ul>
<li><a href="doc/2.html">广义划分问题归约</a></li>
<li><a href="doc/swi.html">区间排工问题</a></li>
</ul>
</li>
<li>2分
<ul>
<li><a href="doc/3.html">X3C-Y</a></li>
<li><a href="doc/mds.html">最小迟序排工问题</a></li>
<li><a href="doc/tsp.html">TSP（货郎问题）</a></li>
</ul>
</li>
<li>3分
<ul class="contains-task-list">
<li><a href="doc/partri.html">划分三角形问题</a></li>
<li class="task-list-item"><input class="task-list-item-checkbox" checked="" disabled="" type="checkbox"> <a href="doc/vc.html">VC（顶点覆盖问题）</a></li>
<li><a href="doc/par.html">划分问题</a></li>
<li><a href="doc/4gcp.html">*顶点度不超过4的图的三着色</a></li>
<li class="task-list-item"><input class="task-list-item-checkbox" disabled="" type="checkbox"> <a href="doc/pgcp.html">*平面图三着色</a></li>
<li class="task-list-item"><input class="task-list-item-checkbox" checked="" disabled="" type="checkbox"> <a href="doc/hc.html">HC（哈密顿回路问题）</a></li>
</ul>
</li>
<li>4分
<ul class="contains-task-list">
<li><a href="doc/3sat.html">3SAT</a></li>
<li class="task-list-item"><input class="task-list-item-checkbox" checked="" disabled="" type="checkbox"> <a href="doc/sat.html">SAT（布尔可满足性问题，Cook定理）</a></li>
<li class="task-list-item"><input class="task-list-item-checkbox" disabled="" type="checkbox"> <a href="doc/3dm.html">3DM（三对集问题）</a></li>
</ul>
</li>
<li>5分
<ul>
<li>...</li>
</ul>
</li>
</ul>
<p>难度分级按照 0-5 分评级：</p>
<ul>
<li>0分：<strong>绝对无任何</strong>难度的，一般由等价问题直接归约，只需要理解相关基础概念的问题。</li>
<li>1分：<strong>非绝对无</strong>难度的，不能说一点难度没有，但也不能认为有多少难度，仅能依靠非0分的状态在坐标中定位，这种暧昧的状态被定为 1分，一般由有限步易得条件推导得到。</li>
<li>2分：有难度的<strong>最低值</strong>，但无法对其强弱进行判定，有难度的最低测度。一般是证明存在一定篇幅，但相对理解可以通过举例较为容易的理解的归约。</li>
<li>3分：<strong>很标准</strong>的难，一般是需要大段描述，且中间穿插多个定理，但推演逻辑相对单一线性，且能够通过更简单的描述理解思想的归约。</li>
<li>4分：<strong>标准之上</strong>的难，缺少可以可视化的例子，需要引入许多的符号、公式、定理，只能通过硬核的推导来结束证明。</li>
<li>5分：<strong>具有侵略性</strong>的难。目前仍然未被证明的难题。这暂时不会出现在本项目中。</li>
</ul>
<blockquote>
<p>该评级策略参照某定标法略做更改而来，具体链接已经找不到了。个人认为这是主观评分的一个非常棒的标准。</p>
</blockquote>
<h2 id="其他">其他</h2>
<ul class="contains-task-list">
<li class="task-list-item"><input class="task-list-item-checkbox" disabled="" type="checkbox"> <a href="doc/2sat.html">2SAT 问题</a></li>
<li><a href="doc/gcp.html">图着色问题</a>
<ul class="contains-task-list">
<li><a href="doc/4gcp.html">顶点度不超过4的图的三着色</a></li>
<li class="task-list-item"><input class="task-list-item-checkbox" disabled="" type="checkbox"> <a href="doc/pgcp.html">平面图三着色</a></li>
</ul>
</li>
</ul>
<h2 id="近似算法">近似算法</h2>
<ul>
<li><a href="approx/approx.html">近似算法基础</a></li>
<li><a href="approx/smsp.html">存储最多程序问题</a></li>
<li><a href="doc/knapsack.html">背包问题贪心策略</a></li>
<li><a href="approx/mstmm.html">MST-MM</a></li>
</ul>
<h1 id="reference">Reference</h1>
<ul>
<li>感谢姜海涛老师的精彩讲解</li>
<li><a href="https://pan.baidu.com/s/19Uhhbp88ZCE2RLNj8Q_M-w">《算法设计与分析》，朱大铭,马绍汉, 高等教育出版社-nuuc</a></li>
</ul>
<h1 id="contributor">Contributor</h1>
<ul>
<li><a href="https://github.com/Kaiyiwing">Kaiyi</a></li>
<li><a href="https://github.com/sailist/AdAlgo/graphs/contributors">Contributor List</a></li>
</ul>
</body>
</html>