Strassen 算法的一丁点推导(ﾉ*･ω･)ﾉ
NP-Complete问题乱证
Posted on
Edited on
做一做课后题吧~
3-3SAT问题NP完全性证明
Posted on
Edited on
X3C-1与广义划分问题的NP完全性证明
Posted on
Edited on
老师上课留的作业
还蛮简单的（
X3C-1问题
首先你需要知道什么是X3C问题（假装你知道了，其实是我懒得写了
X3C-1问题是任意两个元素的交的大小小于等于1
证明
我们尝试用X3C来归约到X3C-1来证明这件事情。
其实蛮简单的，假设$(a,b,c)$是X3C集合的一个元素。
我们把它拆成以下5个元素
$$(a, e1, e2) \ (b, e3, e4) \ (c, e5, e6) \ (e1, e3, e5) \ (e2, e4, e6)$$
正确性显然（
广义划分问题
狭义的划分问题是将集合里的元素划分成两个部分，每个部分的和相等
而广义划分问题便是使得两个部分保持1:2的关系
证明
尝试从划分问题归约到这个问题。
假设原集合为S
加入$\frac{3}{2}S$与$\frac{7}{2}S$两个元素，正确性显然（
顶点覆盖问题度数贪心算法的一个下界
Posted on
Edited on
23树的一种删除方法
Posted on
Edited on
Burnside引理与Polya计数原理
Posted on
Edited on
Burnside引理与Polya计数原理
Burnside引理简介
这个定理主要叙述了在置换群作用下元素的不动情况。
为了方便起见，我们引入颜色的概念，假设一个长度为$n$的向量$x$,其中$x$的第$i$维度记为$x_{i}$,定义一共有$m$种颜色，即$x_{i}\in{1,2,\cdots,m}$。假设$y$是$n$上的一个置换，则$y(x)$表示相应颜色的置换。
设$G$是一个置换群，设两个本质不同的染色为两个维度为$n$的向量$x$与$t$，且不存在$g \in G$，使得$g(x) = y$.
假设所有的染色方案集合为$S$.
则可以发现上面定义了一种等价关系。
$Burnside$引理给出了计数这个商集大小的方法。
Burnside引理感性证明
我知道自己没法写出严格的证明，我只能按照自己的思路整理出合我自己思路的证明思路。
严格思路可以参考链接
该定理的证明方式主要基于对于$G$的不同分组计数方式。
我们知道不同的$G$的计数方式可以形成一个等式，而只要我们要求的商集大小存在于这个等式之中，我们就可以求得商集的大小。
我们考虑$G$是一个置换群，将其作用于${1,2,\cdots,n}$上亦是一个等价关系，先考虑其中的一个等价类$[k]$.
不妨记$[k] = {k,k_{1},\cdots,k_{p}}$,其中由等价关系得到对于任意一个$k_{i}$都存在一个$g_{i} \in G$使得$g_{i}(k_{i})=k$
更感性一点，我们可以发现通过$k_{i}$可以找到一个$G$的子集$G_{k_{i}}$对于这个子集中的任意一个元素，都是一个置换，且是一个可以从$k_{i} \rightarrow k$的置换。
根据这样的一个简单说明,我们知道$[k]$中的每个元素都对应了一个$G$的子集，并且这些子集是无交的而且这些的并是$G$，想想为什么吧。
于是我们得到了一个关于$|G|$的式子，即$$|G| = \sum_{\hat{k}\in [k]}|G_{\hat{k}}|$$
到此为止便是简单思路能够思考到的位置了。
下面就是些只能仰慕的推导了。
数学家们发现$|G_{\hat{k}}|$是相等的。
可以简单在这里证明一下。
令$G_{k_{i}} = {g_{1},\cdots,g_{q}}$，取$g_{1}$作用于$G_{k}$,记结果为$\hat{G_{k}}$现在$\hat{G_{k}}$的每个元素都是$k \rightarrow k_{i}$的一个置换，根据定义$\hat{G_{j}} \subseteq G_{k}$ 用来比大小的话就是$|G_{k_{i}}| = \hat{G_{k}} \leq G_{k}$
接下来只要证明反向包含就行了。
任取$G_{k_{i}}$的一个元素$g_{j}$, 显然$g_{j} = g_{1}*g_{1}^{-1}*g_{j}$,其中$g_{1}^{-1}*g_{j} \in G_{k}$,于是$g_{j} \in \hat{G_{k}}$，于是反向包含就证好了。
于是我们得到了$$|G| = |G_{k}||[k]|$$
为了思路的连贯，并没有保持和参考文章一样的记号。
接下来，对于$G$与$S$列一个矩阵，定义$\mu(g,s) = [g(s)==s]$
$\sum_{g}\sum_{s}\mu(g,s) = \sum_{s}|G_{s}| = t |G_{s}|[s] = t|G|$
于是最后的结果为$t = \frac{1}{|G|}\sum_{g}\sum_{s}\mu(g,s)$
Polya计数原理的简述与感性证明
之所以将它称之为计数原理在于这个方法简化了上面引理的一部分计算。
引用上面Burnside引理的结果$t = \frac{1}{|G|}\sum_{g}\sum_{s}\mu(g,s)$
Polya计数原理简化了$\sum_{s}\mu(g,s)$的计算。
原理在于对每个置换进行循环分解。
大概举个例子$g = (1)(2,3)(4,5,7)(6)(9)$
可以理性观察这个置换，只有每个括号里的元素颜色一样的时候才会对答案有贡献。
于是$\sum_{s}\mu(g,s) = m^{|g|}$
其中$|g|$表示$g$再进行循环分解后有多少个括号。
于是上面的式子就变成了$t = \frac{1}{|G|}\sum_{g}m^{|g|}$
k-median问题在Metric空间上的近似解法
Posted on
Edited on
问题定义
先定义一下用到的符号
空间中有许多工厂，也有许多客户，集合$F$表示工厂集合，集合$C$表示客户集合，y要求给每个客户选择一个工厂，一个工厂可以被多个客户所选择，若一个工厂$x$被客户$y$所选择了，那么称$y$规$x$管理，定义距离函数为$d(x,y)，x \in F, y\in C$表示$y$选择$x$的代价。
具体问题是找到最多$k$个工厂，管理所有的客户，使得距离函数和最小。
这个问题在公制空间上的版本成为Metric K-median问题，是指$d(x,y)$满足正定性，对称性和三角形不等式。
NP？
这其实并不是一个NP-Hard问题，设计近似算法的原因在于加速运算
$C_{2n}^{n}$依旧是多项式复杂度内的问题。
局部搜索算法
首先可以通过简单分析得到选$k$个工厂一定比选择小于$k$个工厂要优。
现在来介绍一种简单的近似算法。
首先随机选择一个集合$S$, 使得$S \subset F$， 并且$|S| = k$， 为了描述方便，扩展一下距离函数的定义令$d(S,y) = \min{d(x,y)},x\in S, y\in C$
然后枚举每个不在$S$中的工厂$z$, 尝试替换$S$中的工厂$x$, 如果能使得答案变得更优就换掉。
这样就会得到一个局部最优解。
实现思路非常简单而且是多项式时间复杂度的做法。
近似度分析
令最优解所选择的工厂集合为$S^{*}$, 其中的元素一般使用$o$来表示。
令上面算法得到的工厂集合为$S$, 其中的元素一般使用$s$来表示。
令$C(x)，x\in F$表示$x$这个元素管理的客户的集合。
首先定义一个术语叫做捕获，如果$C(s) \bigcap C(o) \geq \frac{1}{2}C(o)$则称$s$捕获了$o$。
引理
如果$C(s) \bigcap C(o) < \frac{1}{2}C(o)$，则$C(o)$存在一个自己到自己的满射，使得每一个$x \in C(s)\bigcap C(o)$，可以映射到$C(o) - C(s)$.
我也不知道为什么
定理
该局部搜索算法的近似度为5
证明
首先将$S$根据捕获的最优解中元素的个数分类
$S_{0}$集合表示每个元素不捕获任何最优解中的元素
$S_{1}$集合表示每个元素都捕获最优解中的一个元素
$S_{2}$集合表示每个元素都捕获最优解中的至少两个元素
下面进行$k$次交换，注意并不是连续进行$k$次交换，而是每次都从初始状态进行交换，综合考虑其的代价。
考虑$s \in S_{1}$它所捕获的元素为$o$对于$C(o) \bigcap C(s)$的元素分配给$o$，更严格地这里将$C(o)$的所有元素全部分配$o$(这样相较于之前那种方式并不一定使得当前的答案更加优)，对于$C(o)-C(s)$的元素，因为其中的有个元素为$y$，假设在$S^{}$中分配给了$o^{}$,由于$s$已经捕获了$o$并且因为$s \in S_{1}$于是$o^{}$一定不被$s$所捕获，于是在$C(o^{})$存在一个单射，假设$s^{‘}$为其的像，同时$s^{’} \in C(s^{})$ ,于是将$s$分配给$s^{}$
由三角不等式$$d(y, s^{}) \leq d(y,o^{})+d(o^{},s^{‘}) + d(s^{‘}, s^{})$$
这样一次交换之后$Cost$的变化为
$0 \leq Cost(S-s+o) - Cost(S) \leq \sum_{x \in C(o)} [d(o,x) - d(s,x)] + \sum_{x \in C(s) - C(o)}[d(y,o^{})+d(o^{},s^{‘}) + d(s^{‘}, s^{*}) - d(s, x)]$
接下来考虑剩下的元素该如何交换，可以发现$S_{0}$中的每个元素最多使用$2$次便可以完成最优解中的每个元素被交换一次。
同时可以发现也满足以上不等式。
于是。
将这个不等式累加$k$次，得到$0 \leq Cost(OPT) - Cost(S) + 2*(Cost(OPT) + Cost(OPT) + Cost(S) - Cost(S))$
于是近似度为$5$.
一些学习过程中用到的电子书
Posted on
Edited on
一些学习过程中用到的电子书