SuperAPI AI 工具集

propagate-then-search

通用与其它

查看项目

更新于 10-15 23:32

技能介绍

用途:propagate-then-search 是一种面向约束满足问题(CSP)的求解模式。当给某个变量赋值会约束其他变量、且搜索空间可通过推理剪枝时适用,例如数独、排班、带规则的谜题。若约束之间相互独立、无法进行约束传播,或简单暴力搜索已足够快,则不适合使用。

主要能力:核心思路是交替进行“传播”和“搜索”。传播阶段:一旦赋值,就推断其全部后果,沿推理链消除不可能取值;搜索阶段:仅在传播无法继续时才做猜测。若传播过程中出现矛盾,立即返回失败,实现快速失败。

使用方式:先对初始状态执行 propagate;若返回空则说明矛盾,直接失败;若状态已完整则返回解;否则进入 search。搜索时采用 MRV(最少剩余取值)启发式,优先选择可选值最少的未赋值变量进行猜测,对每个候选值复制状态、赋值、再传播,并递归求解。资料给出的伪代码与数独示例展示了 solve、search、assign、eliminate 等函数结构,其中 eliminate 包含三条规则:某格无候选值则失败;某格仅剩一个候选值则从同组其他格中消除该值;某值在某单元中只剩一个可放位置则直接赋值。

关键原则:充分传播,在猜测前走完所有推理链;快速失败,立即检测矛盾;使用 MRV 启发式优先猜测选项最少的变量;猜测前复制状态,避免搜索过程中修改原状态;用 False/None 表示失败,以区别于空解。

限制:资料未提供该技能的安装命令、运行环境、依赖、性能数据或收费信息,暂未提供。上述内容为模式与示例说明,具体集成方式需参考来源页面。