顶点覆盖问题

组合优化组合优化问题优化问题可以分为两类：一类是连续变量的问题，另一类是离散变量的问题，后者称为组合优化问题。组合优化问题的任务：从一个有限或可数无限集里，寻找一个使得目标函数最优的对象——典型地包括：一组赋值，一个集合，一个排列。组合优化问题随处可见，具有很强的工程代表性应用。许多组合优化问题都是NP难的：最大可满足性（MaxSAT)问题，最大团问题，最小顶点覆盖问题，旅行商问题。。。组合优化组合优化问题优化问题可以分为两类：一类是连续变量的问题，另一类是离散变量的问题，后者称为组合优化问题。组合优化问题的任务：从一个有限或可数无限集里，寻找一个使得目标函数最优的对象——典型地包括：一组赋值，一个集合，一个排列。组合优化问题随处可见，具有很强的工程代表性应用。许多组合优化问题都是NP难的：最大可满足性（MaxSAT)问题，最大团问题，最小顶点覆盖问题，旅行商问题。。。求解NP难组合优化问题分支限界：完备算法（保证解的最优性），回溯搜索，遍历解空间启发式搜索（包括局部搜索，演化算法等）：不完备算法，迭代改进，采样解空间局部搜索简单地说，局部搜索是：先产生一个（或一群）完整的候选解，然后进行迭代改进，每一步只修改解的某个局部（比如一个基本单元），直到得到一个令人满意的解或者达到某个资源限制（一般是时间限制）。局部搜索简单地说，局部搜索是：先产生一个（或一群）完整的候选解，然后进行迭代改进，每一步只修改解的某个局部（比如一个基本单元），直到得到一个令人满意的解或者达到某个资源限制（一般是时间限制）。形式化一点说，局部搜索定义为：候选解集合（也称搜索空间）S；目标函数f：S->R(实数集)；初始候选解集合I；邻域关系N:S->2^S，对于每个候选解s，N(s)={s′∈S|N(s,s′)}⊆S;（一般是基于候选解的海明距离，最常见的是1-海明距离邻域）跳转函数（Stepfunction）：定义了如何从当前候选解跳转到它的一个邻居候选解局部搜索局部搜索的优点：简单；通用；容易实现；可扩展性强；许多NP难问题在求解性能上最好的算法都是基于局部搜索什么时候使用局部搜索组合爆炸：对于NP难问题，解空间是问题规模的指数级别时间限制短，或者时间资源非常重要关于问题的领域知识太少接受近似解一个局部搜索的例子一个例子：最大可满足性问题（MaxSAT）变元：x1,x2,x3,…,xn文字：变元或者其否定形式x1,~x1,…子句：文字的析取x1\/~x2,x1\/x2\/~x4,….CNF公式：子句的合取，可看为一个子句集合MaxSAT（优化问题)：给出一组（布尔）赋值，满足最多子句。SAT（判定问题）：是否存在一组（布尔）赋值，满足所有子句。一个局部搜索的例子一个例子：最大可满足性问题（MaxSAT）用局部搜索求解以下MaxSAT（或SAT）实例{x1\/~x2,x1\/x2,x2\/x3,~x1\/x2\/~x3}变元：x1,x2,x3,…,xn文字：变元或者其否定形式x1,~x1,…子句：文字的析取x1\/~x2,x1\/x2\/~x4,….CNF公式：子句的合取，可看为一个子句集合MaxSAT（优化问题)：给出一组（布尔）赋值，满足最多子句。SAT（判定问题）：是否存在一组（布尔）赋值，满足所有子句。赋值不满足的子句初始000x1\/x2,x2\/x3Step1001x1\/x2Step2101~x1\/x2\/~x3Step3110无（找到最优解）局部搜索的循环问题局部搜索的循环问题重复访问（近期刚访问过的）候选解花费很长时间在解空间的某个区域（比如某个局部最优附近的区域）搜索导致：容易陷入局部最优，花费太多时间在做无效搜索。。。很多局部搜索的文献其实都是围绕如何解决这个问题循环问题不可能完全避免这是由局部搜索的无记忆性决定的不可能增加一个记忆机制来记住访问过的候选解，空间时间要求都太庞大局部搜索的循环问题局部搜索的循环问题重复访问（近期刚访问过的）候选解花费很长时间在解空间的某个区域（比如某个局部最优附近的区域）搜索导致：容易陷入局部最优，花费太多时间在做无效搜索。。。很多局部搜索的文献其实都是围绕如何解决这个问题循环问题不可能完全避免这是由局部搜索的无记忆性决定的不可能增加一个记忆机制来记住访问过的候选解，空间时间要求都太庞大已有的（通用）方法随机游动重启以一定条件（如概率）允许非改进步Tabu策略：禁止反转近期内（t步内）所做的改动加权方法改变能量地图格局检测相关概念：解的基本单元一般称为解部件(solutioncomponent)：在最大团问题中是一个点，在可满足性问题中是一个变元。。。解部件的赋值：例如，点{选中，没选中},变元{true,false}格局检测相关概念：解的基本单元一般称为解部件(solutioncomponent)：在最大团问题中是一个点，在可满足性问题中是一个变元。。。解部件的赋值：例如，点{选中，没选中},变元{true,false}格局检测（configurationchecking，简称CC）的直观理解：无法记忆整个解，但可以记忆每个解部件的环境及其变化。通过检测解部件的环境，减少解的局部结构上的循环，以此减少整个搜索的循环问题。对于一个解部件x，如果从上次x改变赋值之后，x的环境没有改变过，那么禁止x变回原来的赋值。格局检测是一种从空间（或结构）上考虑的禁忌策略格局检测解部件的格局我们把解部件的环境信息称为它的格局，可以有不同的定义最常见的是：一个解部件的格局，是一个由它的邻居解部件的赋值构成的向量。格局检测解部件的格局我们把解部件的环境信息称为它的格局，可以有不同的定义最常见的是：一个例子：CCforSAT邻居变量：如果两个变量出现在同一个子句中，称他们是邻居。变量x的格局：一个由x的所有邻居变量的赋值构成的向量。一个解部件的格局，是一个由它的邻居解部件的赋值构成的向量。格局检测用于SAT问题CCforSAT：对于一个变量v，如果从上次v改变赋值之后，v的格局没有改变过，那么禁止v变回原来的赋值。顶点覆盖问题顶点覆盖：对于一个无向图，一个顶点覆盖是一个顶点子集，使得每条边都至少有一个点属于该集合。最小顶点覆盖问题：给定一个无向图，找出最小的顶点覆盖。格局检测用于顶点覆盖问题最小顶点覆盖问题可以通过迭代解决其判定问题来求解当找到一个规模为k的顶点覆盖时，继续寻找一个规模为k-1的顶点覆盖。算法核心：对一个整数k，找一个规模为k的顶点集合覆盖所有的边。初始的时候，构造一个规模为k的顶点集合（候选解）。局部搜索的每一步交换集合中的一点和集合外的一点。格局检测用于顶点覆盖问题最小顶点覆盖问题可以通过迭代解决其判定问题来求解当找到一个规模为k的顶点覆盖时，继续寻找一个规模为k-1的顶点覆盖。算法核心：对一个整数k，找一个规模为k的顶点集合覆盖所有的边。初始的时候，构造一个规模为k的顶点集合（候选解）。局部搜索的每一步交换集合中的一点和集合外的一点。格局检测：对一个顶点v，如果从上次v被移出候选解之后，v的格局没有改变过，那么禁止把v重新加入候选解。格局检测更一般的说，格局检测（CC）是一种思想不同的格局定义

不同的CC策略。比如对SAT问题，变量的格局还可以定义为：变量的关联子句的状态构成的向量。不同的检测方法

不同的CC策略。比如量化CC，以格局改变的幅度作为选择解部件的一个优先序法则。不同的格局定义，禁忌强度不同。可以设计多层次的CC策略。格局检测格局检测已经被使用于多个组合优化问题SAT，MaxSAT，顶点覆盖，最大团，图着色，集合覆盖，支配集，刻度划分问题等等。从2011年提出到目前已经产生20几篇论文（包括其他团队）。格局检测对SAT领域产生极大影响2013年SAT比赛随机组接近40%的solver使用该技术；最近三年，共有6个获奖SATsolver使用该技术，包括2个第一，2个第二，2个第三；最近两年，非完备算法组获奖的MaxSAT

solver大都采用了格局检测。AAAI2013年关于SAT方面的TutorialForum评价“Itisoutstanding.Itislikelychangingthegame.”机遇和挑战把格局检测（CC）用于提高原有局部搜索算法容易实现，开销小（高效实现CC策略参考本人在AIJournal2011和AIJournal2013的两篇论文）可以普遍用于各种组合优化问题尝试不同的CC策略，总有一款适合你

（比如对于SAT问题已有4种CC策略：基于邻居变量的CC，基于关联子句的CC，量化CC，双层CC）机遇和挑战把格局检测（CC）用于提高原有局部搜索算法容易实现，开销小（高效实现CC策略参考本人在AIJournal2011和AIJournal2013的两篇论文）可以普遍用于各种组合优化问题尝试不同的CC策略，总有一款适合你

（比如对于SAT问题已有4种CC策略：基于邻居变量的CC，基于关联子句的CC，量化CC，双层CC）格局检测的理论分析目前只得到一个结果从理论上证明格局检测的有效性？需要理论工作！参考文献关于格局检测（CC）的更多信息，请参考以下文献Localsearchwithedgeweightingandconfigurationcheckingheuristicsforminimumvertexcover.Artif.Intell.175(9-10):1672-1696(2011)LocalsearchforBooleanSatisfiabilitywithconfigurationcheckingandsubscore.Artif.Intell.204:75-98(2013)ClauseStatesBasedConfigurat