量化最优答案集的研究

作者

引言：扩展回答集编程的边界

在过去的几十年里，回答集编程（ASP）作为一种强大的逻辑编程范式，已经被广泛应用于解决各种搜索和优化问题。尽管ASP在解决多种实际问题方面表现出色，但其原始形式的表达能力仍然受到限制，特别是在处理更高复杂度的问题时。随着对复杂问题需求的增加，研究者们提出了ASP的扩展版本，尤其是加入量化的版本——带量化的回答集编程（ASP(Q)）。然而，尽管这一扩展能够自然地表示多项式层次中的问题，但在处理需要多次调用Σp_n类的oracle（即Δp_{n+1}类问题）时，仍显得力不从心。

本篇文章将介绍一种新的ASP(Q)扩展形式，称为ASPω(Q)，该形式允许在量化的子程序中使用弱约束。这种弱约束使得在量化子程序内部可以表达局部优化，同时也能为全局优化标准建模。通过多个应用场景的实例，我们将展示这一新形式的建模能力及其计算性质。

理论基础：回答集编程

ASP的基本语法

在ASP中，程序由一组规则构成，每条规则的形式为：

$$ h \leftarrow b_1, \ldots, b_k, \sim b_{k+1}, \ldots, \sim b_m $$

其中，$h$为规则的头，$b_i$为规则的身体，$\sim$表示否定。除了标准规则外，ASP中还引入了弱约束的概念，其形式为：

$$ \leftarrow_w b_1, \ldots, b_k, \sim b_{k+1}, \ldots, \sim b_m [w@l, T] $$

这种弱约束被引入以便对答案集进行偏好排序，提供了一种在答案集之间进行比较的方法。

ASP(Q)的引入

ASP(Q)的引入为逻辑编程提供了一个自然的声明式手段，能够涵盖整个多项式层次中的问题。这种形式使得我们可以通过引入量化符号来扩展ASP的表达能力，例如，通过存在量化符号$\exists$和全称量化符号$\forall$来描述更加复杂的问题。

ASPω(Q)的提出

弱约束的双重功能

在ASPω(Q)中，弱约束的引入具有双重功能：一方面，它可以表达量化子程序内部的局部优化；另一方面，它也可以用于全局优化标准的建模。这一特性大大增强了语言的建模效率，使得ASP能够更有效地应对复杂的优化问题。

在此，我们将通过几个具体的案例来展示ASPω(Q)的建模能力和计算特性。

案例分析：最小最大团问题

最小最大团问题是一个著名的优化问题，涉及到在给定图中找到最小的最大团。我们可以通过以下程序来建模该问题：

P1 =
{
    v(i, j, a) ← ∀i ∈ I, j ∈ J, a ∈ A_{i,j}
    inI(i) ← ∀i ∈ I
    inJ(j) ← ∀j ∈ J
    e(x, y) ← ∀(x, y) ∈ E
    {f(i, j) : inJ(j)} = 1 ← inI(i)
    {valK(1); ...; valK(|V|)} = 1
}

在上述程序中，$P1$负责建模图的节点和边，$P2$则计算最大团的大小。通过使用弱约束，我们可以确保选出的团的大小尽可能小。

复杂性分析

在对ASPω(Q)程序的复杂性进行分析时，我们发现其一致性问题的复杂度在于：存在量化程序的复杂度为$\Sigma^P_{n+1}$，而全称量化程序的复杂度则为$\Pi^P_{n+1}$。这一发现提供了对ASPω(Q)的深刻理解，使我们能够在实际应用中进行合理的复杂性预期。

结论

本文提出的ASPω(Q)为回答集编程提供了新的扩展，能够有效地处理复杂的优化问题。通过引入弱约束，我们不仅增强了语言的表达能力，还开辟了新的研究方向。未来的工作将集中在进一步加强复杂性的界限、扩展ASPω(Q)以支持子集最小性以及基于ASPω(Q)的复杂性感知实现等方面。

参考文献

  1. Amendola, R., Fandinno, J., & Ricca, F. (2019). Answer Set Programming with Quantifiers.
  2. Brewka, G., Eiter, T., & McGuinness, D. L. (2011). Knowledge Representation.
  3. Buccafurri, F., & Faber, W. (2000). Weak Constraints in Logic Programming.
  4. Schaefer, M., & Umans, C. (2002). Completeness in the Polynomial-Time Hierarchy.
  5. Wagner, K. W. (1990). Bounded Query Classes.

发表评论