赵晓东　陈思宇　方欢

摘要：目前，路径搜索问题在生活中的很多领域都能得到应用。生活中存在很多可转化为如下表述的实际问题：有向图图中边的权值是一个区间[a，b]，其中a表示最小代价b表示最大代价，根据个人偏好给出各边的偏好因子和一个目标值F，找出从源点到汇点的所有路径中，满足边的偏好权重值之和

关键词：有向图；偏好；路径搜索；深度优先；路径优化

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）07-0192-03

1背景

路径搜索问题在很多领域都有其研究的价值，很多问题最终都可以转化为图的路径搜索问题。常见的路径搜索算法有：Dijkstra算法、BSF算法、A*算法等。Dijkstra算法是通过中心为起点，以辐射状不断向中心外搜索（每次取距离起点最近的点），一圈一圈向外扩张，直到逼近目标点，完成路径搜索，它较能适应网络拓扑的变化、性能较稳定等；BSF算法每次扩张节点，都是通过启发函数选择最接近目标的节点，最终完成搜索；A*算法兼具Dijkstra准确和BSF的快速，在搜索路径时，通过启发式函数计算当前节点到目标节点的距离，而起始点到当前点距离已知，则每次选择初始点到目标点的代价估计最小的节点，A*算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。A*算法中的距离估算值与实际值越接近，最终搜索速度越快。以上算法都是用来求解最短路径搜索问题，大多数研究者也都是对最短路径搜索问题在不同领域进行研究。……