一种基于与或树的有限约束问题推理方法

摘要

本发明提供一种基于与或树的有限约束问题推理方法，包括以下步骤：对原问题P进行分解操作，将原问题P分解成n个相互等价的子问题；根据约束条件集，实时调整对子问题的推理求解顺序，从而得到每个子问题的解，最终输出得到的问题序列P和方法序列C。可高效快速的对有限约束问题进行推理求解。

说明书

技术领域

本发明涉及一种有限约束问题推理方法，具体涉及一种基于与或树的有限 约束问题推理方法。

背景技术

约束问题中约束的含义，顾名思义，是对事物的限制。事实上，逻辑程序 设计(Logicprogramming)在实质上就是一种特殊的约束求解问题。约束问题 可以简单理解成逻辑推理时的附加条件，也可以说是得出某些结果时所必须考 虑的限制条件。对待这类问题的求解的研究初始于上个世纪70年代的Scene Labeling以及60年代的InteractiveGraphics。它允许用户在计算机中绘制和处理图 形，从而发展了局部推演(Localpropagation)等关键技术。现今在计算机领域 中，约束问题包括诸如布尔约束问题、有限约束问题和数值约束问题等等。其 中，有限约束问题最为常见。

随着人工智能技术的兴起，用计算机进行逻辑推理的技术也日益成熟。就 计算机的推理方法而言，常见的方法有以下几个：基于OWA(orderedweighted aggregation)算子核心思想的目标可满足性推理方法，这种方法避免了纯逻辑推 理中“与”、“或”的过于“偏执”的推理结果，较好地反映出了人类一般思维 的特点。基于模糊Petri网的并行推理方法，这种是把模糊Petri网模型转化为了矩 阵形式，在此基础上提出了一种并行推理算法。该算法是对传统使用Petri网模型 的算法进行了改进，提高了算法的推理效率，尤其适合较大的复杂的模糊Petri 网模型。还有基于模糊决策树的推理方法，该方法被用于网络取证，在做证据 分析和推理时，其正确分类率可达到91.16％。

然而，上述所公开的各类推理方法都有较强的针对性，并不适用于对有限 约束问题进行求解，因此，如何对有限约束问题进行高效快速的推理求解，具 有重要意义，现有技术中，尚未出现有效的解决方案。

发明内容

针对现有技术存在的缺陷，本发明提供一种基于与或树的有限约束问题推 理方法，可有效解决上述问题。

本发明采用的技术方案如下：

本发明提供一种基于与或树的有限约束问题推理方法，包括以下步骤：

步骤1，对于一个具有有限约束的原问题P，对原问题P进行分解操作，将原 问题P分解成n个相互等价的子问题，将各个子问题依次记为子问题P1、子问题 P2…子问题Pn；其中，n为自然数；

步骤2，对于任意一个子问题Pi，i∈(1、2…n)，对子问题Pi进行独立的求 解，得到子问题Pi的m个解，将子问题Pi的m个解分别记为：Ci1、Ci2…Cim；其 中，m为自然数，对于不同的子问题Pi，其具有的解个数m的值相同或不相同；

步骤3，将原问题P作为根节点；将各个子问题Pi作为原问题P的儿子节点； 将子问题Pi的m个解作为子问题Pi的儿子节点，由此建立得到一棵层数为3的与 或树；

步骤4，建立约束关系集；所述约束关系集用于存储子问题Pi与其他子问题 的解之间的约束关系；

步骤5，采用以下方法对问题进行推理求解：

步骤5.1，建立问题序列P＝[]和方法序列C＝[]；初始时，问题序列P＝[]和方法 序列C＝[]均为空；

步骤5.2，令i＝1；

步骤5.3，遍历第i个子问题Pi，并将Pi存入P，即P＝[Pi]；

步骤5.4，令j＝1；

步骤5.5，遍历子问题Pi的第j个解Cij，并将Cij存入C，即C＝[Cij]；

通过对所述约束关系集进行分析，判断所述约束关系集中是否存在对解Cij 的约束条件；如果不存在，则执行步骤5.6；如果存在，则查找到解Cij的约束条 件，并获得约束解Cij的至少一个子问题Pk；其中，k≠i；然后，判断在当前的与 或树中是否存在子问题Pk，如果不存在，则执行步骤5.6；如果存在，则执行步 骤5.8；

步骤5.6，对与或树进行更新，删除与或树中的子问题Pi节点以及子问题Pi 节点的所有儿子节点；

步骤5.7，判断i是否等于n，如果不等于，则返回到步骤5.3；如果等于，则 转到步骤6；

步骤5.8，将Cij从方法序列C中删除；

步骤5.9，判断j是否为子问题Pi具有的儿子节点的总数，如果不是，则令 j＝j+1，返回到步骤5.5；如果是，则执行步骤5.10；

步骤5.10，通过对所述约束关系集进行分析，得到解Cij的约束条件，并获 得约束解Cij的存在于当前与或树中的所有的子问题Pk；其中，k≠i；然后，执行 步骤5.11；

步骤5.11，将Pi从问题序列P中删除；

对于每个子问题Pk，分别按照步骤5.2-步骤5.10的方法，对每个子问题Pk依 次进行求解，在求解得到所有子问题Pk的解后，子问题Pk以及其所有的儿子节 点必然已不存在于当前的与或树中，因此，此时的与或树中不存在约束解Cij的 子问题Pk，则解Cij即为问题Pi的解，将Cij存入方法序列C；将Pi存入问题序列P； 然后转回步骤5.6；

步骤6，输出得到的问题序列P和方法序列C。

本发明提供的基于与或树的有限约束问题推理方法具有以下优点：

可高效快速的对有限约束问题进行推理求解。

附图说明

图1为本发明提供的一种与或树的具体示意图；

图2为在得到子问题P1的解后更新得到的与或树的具体示意图。

具体实施方式

为了使本发明所解决的技术问题、技术方案及有益效果更加清楚明白，以 下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述 的具体实施例仅用以解释本发明，并不用于限定本发明。

为方便对本发明进行理解，首先介绍本发明的大致思路和原理：

对于一个有限约束的原问题P的推理，首先对原问题P进行分解操作，将 原问题P分解成若干个相互等价的子问题Pi。之后再分别求解各个子问题Pi， 并将子问题Pi的解进行集合处理，即得到原问题P的解。这种采用缩小问题规 模策略的对原问题P的分解，其依据是：当子问题的规模足够小时，子问题的 解决难度就会大大降低。因此，通过采用上述方法，即分解原问题，缩小原问 题的规模的方法，加快了求解的速度。

进一步的，对于每个子问题Pi来讲，各自可用的解决方法通常并不是唯一 的。也就是说，任一个子问题Pi可能对应一个或者多个解决方法，至于具体哪 一个解决方法是可用的，是可以解决这个子问题Pi的，就要看针对这个解决方 法的具体的约束条件是如何限制的。不过，这些约束条件并不会影响以下结论： 每一个子问题的下属的所有解决方法之间存在着“或”的关系。换言之，对子 问题Pi来说，只要得到一个可用的解决方法，该解决方法即可作为子问题Pi的 最终解。

为方便对本发明进行理解，介绍一个简单的本发明的应用场景：

假设存在病人A，其具有口腔疾病，即：具有两棵相邻的坏牙，分别为牙 齿A和牙齿B。其中，牙齿A损害程度较高，可采用的治疗方案包括拨除牙齿 A和种植牙齿A。牙齿B存在的问题为牙齿松动，采用的治疗方案为通过治疗 牙周病而治疗牙齿B的牙齿松动问题。

对于上例，可建立图1所示的与或树，其为一个三层的与或树，P为原问题， 即：治疗病人A的口腔问题。P1代表治疗牙齿A的子问题；P2代表治疗牙齿B 的子问题。C11代表拨除牙齿A的治疗方法；C12代表种植牙齿A的治疗方法； C21代表治疗牙齿B的牙周病的治疗方法。

此外，约束条件集为：C11和P2之间存在约束：当P2子问题未解决时， 不允许采用C11方法。也就是说，当牙齿B松动情况下，不允许对相邻的牙齿 A进行拔除治疗方法。

对于图1示出的与或树，推理求解方法为：

步骤1.1，建立问题序列P＝[]和方法序列C＝[]；初始时，问题序列P＝[]和方法 序列C＝[]均为空；

步骤1.2，遍历第1个子问题P1，并将P1存入P，即P＝[P1]；

步骤1.3，遍历子问题P1的第1个解C11，并将C11存入C，即C＝[C11]；判断 约束关系集中是否存在对解C11的约束条件，此时，存在约束条件；然后，查找 到解C11的约束条件，并获得约束解C11的子问题P2；又进一步查找与或树，证 明当前的与或树中存在子问题P2，表明子问题P2尚未解决；此时，将C11从方法 序列C中删除；

步骤1.4，然后，按同样的方法遍历子问题P1的第2个解C12，并将C12存入C， 即C＝[C12]；判断约束关系集中是否存在对解C12的约束条件，此时，在本例中， 由于不存在对解C12的约束条件，因此，已求解得到对子问题P1的解为C12；

步骤1.5，将子问题P1和其所有儿子节点从与或树中删除，得到图2所示的树 形结构。

步骤2.1，然后，遍历第2个子问题P2，并将P2存入P，即P＝[P1、P2]；

步骤2.2，遍历子问题P2的第1个解C21，并将C21存入C，即C＝[C12、C21]； 判断约束关系集中是否存在对解C21的约束条件，此时，在本例中，由于不存在 对解C21的约束条件，因此，已求解得到对子问题P2的解为C21。

步骤3，输出问题序列P＝[P1、P2]，方法序列C＝[C12、C21]。

意义为：首先采用C12方法解决P1问题，然后再采用C21方法解决P2问题。

基于上述原理，以下介绍本发明的技术方案，本发明提供一种基于与或树 的有限约束问题推理方法，包括以下步骤：

步骤1，对于一个具有有限约束的原问题P，对原问题P进行分解操作，将原 问题P分解成n个相互等价的子问题，将各个子问题依次记为子问题P1、子问题 P2…子问题Pn；其中，n为自然数；

步骤2，对于任意一个子问题Pi，i∈(1、2…n)，对子问题Pi进行独立的求 解，得到子问题Pi的m个解，将子问题Pi的m个解分别记为：Ci1、Ci2…Cim；其 中，m为自然数，对于不同的子问题Pi，其具有的解个数m的值相同或不相同；

步骤3，将原问题P作为根节点；将各个子问题Pi作为原问题P的儿子节点； 将子问题Pi的m个解作为子问题Pi的儿子节点，由此建立得到一棵层数为3的与 或树；

步骤4，建立约束关系集；所述约束关系集用于存储子问题Pi与其他子问题 的解之间的约束关系；

步骤5，采用以下方法对问题进行求解：

步骤5.1，建立问题序列P＝[]和方法序列C＝[]；初始时，问题序列P＝[]和方法 序列C＝[]均为空；

步骤5.2，令i＝1；

步骤5.3，遍历第i个子问题Pi，并将Pi存入P，即P＝[Pi]；

步骤5.4，令j＝1；

步骤5.5，遍历子问题Pi的第j个解Cij，并将Cij存入C，即C＝[Cij]；

通过对所述约束关系集进行分析，判断所述约束关系集中是否存在对解Cij 的约束条件；如果不存在，则执行步骤5.6；如果存在，则查找到解Cij的约束条 件，并获得约束解Cij的至少一个子问题Pk；其中，k≠i；然后，判断在当前的与 或树中是否存在子问题Pk，如果不存在，则执行步骤5.6；如果存在，则执行步 骤5.8；

步骤5.6，对与或树进行更新，删除与或树中的子问题Pi节点以及子问题Pi 节点的所有儿子节点；

步骤5.7，判断i是否等于n，如果不等于，则返回到步骤5.3；如果等于，则 转到步骤6；

步骤5.8，将Cij从方法序列C中删除；

步骤5.9，判断j是否为子问题Pi具有的儿子节点的总数，如果不是，则令 j＝j+1，返回到步骤5.5；如果是，则执行步骤5.10；

步骤5.10，通过对所述约束关系集进行分析，得到解Cij的约束条件，并获 得约束解Cij的存在于当前与或树中的所有的子问题Pk；其中，k≠i；然后，执行 步骤5.11；

步骤5.11，将Pi从问题序列P中删除；

对于每个子问题Pk，分别按照步骤5.2-步骤5.10的方法，对每个子问题Pk依 次进行求解，在求解得到所有子问题Pk的解后，子问题Pk以及其所有的儿子节 点必然已不存在于当前的与或树中，因此，此时的与或树中不存在约束解Cij的 子问题Pk，则解Cij即为问题Pi的解，将Cij存入方法序列C；将Pi存入问题序列P； 然后转回步骤5.6；

步骤6，输出得到的问题序列P和方法序列C。

本发明提供的上述方法的求解思路为：

步骤5.1，首先遍历子问题P1，并将P1存入P，即P＝[P1]；

步骤5.2，然后遍历子问题P1的解C11，并将C11存入C，即C＝[C11]；

然后，对约束关系集进行分析，判断约束关系集中是否存在对解C11的约 束条件，如果不存在，则直接得到解C11为子问题P1的最终解，不再进一步遍历 子问题P1的其它解，同时，把子问题P1和其所有儿子节点从与或树中删除，也 就是说，本发明方案中，只要一个子问题求解成功后，需要立即将该子问题及 其所有解从与或树中删除，这一点非常重要。然后按同样的方法对另一个子问 题进行遍历求解，直到得到所有子问题的解，结束。

但是，如果约束关系集中存在对解C11的约束条件时，此时要区分两种情况， 一种情况为对C11的约束问题已被解决了，即：已不存在于当前的与或树中，那 么，此时的这个约束问题实际上已不存在，因此，可以等效为不存在对解C11的 约束条件，即：解C11为子问题P1的最终解。而如果约束关系集中存在对解C11 的约束条件时，本发明采用的方法为：先暂时舍弃解C11，即：将解C11从方法 序列中删除，C＝[]；然后，遍历子问题P1的其他解，只要遍历得到一个不存在 约束条件的解时，便将遍历到的解作为子问题P1的最终解。然后遍历其他子问 题。而如果子问题P1的所有解均遍历后，发现所有解均存在有效的约束条件， 此时表明必须要调整子问题的解决顺序，才能使子问题P1有解。因此，本发明 中，对于遍历到的子问题P1的最后一个解，假设为C15，存在以下约束：当存在 子问题P3时，C15不可用。此时，需要置P＝[]、C＝[]；然后，转而遍历子问题P3， 将P3存入P，即：P＝[P3]；然后，遍历子问题P3的解C31，将C31存入C，即C＝[C31]， 采用上述约束条件判别方法，假设此时C31不存在约束，则C31即为子问题P3的 最终解，此时：P＝[P3]、C＝[C31]。同样，与或树中删除子问题C3及其所有儿 子节点。

然后，再转回遍历子问题P1，将P1存入P，即P＝[P3、P1]；再继续对子问题 P1的最后一个解进行遍历，即对C15进行遍历，此时，虽然约束关系集中存在以 下约束内容：当存在子问题P3时，C15不可用。但通过查找与或树可以发现，已 不存在子问题P3，因此，这相当于一个无效的约束条件了，因此，此时C15即作 为子问题P1的最终解，由此得到：P＝[P3、P1]、C＝[C31、C15]。

然后，再对子问题P2进行遍历，原理一致，在此不再赘述。

当与或树的结构变得复杂时，推理的过程也会增加，但基本的逻辑思路是 不变的。采用上述方法，就可以得到一个可以解决所有子问题的解决方案序列。 事实上，该方法已经应用于《牙列缺损诊疗决策专家系统》当中，并取得了一 定的效果。同样，该方法可以拓展应用于面向有限约束问题的专家系统中。对 于系统知识库建立、推理规则的定义有一定的参考价值。

本发明提供的基于与或树的有限约束问题推理方法，对于有限约束问题的 求解提供了一种新的思路，即：对原问题P进行分解操作，将原问题P分解成n个 相互等价的子问题：根据约束条件集，实时调整对子问题的推理求解顺序，从 而得到每个子问题的解，最终输出得到的问题序列P和方法序列C。本发明可以 用于专家系统方向。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通 技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰， 这些改进和润饰也应视本发明的保护范围。