二叉判定图最优化算法研究综述

对近年来二叉判定图 (BDD)最优化算法的成果和发展趋势进行了综述和讨论 ,重点介绍精确排序算法和动态启发式排序算法 .给出了BDD优化算法的改进建议 :用不完全枚举法的优势和随机过程动态规划策略改进BDD优化算法 .

BDD数据建模的路径规划算法

针对道路交通状态高动态性和不确定性的路径规划问题,提出一种基于BDD建模的启发式初始路径规划、增量重规划算法与A*搜索算法.首先利用基于BDD的启发式搜索进行全局规划,求解路网中车辆的最优路径集.基于BDD的启发式搜索利用BDD这一紧凑的数据结构来表示迁移状态空间,又通过启发信息进一步压缩搜索空间的大小;当路网信息发生变化时,按不同拥堵状况分类进行BDD迁移关系的修改,并进行增量重规划,重新获得当前状态至目标状态的最优路径集.仿真实验结果表明:基于BDD的启发式搜索和增量重规划,在求解路网信息动态不确定性下的车辆路径规划问题上具有高效性和实用性,避免了交通路网长时间陷入拥堵状态.