问题求解（三） Open Topic 9 笔记

Posted on 2023-10-28 In Course Note , Problem Solving

OT：请调研教材中未介绍过的至少2种判定问题和2种优化问题（不能是相互对应版本，也不能是教材中介绍过的问题的对应版本），讨论适用场景，用教材中的方法形式化描述问题。

Slide

字符集编码和问题的形式化描述

字符集 $\Sigma$ 的编码能力

引入

字符集 $\Sigma_{bool}$，$\Sigma_{latin}$，$\lbrace 0, 1, \#\rbrace$ 等有什么本质不同？

e.g. 使用 $\lbrace 0, 1, \#\rbrace$ 表达带权图？使用 $\lbrace 0, 1\rbrace$ 表达带权图？

字符集 $\Sigma$ 的编码能力只和其元素个数 $|\Sigma|$ 有关，和其种类无关(因为存在双射)。

（e.g. $\lbrace 0, 1\rbrace$ 和 $\lbrace a, b\rbrace$）
所有基数大于等于 $2$(有限)的字符集 $\Sigma=\lbrace x_0, x_1, \cdots, x_{|\Sigma|}\rbrace$ 的编码能力相同（编码长度仅差距多项式倍），都和 $\Sigma_{bool}$ 等价。

若 $w\in \Sigma_{bool}^*$，可以使用 $\lbrace x_0, x_1\rbrace$ 在 $\Sigma$ 上表达 $w$。
若 $w\in \Sigma^*$，将 $\Sigma$ 中的字符用 $\Sigma_{bool}$ 赋予 $0/1$ 上的唯一编码后即可在 $\Sigma_{bool}$ 上表达 $w$。

如何赋予唯一编码？

($0/1$ 上的唯一编码) 给定 $\Sigma=\lbrace x_0, x_1, \cdots, x_{|\Sigma|-1}\rbrace$，需要输出一个转化函数 $f: \Sigma\to \Sigma_{bool}^*$。约束为：根据 $f$ 可以确定性地构造函数 $g_f:\Sigma^*\to \Sigma_{bool}^*$ 为，若 $w=c_1c_2\cdots c_{|w|}, c_i\in \Sigma$，则 $g_f(w)=f(c_1)f(c_2)\cdots f(c_{|w|})$，要求 $g_f$ 是单射，且 $|g_f(w)|$ 是 $|w|$ 的 poly-bounded 倍。

形象化理解，需要给 $\Sigma$ 的每个字符用 $0/1$ 编码，并保证对任意 $\Sigma$ 上的词语，改为用 $0/1$ 表达后不会发生误读。

e.g. $\lbrace 0, 1, \#\rbrace$ 上的字符串 $11\#01$ 代表了一个有向无权图。定义 $f(0)=00$，$f(1)=01$，$f(\#)=10$，原字符串改写为 $0101100001$，两位一读，不会发生误读。

满足条件的 $f$

从上例可知，一种最简单的编码：对于大小为 $n=|\Sigma|$ 的字符集 $\Sigma$，对每个 $x_i\in\Sigma$ 固定使用长度为 $\lceil \lg n\rceil$ 的 $\Sigma_{bool}$ 词 $w_i$ 表示（前补零），且 $Number(w_i)=i$。

更本质地，什么样的 $f$ 是合法的？

只需对任意 $x, y\in \Sigma$ 且 $x\ne y$，满足 $f(x)$ 不是 $f(y)$ 的前缀即可。（在 0/1 trie 树上不同时选择祖先-子孙对）。

思考题：若已知 $w\in \Sigma^*$，如何输出合适的 $f$，使得 $g_f(w)$ 尽量短？

由于字符集 $\Sigma$ 的选取对问题的本质无影响（但编码内容有影响），故以下问题只给出最易于表达的 $\Sigma$。

Some Decision Problems

有向无环图的判定问题

有向无环图的判定问题：给定图 $G$，判断其中是否不存在有向环。

形式化地，有向无环图的判定问题是 Decision Problem $(\text{isDAG}, \lbrace 0, 1, \# \rbrace)$，其中

\[ \text{isDAG} = \lbrace w\in \lbrace 0, 1, \#\rbrace^* | \text{$w$ 表示一个有向图且无环}\rbrace \]

有向(无权)图的表示可以为：对于 $n$ 阶图，设邻接矩阵为 $G=(a_{ij})_{n\times n}, a_{ij}\in \lbrace 0, 1\rbrace$，表示为

\[ w_{G}=a_{11}a_{12}\cdots a_{1n}\#a_{21}a_{22}\cdots a_{2n}\#\cdots\# a_{n1}a_{n2}\cdots a_{nn} \]

停机问题

停机问题：给定程序 $P$ 和输入集合 $S$，判断 $P$ 是否可以在以任意 $s\in S$ 作为输入的前提下在有限时间内结束。

如果把 $P$ 使用的字符集记为 $\Sigma_P$，即 $P\in \Sigma_P^*$，把 $P$ 的输入使用的字符集记为 $\Sigma_{in}$，即 $S\subseteq \Sigma_{in}^*$，且定义 $\perp$ 是在 $\Sigma_P\cup \Sigma_{in}$ 中未出现的一种字符。则

形式化地，停机问题是 Decision Problem $(\text{Halt}, \Sigma)$，其中

\[ \Sigma = \Sigma_{P}\cup\Sigma_{in}\cup\lbrace \perp\rbrace \]

且

\[ \text{Halt}=\lbrace w\in\Sigma^*| \text{$w$ 表示程序 $P$ 和 $S$，且满足对任意 $s\in S$ 作为输入 $P$ 可停机}\rbrace \]

$w$ 的编码方式可以为

\[ w=P\perp s_1\perp s_2\perp \cdots \perp s_{|S|}\perp\perp \]

其中 $P\in \Sigma_P^*$ 编码程序 $P$，$s_i\in \Sigma_{in}^*$ 编码 $P$ 的输入 $s_i$.

Some optimization problems

排序问题

排序问题：输入 $n$ 和序列 $\langle a_1, a_2, \cdots, a_n\rangle$，输出序列的一个重排 $\langle b_1, b_2, \cdots, b_n\rangle$ 且 $b_1\le b_2\le \cdots \le b_n$。

只需要求解可行解，在可行解之间没有优劣之分。

形式化地，排序问题定义为:

Input: 正整数 $n\ge 1$ 和正整数序列 $a_1, a_2, \cdots, a_n$.
Constraints: 对任意输入实例 $(n, a_1, a_2, \cdots, a_n)$，$\mathcal M(n, a_1, a_2, \cdots, a_n)=(b_1, b_2,\cdots, b_n)$，满足多重集 $\lbrace a_1, a_2, \cdots, a_n\rbrace=\lbrace b_1, b_2, \cdots, b_n\rbrace$，且 $b_1\le b_2\le \cdots\le b_n$.
Costs: 对 $(b_1, b_2, \cdots, b_n)\in \mathcal M(n, a_1, a_2, \cdots, a_n)$，$cost((b_1, b_2, \cdots, b_n), (n, a_1, a_2, \cdots, a_n))=0$.
Goal: 最小化。

最小化唯一编码问题

(最小化唯一编码问题) 输入 $\Sigma=\lbrace x_0, x_1, \cdots, x_{|\Sigma|-1}\rbrace$ 和 $w\in \Sigma^*$，需要输出一个转化函数 $f: \Sigma\to \Sigma_{bool}^*$。约束为：根据 $f$ 可以确定性地构造函数 $g_f:\Sigma^*\to \Sigma_{bool}^*$ 为，若 $w'=c_1c_2\cdots c_{|w|}, c_i\in \Sigma$，则 $g_f(w')=f(c_1)f(c_2)\cdots f(c_{|w'|})$，要求 $g_f$ 是单射，且 $|g_f(w')|$ 是 $|w'|$ 的 poly-bounded 倍。最小化 $g_f(w)$.

形式化地，最小化唯一编码问题定义为：

Input: $\Sigma=\lbrace x_0, x_1, \cdots, x_{|\Sigma|-1}\rbrace$ 和 $w=c_1c_2\cdots c_{|w|}, c_i\in\Sigma$.
Constraints: 对任意输入实例 $(x_0, x_1, \cdots, x_{|\Sigma|-1}, w)$，$\mathcal M(x_0, x_1, \cdots, x_{|\Sigma|-1}, w)=(f(x_0), f(x_1), \cdots, f(x_{|\Sigma|-1}))$，满足上述约束。
Costs: 对 $(f(x_0), f(x_1), \cdots, f(x_{|\Sigma|-1}))\in\mathcal M(x_0, x_1, \cdots, x_{|\Sigma|-1}, w)$，$cost((f(x_0), f(x_1), \cdots, f(x_{|\Sigma|-1})),(x_0, x_1, \cdots, x_{|\Sigma|-1}, w))=\sum_{i=1}^{|w|}|f(c_i)|$.
Goal: 最小化。