1、“.....本文将介绍如何通过使用基于有序叉决策图的和简单的并行计算来对组合优化问题进行快速求解。我们将采用并行双向广度优先搜索算法来实现求解，通过数据结构来加快运算速度和减小空间占用。本文先以规模的棋盘为例讲解算法原理，最后使用多种规模。关键词组合优化布尔函数有序又决策图前言组合优化问题，是通过对数学方法的研究去寻找离散事件的最优编排分组次序或筛选等，是运筹学的个重要分支。所研究的问题涉及信息技术经济管理工业工程交通运输通信网络等领域。典型的组合优化问题有旅行商问题组合调度问题等。这类问题的描述都非常简单，并且具有很强的工程代表性，但最优化求解很困难基于二叉决策图的状态组合爆炸问题并行求解方法论文原稿用方框表示终节点，用圆圈表示其它节点，节点之间通过虚线或者实线连接。通常，假设连接弧的方向向下，边用虚线表示，卜边用实线表示......”。

2、“.....到，的布尔函数和定变量序，在表示布尔函数族的中，如果任有向路径上的变量均以变量序所规定的的次序依次出现，则称该为布尔函数的有序叉决策图。摘要布尔函数的可示布尔函数族的个有向无环图，它满足中节点分为根节点终节点和内部节点类。没有父辈节点或者没有输入弧的节点称为根节点没有后继子节点或者没有输出弧的节点称为终节点除根节点和终节点之外的节点或者具有输入和输出弧的节点称为内部节点终节点有个，分别标记为和。终节点具有属性∈，表示布尔常量和非终节点具有元组属性，其中，盘的状态集，而棋盘每步棋子的消耗造成了非同步状态集之间的差异，从而使得这样构建的叉决策图是绝对有序的，即天然是有序叉决策图。基于二叉决策图的状态组合爆炸问题并行求解方法论文原稿。有序叉决策图有序叉决策图是种基于符号的新型数据结构......”。

3、“.....是迄今为止布尔函数表述和操作中最为有效的技术之。根据描述，我们可以对该式中的变量逐次进行香农展开，并将其展开过程用如下图形的形式表示根节点表示布尔函数自身，从根节点引出两个分枝，分别表示经过个变量的第次香农展开后所得到的输入模式和下的布尔函数布尔函数可进步进行香农展开，并将它们和各自所展开得到的分量和分量连接类似地，将每次展开所得到的布尔函数再进行进步的香农展，还需要想出个合理的方式来安排下标，而且对于状态数太过庞大的问题，程序还会因为数组过大而过不了编译。本文使用的数据结构完美地解决了这个问题，无论是什么状态，只要能用来表示，就能在上直接判重。在具体实现上，我们利用多核的优势，使用双线程来实现双向并行搜索，以提高搜索效率。问题建模与表示必然得到分量和分量中的个或者两个同时取常值或。基于此......”。

4、“.....结合题目来谈，这里和，表示两个状态集之间的关系是可达还是不可达的。也就是说寻找路径问题可以归结为寻找布尔表达式问题，布尔表达式又可以对应个或多个叉决策图，这样，问题就转变成了叉决策图的构建问题。由于所求叉决策图的每个节点对应于棋盘的状表示中，通常用方框表示终节点，用圆圈表示其它节点，节点之间通过虚线或者实线连接。通常，假设连接弧的方向向下，边用虚线表示，卜边用实线表示。定义对于从，到，的布尔函数和定变量序，在表示布尔函数族的中，如果任有向路径上的变量均以变量序所规定的的次序依次出现，则称该为布尔函数的有序叉决策图。根据是用于表示布尔函数族的个有向无环图，它满足中节点分为根节点终节点和内部节点类......”。

5、“.....分别标记为和。终节点具有属性∈，表示布尔常量和非终节点具有元组基于二叉决策图的状态组合爆炸问题并行求解方法论文原稿显然的，上述棋盘的每种状态都可以被描述个变量。存在个从，到，的布尔表达式，其中每个变量代表棋盘的个状态集。当经历合适的状态集，即个变量被的激活时，的值为真，而这个变量对应的状态集中包含着我们要找的路径。基于二叉决策图的状态组合爆炸问题并行求解方法论文原稿。述个变量。存在个从，到，的布尔表达式，其中每个变量代表棋盘的个状态集。当经历合适的状态集，即个变量被的激活时，的值为真，而这个变量对应的状态集中包含着我们要找的路径。判重广度优先搜索的判重般通过个标记数组来实现，必须用过哈希或者全排列的方式才能将状态与数组下标对应......”。

6、“.....古天龙提出的有序叉决策图，种基于叉决策树的新型数据结构，则是该方面问题很有效的解决方案。本文将介绍如何通过使用基于有序叉决策图的和简单的并行计算来对组合优化问题进行快速求解。有序叉决策图有序叉决策图是种基于符号的新型数据结构，是布尔函数的种有效图形数学描述技术，是迄今为止布尔函数表述和操作中最为有态集，而棋盘每步棋子的消耗造成了非同步状态集之间的差异，从而使得这样构建的叉决策图是绝对有序的，即天然是有序叉决策图。基于二叉决策图的状态组合爆炸问题并行求解方法论文原稿。在具体实现上，我们利用多核的优势，使用双线程来实现双向并行搜索，以提高搜索效率。问题建模与表示显然的，上述棋盘的每种状态都可以被描描述，我们可以对该式中的变量逐次进行香农展开，并将其展开过程用如下图形的形式表示根节点表示布尔函数自身，从根节点引出两个分枝......”。

7、“.....并将它们和各自所展开得到的分量和分量连接类似地，将每次展开所得到的布尔函数再进行进步的香农展开，性，其中，表示节点所对应的布尔函数，∈表示节点的标记变量表示时，节点的分枝子节点表示时，节点的分枝子节点每个非终节点均具有两条输出分枝弧，将它们和各自的两个分枝子节点连接在起。节点和的连接弧称为边，节点和的连接弧称为边的任有向路径上，布尔函数中的每个变量至多出现次。在图效的技术之。的本质是种对布尔函数的有序压缩表达方式，可以高效地实现相应函数的运算功能，从而达到仅仅使用少许的数据结构就能表示和处理大规模复杂的数据集的目的。因此在组合优化问题的研究领域中，在保证获得精准结果的情况下能很好地实现时间与空间上的优化......”。

8、“.....到，的布尔函数，基于二叉决策图的状态组合爆炸问题并行求解方法论文原稿性，但最优化求解很困难，其主要原因是求解这些问题的算法需要极长的运行时间和极大的储存空间，即所谓的组合爆炸。然而随着电子技术的快速发展，计算机的内存空间越来越大，充分利用内存空间计算组合爆炸问题来减少时间上的消耗，是种有效的解决方案，那么广度优先搜索正是最广泛的选择。而最核心的问题，是如何组织和储存状态数据，还有测试。摘要布尔函数的可满足性和等价性等问题的完备性所导致的状态组合爆炸问题严重地限制了大规模甚至工业小规模问题的解决。然而在实际问题的处理中，对布尔函数采取恰当的描述并建立相应描述下的操作算法，可以有效地减缓甚至避免问题处理过程中的状态组合复杂性。而本文就是利用了来建立布尔函数模型并求解实际问题......”。

9、“.....即所谓的组合爆炸。然而随着电子技术的快速发展，计算机的内存空间越来越大，充分利用内存空间计算组合爆炸问题来减少时间上的消耗，是种有效的解决方案，那么广度优先搜索正是最广泛的选择。而最核心的问题，是如何组织和储存状态数据，还有重复状态的判定。古天龙提满足性和等价性等问题的完备性所导致的状态组合爆炸问题严重地限制了大规模甚至工业小规模问题的解决。然而在实际问题的处理中，对布尔函数采取恰当的描述并建立相应描述下的操作算法，可以有效地减缓甚至避免问题处理过程中的状态组合复杂性。而本文就是利用了来建立布尔函数模型并求解实际问题，结果在效率上较传统方法有很大提升表示节点所对应的布尔函数，∈表示节点的标记变量表示时，节点的分枝子节点表示时，节点的分枝子节点每个非终节点均具有两条输出分枝弧......”。