zhuye

通用问题的求解---约束满足

一、概述

在人工智能领域，很多问题都属于约束满足问题，即寻找满足一组约束的目标状态的问题。

在问题空间搜索解的单一过程就变成两个并行的搜索：一个工作于约束的问题空间，一个工作于原问题空间，但操作和启发函数应能顾及约束空间的当前状态。操作也分为两种：一种是约束问题空间的操作，作用于当前约束状态产生新的约束，称为约束操作；一促是原问题空间的操作，作用于当前问题状态产生满足当前约束时新的部分解。

二、约束满足过程

         约束满足过程的一般形式如下：

    （1）Untill 找到一个完整的解或所有路径均已失败　　do
    （2）         begin
    （3）        在搜索图中选择一个未扩展的结点。
        （4）    　如果约束集合出现矛盾，则当前路径失败。
        （5）　如果约束集合描述了一个完整的解，则搜索成功。
        （6）        如果既无矛盾又无完整的解，则应用问题空间的操作产生满足当
            前约束集合的新的部分解，并将这些部分解加入到搜索图中
        （7）                      end

这是一个非常粗略的过程描述，为了理解过程的工作，下面考察一个实例。

三、秘密算式问题

本章完下一章返回主页