5.2 “是否”问题及语言.ppt

5.2 “是否”问题及语言 讨论“是否”问题及其语言表达形式， 从而将“是否”问题的解算转化为相应语言的识别， 这使我们可以利用现有的数学工具 ——形式语言理论。 一个 “是否’’问题Π的所有实例组成集合D∏ ， 解为“是”的实例集合为Y∏ ，显然有 Y∏（ D∏ “是否’’问题的格式由两个部分组成， 第一部分是问题实例的通用描述(简称为实例)， 第二部分是一个问句(简称为问)，该问句要求的回答为“是”或“否”。 例 子图同构问题(简称SI) 实例：两个图Gl＝(V1，E1)和G2＝(V2，E2) 问：图Gl是否含有与G2同构的子图? 即是否存在V’（ V1，E’（ E1， (|V’|＝|V2|，|E’|＝|E2|)，及一对一映射 f：V2→V’ 且具有性质： 边(u,v) ∈E2 ≡ 边(f(u), f(v)) ∈E’ 例 巡回售货员问题 实例：城市集合c＝{cl，c2，…，cm}， d(ci,cj)为正整数(ci, cj ∈ C)， 正整数B 问：是否存在一条包含所有城市的闭合路径且其长度不大于B? 即是否存在城市序列 CΠ1，CΠ2, … CΠm 且 d(CΠ1, CΠ2)+d(CΠ2, CΠ3)+…+d(CΠm, CΠ1) ≤ B 前例显示了如何从一个最优化问题(如上节所述)得到一个“是否’’问题。 这一类由最优化问题衍变而来的“是否”问题不比原先的最优问题难， 如最优问题可用多项式时间算法解答，则相应的是否问题也一定可用多项式时间算法解答。 因此，如果“是否”型巡回售货员问题是NP完全问题(事实上也是)，则最优型巡回售货贞问题也是NP完全问题。 在形式语言中，令∑为有限集合，其元素为符号 则∑*表示用∑的符号组成的所有有限序列的集合。 如L为∑*的子集，即 L （ ∑* 则L称为∑上的一个语言， ∑称为字汇表。 映射e将问题Π每一实例映射为字符串。 e所使用的字符集合为∑，则Π及e将∑*划分为三个子集： ·不代表任何实例的串集合 ·相应实例的解为“否”的串集合 ·相应实例的解为“是”的串集合 将第三个子集表示为语言 L(Π ,e)＝{x∈ ∑*|存在I ∈ Y∏ , x=e(I)} 解为“是”的实例映射得到的串的集合 我们假设每一问题都有各自的关于实例大小的度量方法， 即每一个问题Π有映射 DΠ → Z十 其中Z十为正整数集合。 * *