XiaoMi-AI文件搜索系统
World File Search Systemsfia
成本最优规划作为可满足性
简介 命题可满足性 (SAT) 或其他约束形式主义的编译已成为解决不同规划和模型检查变体的成功方法（Kautz 和 Selman 1992；Biere 等人 1999）。大多数此类基于编译的技术通过向约束求解器（例如 SAT 求解器）提交多个查询来工作，并且每个查询都对问题进行编码“是否存在最多有 h 个步骤的见证转换序列？”，其中 h 是某个自然数，通常称为地平线。对多个增加的 h 值重复此操作。为了使这些方法完整，h 必须有一个上限，通常称为完整性阈值，如果没有更短的上限，则不会找到任何见证人。此外，界限越严格，这些基于编译的程序就越有效。先前的研究已经将状态空间的不同拓扑属性确定为不同变体模型检查和规划问题的完备性阈值。例如，对于安全属性的有界模型检查，Biere 等人将直径（状态空间中最长最短路径的长度）确定为完备性阈值。直径也是基于 SAT 的满意规划的完备性阈值。Biere 等人还将递归直径（状态空间中最长简单路径的长度）确定为活性属性有界模型检查的完备性阈值。Edmund Clarke（Clarke、Emerson 和 Sifakis 2009）在其 Turing 中将识别和计算完备性阈值视为模型检查的一个活跃研究领域
在经典和量子计算平台上估计布尔可满足性问题的状态密度
给定一个合取范式 (CNF) 中的布尔公式 φ (x)，状态密度计算对于所有 e 值，恰好违反 e 个子句的变量分配的数量。因此，状态密度是所有可能分配中未满足子句数量的直方图。这种计算概括了最大可满足性 (MAX-SAT) 和模型计数问题，不仅可以洞察整个解空间，还可以衡量问题实例的难度。因此，在现实世界中，即使使用最先进的算法，这个问题通常也是不可行的。虽然找到这个问题的确切答案是一项计算密集型任务，但我们提出了一种基于测度不等式集中度来估计状态密度的新方法。该方法产生了二次无约束二进制优化 (QUBO)，这特别适用于基于量子退火的解决方案。我们介绍了总体方法，并将 D-Wave 量子退火器的结果与最著名的经典算法（如 Hamze-de Freitas-Selby (HFS) 算法和可满足性模理论 (SMT) 求解器）进行了比较。