人工智能中的约束满足问题

我们已经遇到了包括对抗搜索和即时搜索在内的各种方法来解决各种问题。解决问题的每种方法都有一个共同的目的：找到一个能够实现目标的解决方案。然而，在对抗搜索和局部搜索中，对机器人解决问题和得出答案的能力并没有限制。

本节将探讨约束优化方法，这是另一种真正的问题解决方式。顾名思义，约束满足意味着必须在遵守一组约束或规则的情况下解决问题。

当一个问题的变量遵循严格的规则条件时，就说它已经通过解决多目标问题的方法得到了解决。哇，这种方法能够深入研究问题本身的复杂性和组织性。

有三个因素会影响约束满足，特别是在

• 它指的是一组参数，或 X。
• D：变量包含在一个集合中。每个变量都有一个不同的域。
• C：这是一组参数集合必须遵守的约束。

在约束满足中，域是参数所在的位置，以及特定于任务的约束。这三个组成部分构成了约束满足技术的整体。一对“域，关系”构成了约束的数量。域是构成约束的变量的元组，而关系包含参数必须满足约束的可能解决方案列表。

包含数量已解决的问题

对于约束满足问题 (CSP)，必须满足以下条件：

• 状态空间
• 解决问题的基本思想。

状态空间中的状态定义是通过为所有参数赋值来完成的，例如

X1 = v1, X2 = v2, etc.

有三种方法可以为参数经济地赋值：

1. 一致或合法的赋值：如果一个任务遵守所有法律法规，则称为一致或合法的任务。
2. 完整赋值：一个任务中，每个变量都有一个与之关联的数字，并且 CSP 解是连续的。这样的任务被称为完整任务。
3. 部分赋值是只为部分变量赋值的赋值。此类任务被称为不完整赋值。

CSP 中的域类别

参数使用以下两种类型的域之一：

• 离散域：这个无限的区域允许存在许多变量的单个状态。例如，每个参数都可以接收无限数量的初始状态。
• 这是一个具有连续阶段的有限域，可以为单个特定变量描述一个区域。另一个名称是常数区域。

CSP 中的约束类型

基本上，根据参数，有三种不同的约束类别：

• 单元约束是最简单的约束，因为它们只限制一个变量的值。
• 二元约束：这些约束连接两个参数。一个名为 x2 的变量的值可以在 x1 和 x3 之间找到。
• 全局约束：这种约束包含无限制数量的变量。

主要类型的约束使用特定类型的分辨率方法来解决：

• 在线性规划中，当每个取整数值的参数仅出现在线性方程中时，经常使用线性约束。
• 非线性约束：在非线性规划中，当每个变量（整数值）以非线性形式出现时，使用几种不同类型的约束。

注意：偏好约束是现实世界中存在的独特约束。

想象一个数独谜题，其中一些方格已经填入了特定的数字。

您必须用 1 到 9 之间的数字填充空白方格，并确保任何行、列或块中都没有重复的数字。这个多目标问题相当基本。必须在考虑特定限制的情况下解决问题。

可以填充其他空间的整数范围（1-9）被称为域，而空白空间本身被称为变量。变量的值首先从域中提取。约束是决定变量如何选择域的规则。