基于随机游走的多目标A~*算法的改进

针对基于降维技术改进的多目标A~*(NAMOA*dr)算法中存在的高原搜索现象,结合蒙特卡罗随机游走策略提出了一种基于随机游走的多目标A~*(RWNAMOA~*dr)算法,其基本思想是当NAMOA~*dr算法陷入高原搜索时,利用随机游走策略及时找到一个出口(具有被上次扩展标签的启发值非支配的启发值的标签)逃离该高原搜索。针对NAMOA~*dr算法何时陷入高原搜索的问题,提出了一种检测高原搜索的方法,即当连续扩展m次标签的启发值都被上一次扩展的标签的启发值支配时则认为NAMOA~*dr算法陷入了高原搜索。使用多目标搜索算法的标准测试平台——随机网格进行了实验。实验结果表明RWNAMOA~*dr算法比NAMOA~*dr算法的运行时间平均减少了50.69%,占用的空间平均减少了约10%,能够为现实生活中加速多目标路径搜索提供理论支撑。

异构环境下的P2P流媒体节点选择算法

针对异构环境的复杂性和不稳定性,提出一种异构环境下的点对点(P2P)流媒体节点选择算法。利用模糊认知图理论研究异构环境下影响节点性能的多方面因素之间的关系,计算节点的综合服务能力,并选择服务能力强的节点作为邻居节点;为保证邻居节点具有较强的实时服务能力,利用马尔科夫蒙特卡洛方法进行随机行走,周期性地更新邻居节点列表,采用Metropolis-Hastings算法计算转移矩阵以满足随机行走的期望静止概率分布。研究结果表明:该算法能在选择优质邻居节点,提高视频服务质量的同时,保证节点的负载均衡,降低系统消耗,显著提高了系统性能。

基于局部随机游走的超像素分割方法

针对基于图论的超像素分割方法缺乏超像素紧凑性控制和运算复杂度过高的问题,提出了一种基于局部懒惰随机游走(LLRW)的超像素分割方法,并将超像素分割形式化为像素邻接图的局部划分问题,提出了一种直观的分割质量度量。该方法首先将均匀平铺的六边形重心作为超像素种子点初始位置;然后利用局部随机游走算法计算种子点与周围像素的相关程度,将其最相关种子点的标号赋予该像素;最后计算新的超像素重心,并将其作为下一轮迭代的种子点位置,通过若干次迭代逐步优化超像素分割结果。此算法具有线性的时间复杂度和线性的空间复杂度,同时超像素分割质量具有理论保证。通过标准数据集上的实验证明,该方法不仅能够较好地保持图像边界,还可以保证超像素的紧凑性,从而达到理想的超像素分割效果。