基于变量权重的约束满足问题启发式算法研究

发布时间：2021-10-26 02:09

　　约束满足问题是人工智能领域重要的研究方向之一,主要用于求解实际问题和学术问题。约束满足问题技术解决问题的主要思想是:首先将待求解问题抽象成一个约束网络模型,然后利用约束满足问题相关求解算法对得到的约束网络模型进行求解。目前求解约束满足问题的算法主要包括:回溯搜索算法、局部推理算法以及启发式算法等。基于回溯搜索的MAC算法是目前求解约束满足问题使用最广泛的搜索算法,其算法思想是采用回溯搜索策略,在选择变量进行实例化后,利用相容性算法对约束网络进行约束传播,删除变量论域中不满足相容性条件的值,从而压缩约束网络,减小搜索空间,简化求解过程。在使用MAC算法求解规模较大的约束满足问题时,不合理的变量实例化顺序,常常会导致搜索树的体积过于庞大,严重影响求解效率。然而在回溯搜索过程中,由于约束网络的状态经常发生改变,因此寻找一个最优的变量实例化顺序的难度非常大。为了解决这一问题,学者们提出了启发式的概念。在对变量进行实例化之前,使用启发式算法进行变量和值的选择,尽可能地缩减搜索树的规模。变量排序启发式算法的作用是根据启发式规则指导回溯搜索算法选择变量进行实例化,避免冗余搜索,提高求解效率。变量排序... 

【文章来源】：吉林大学吉林省 211工程院校 985工程院校 教育部直属院校

【文章页数】：47 页

【学位级别】：硕士

【部分图文】：

四皇后问题约束满足问题模型

foreach value a dom(x) doif seekSupport(c x a) thenremove a from dom(x)return nbElements |dom(x)|图 2.2 描述的是 4 皇后问题在实例化变量 w 后的约束网络图。图中，Q 表应的取值，X 表示从论域中删除掉的值。在未经过 GAC 算法过滤的左网络中共还有 12 个值，即在搜索树的下一层还有 12 条分支。而在经过过滤的右图中，剩余三个变量论域中的 10 个值，由于不满足 GAC 被删索树的下一层仅有 2 条分支，搜索空间被极大地压缩了。并且由于 dom全部被删除，可以直接判定 w 1 不是任何解的一部分，无需继续向下进因此，在回溯搜索算法中加入相容性技术，能够有效地过滤掉不存在于解分支，压缩搜索空间，提高求解效率。

三个部分：分支策略、传播算法以及回溯机制。其中，分支策略决进行实例化；传播算法用于过滤约束网络，压缩搜索空间；回溯机量实例化失败或约束传播失败后，搜索树应该如何回退的问题。算法是目前求解约束满足问题使用最广泛、最有效的回溯搜索算法二路分支策略，即搜索树中的每一个结点最多只有两个孩子结点， x a，如图 2.3 所示。在图 2.3 中，在搜索初始时，为变量 x 赋值 结点的左子树 x a。此时变量 x 实例化成功，继续选择变量 y 赋值左子树 y a。当在 y a 的子树上不能求出解时，搜索树回退到 x (y)中的值 a 删除，进入分支 x a 的右子树 y a，重新选择变量进执行上述过程直到搜索过程结束。MAC 算法中的回溯机制是按序回溯的策略（SBT），沿着搜索路径从下往上依次进行回溯。此出了 CBJ 和 DBT 等回溯机制。

【参考文献】：
期刊论文
[1]基于实例化次数的约束求解方法研究[J]. 李占山,张乾,张良.  计算机研究与发展. 2015(05)

硕士论文
[1]约束满足问题（CSP）的求解技术研究[D]. 郭劲松.吉林大学 2013



本文编号：3458616