CSP过滤
• CSP
CSP过滤 1. 相关概念 在约束满足问题中，过滤（Filtering） 是通过约束传播来缩小变量域的技术。过滤的核心思想是在搜索过程中主动推理，提前发现和消除不可能的赋值，从而显著减少搜索空间。 过滤不同于盲目的回溯搜索，它利用约束的结构信息进行局部推理，在赋值之前就排除明显不可行的选择，避免了大量无意义的搜索尝试。...
All Posts
Total words: 556401
CSP算法
• CSP
> 下面是对CSP的相关概念的接口预实现，之后会用到 ``python class CSP: """Constraint Satisfaction Problem class""" def __init__(self, variables: List[str], domains:...
约束满足问题
• CSP
约束满足问题 1. 约束满足问题概念 约束满足问题（Constraint Satisfaction Problem, CSP）是一类特殊的搜索问题，它提供了一种结构化的方式来表示和解决组合问题。与传统搜索问题不同，CSP关注的是找到变量赋值的组合，使之满足所有约束条件，而不是寻找从起始状态到目标状态的路径。...
本地搜索
• Search
本地搜索 1. 相关概念 $a.$本地搜索概念 在某些问题中，我们只关心找到目标状态而并不需要知道达到这个状态的优化路径，并不需要通过设计算法来让路径成本优化。局部搜索算法允许我们找到目标状态而无需优化到达那里的路径成本。 在局部搜索问题中，状态空间由“完整”解的集合组成。我们使用这些算法来尝试找到满足某些约束或优化某...
有信息搜索
• Search
有信息搜索 1. 有信息搜索概念 在无信息搜索中，我们会从起始点开始、展开当前边界的所有可能后继状态。但是这样的搜索效率很低，会导致进行很多没必要的搜索。如果我们了解了当前环境的信息、对当前的空间的搜索方向有一定概念，就可以显著提高性能、快速到达目标。 2. 启发式搜索...
无信息搜索
• Search
无信息搜索 1. 无信息搜索概念 $a.$边界（$frontier$） 边界是当前已发现，但是还未被拓展的节点的集合，是搜索的边界。 $b.$边界的拓展（$expand$） 在搜索过程中，我们会展开当前边界的所有可能的后继状态，并把它加入边界中。这相当于下一步Search的探索动作。然后当前的边界就会被丢弃。...
搜索概念
• Search
搜索概念 1. 状态空间大小 如果在一个给定的世界中有$n$个变量对象，它们可以分别取$x_1, x_2, \ldots, x_n$个不同的值，那么状态的总数就是$x_1 \cdot x_2 \cdot \ldots \cdot x_n$。 2. 状态空间图与搜索树 $a.$状态搜索图...