摘要:在最小割理论基础上提出了最小割多路径(min-cut multi-path,简称MCMP)路由算法,为流量请求选取少量关键路径,并在这些路径间均衡流量,在获得方法易实现性的同时能够有效地控制网络瓶颈链路拥塞.通过实际流量数据在北美和欧洲骨干网络中的实验,对比常用的OSPF(open shortest path first)路由算法和模型中的多路径路由算法,MCMP 路由算法可降低拥塞链路负载分别达到41%和20%以上.

摘要:电路划分是VLSI 物理设计过程中的一个关键阶段.该问题本质上是一个NP 困难的组合优化问题.针对该问题,提出了一种带FM 策略的混合粒子群优化算法.引入遗传算法的两点交叉算子和随机两点交换变异算子,保证了粒子在位置更新后依然可行;为了提高算法的局部搜索能力,将具有较强局部搜索能力的FM 策略融入算法的位置更新;设计了种群多样性变异策略,提高了种群多样性,避免了易陷入局部最优的缺陷.对ISCAS89 标准测试电路的仿真实验结果表明,所构造的算法是有效的.

摘要:针对经典最小割算法计算量大和适应性不足的问题,提出一种改进的基于网络最小割计算稠密深度图的全局优化方法.首先,根据视差变化与不连续区域之间的关系,定义了具有一定适应性的平滑约束和遮挡约束,然后使用网络最小割算法,求解遮挡情况下的稠密视差.其次,在分析最小割算法复杂性的基础上,给出了一种受限α-扩展(α-expansion)操作,该操作根据灰度连通性和特征点匹配的结果对每次网络构造的顶点进行控制,减少网络中顶点和边的数目,可有效提高计算效率.实验结果显示,该算法在保证视差恢复准确性的前提下,能以较快的速度计算出较理想的稠密视差图.