学位论文 > 优秀研究生学位论文题录展示

一类约束可满足问题的固定参数算法

作　者: 张驰豪
导　师: 陈翌佳
学　校: 上海交通大学
专　业: 计算机软件与理论
关键词: 约束可满足问题固定参数可解迭代压缩
分类号: TP301.6
类　型: 硕士论文
年　份: 2012年
下　载: 25次
引　用: 0次
阅　读: 论文下载

内容摘要

设为一个二元布尔约束可满足问题的实例。考虑如下问题:判定是否可以删除至多个中约束,使得剩下的约束是可满足的。我们称其为AlmostCSP问题。容易证明,此问题是NP难的,本文从参数复杂性的角度对其可解性进行研究,其中k为参数。Almost CSP的表达能力很强,许多已被广泛研究的组合问题可以看成它的特例。考虑如下两个例子(1)当约束的关系为=?时,Almost CSP等价于判定是否可在一个无向图中删除至多条边使得该图成为二分图。(2)当约束的关系限制为或类关系时,Almost CSP等价于给定一个2-SAT公式,判定是否可以删除至多个子句使其可满足。这两个特例都已经被证明是固定参数可解(Fixed Parameter Tractable)的,于是,有理由猜想,对于最一般的Almost CSP问题,也存在固定参数可解算法。本文对这一猜想提供了正面的佐证。把一类二元布尔关系称之为决定性关系,并且证明当一个约束可满足问题的实例中所有关系均为此类时,AlmostCSP是固定参数可解的。由于=?关系属于此类,本文的结论是(1)问题的推广。此结论的一个推论能够进一步说明,当输入实例中出现的关系不包括或类关系时,问题依然是固定参数可解的。

全文目录

摘要  3-4
ABSTRACT  4-6
目录  6-9
表格索引  9-10
主要符号对照表  10-11
第一章绪论  11-15
  1.1 问题背景  11-12
  1.2 参数复杂性  12
  1.3 主要结果和方法  12-13
  1.4 章节安排  13-15
第二章预备知识  15-23
  2.1 参数复杂性  15-19
    2.1.1 问题的参数化  15-17
    2.1.2 固定参数可解  17
    2.1.3 一些参数复杂性类  17-18
    2.1.4 宽限制搜索树方法  18-19
  2.2 约束可满足问题  19-21
    2.2.1 CSP 的判定版本  19-20
    2.2.2 CSP 的优化版本  20-21
  2.3 图论记号  21-23
第三章迭代压缩技术及应用  23-29
  3.1 基本思想  23-24
    3.1.1 实例：顶点覆盖  23-24
  3.2 图的边二分化  24-27
  3.3 历史注记  27-29
第四章重要割技术  29-35
  4.1 重要割的定义和性质  29
  4.2 重要割的计数  29-35
    4.2.1 割函数的子模性  30-31
    4.2.2 计算重要割  31-35
第五章确定类关系的Almost CSP 问题  35-45
  5.1 二元布尔关系  35-36
  5.2 问题定义与主要结论  36
  5.3 规约到图论问题  36-40
    5.3.1 使用迭代压缩规约到中间问题一  37
    5.3.2 从中间问题一到中间问题二  37-38
    5.3.3 从中间问题二到中间问题三  38-39
    5.3.4 从中间问题三到MinMixedCut问题  39-40
  5.4 -MinMixedCut 问题的固定参数可解算法  40-43
    5.4.1 算法描述  41-42
    5.4.2 算法分析  42-43
  5.5 主定理的证明  43-45
    5.5.1 定理5 1 的证明  43-44
    5.5.2 推论5 2 的证明  44-45
第六章结论与公开问题  45-47
参考文献  47-49
致谢  49-51

一类约束可满足问题的固定参数算法

内容摘要

全文目录

相似论文