其实这门课开始的时候非常非常的担心。因为在本科的时候着实没有认真学过算法和数据结构。更确切的说，大学四年，专业知识几乎就没怎么认真学过，导致如今还在努力的填着当年留下的空缺。
不过庆幸的是，这门课对基础的要求并不是很高，需要回头补得东西倒也不是很多。也算是幸运吧。
Algo.这门课主要内容就4点：
1，局域搜索 local search
2，线性规划 LP
3，回溯算法 back tracking
4，博弈 game theory
其中最主要的就是LP找最优解了。这门课每个星期都要交作业，每次都要和同组的同学要在一起费力的做几个小时才能完成。可以说这门课和另外一门同样也是每个礼拜都交作业的SPEZMOL都是尤其花费功夫的课程。不过现在回头看来，复习的时候倒也就不是那么的恐怖了，只是希望考试的时候能有足够的时间来解题。
再过2天，17号的上午就是Algo.的考试了，这两天会集中精力复习，白天估计会和同学一起在图书馆复习，晚上回来以后如果还有时间的话，就自己在这里做个整理吧。
局域搜索 local search
对于一些问题并不一定非得要全局的最优解，有的时候只要是能解决最优解的次优解也是可以接受的。这时就可以将求全局最优解简化为求局域最优解。同时也为了让初始状态对结果影响太大，而获得更好的效果，还需要多试几次随机设定的初始状态。
为了解决上面的问题，还有一种办法就是模拟自然界中的物理模型（模拟煺火）。在自然界中，当一个很热的金属物体在降温时，虽然从整体上而言分子都是从高位势能往低位势能的位置运动；但是就单个分子而言其运动是无规律的。不过这种无序运动的程度却受温度的影响。也就是说，温度越高，无序程度越高。对应到模拟煺火算法则是有一定的概率使得某状态向成本更高的相邻状态运动。而这个概率受运算时间长短的影响。
LP线性规划
1，首先介绍的是一些基本概念，比如什么是线性规划，目标方程式等。这是通过一个最常见的生产啤酒的例子进行的说明。其中最难的是模型的建立，即变量、目标方程式以及约束条件的设计。
2，然后就是如何从通用表达式向标准表达式转换。即，s1，将所有的未限定的变量通过一对变量转换为大于零的被限定的变量;s2将所有不等式用松弛变量转变成等式。
3，再用simplex算法求最优解。在物理意义上，即转换成凸多边形，然后找最优的顶点。步骤：s1，计算得到一个基础解；s2，得到一个可行的基础解；s3，得到最优解。
4，再接下来的是，所有的IP问题都是成对的。也就是说，如果所求的是最大值，那么一定有一个和其对应的求最小值的IP问题。而这两个问题实质上是同一个问题。而剥去实际意义，单纯从数学角度上，这个问题可以这么理解：
原来是求 max(c*x) 约束条件是 A * X <= b
那么对应的最小值问题则是 min(b*y) 约束条件是 A′ * y >= c
5，LP问题还可以进一步分为ILP，RLP问题。即，所求的解必须是整数还是实数。很明显ILP是难于RLP的。已经得到证明的是，ILP 是NP完全的。所以，对于一些ILP问题，可以用近似解的方法来求解。方法是：s1，将ILP转换为RLP（konsistent）并求解；s2，检验所求得的解是否正确（richtig）。
回溯算法 back tracking
回溯算法有点类似与深度优先的搜索算法。即，深度优先遍历所以解集空间，通常是一棵树。从根节点开始，到第一个叶子节点，再回溯到上一层，然后进入上一层的其它叶子节点，如果上一层的所有叶子节点都已经遍历过了，就再回溯至更上一层，并以此类推直至遍历完成。
伪码算法如下：
Algorithm Backtrack(l，x(1)，....，x(l-1))
Input: l ( depth l is natural number)， partial solution (x(1)，....，x(l-1))
Output: optimal solution (x(1)，....，x(l-1)) in a global variable
if x(1)，....，x(l-1) is a valid solution then
compute the value of (x(1)，....，x(l-1))
else
compute Cl
for all x belong to Cl do Backtrack(l+1 ， (x(1)，....，x(l-1))，x) end for
end if
其中 Cl 是选择后的解集，而不是笛卡尔的所有解集空间。
所以我们需要的是
上面的算法虽然正确，但是效率却很低，当解集空间特别大时，那么需要的时间将非常恐怖。所以这个时候就需要提高效率。其中一个很有效的方法就是bounding function。即，建立一个限定函数，用于剪去那些肯定没必要访问的子树。
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
