计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2004年
17期
72-73
,共2页
路线规划%时间复杂度%算法
路線規劃%時間複雜度%算法
로선규화%시간복잡도%산법
在城市的公交网络系统中,如果通过乘公交车从点X到点Y,那么如何乘坐(可能需要换乘公交车),使得花费最少?这是Datar和Ranade提出的一个开问题.该文通过对城市公交网络系统的分析,给出了一个解决该问题的时间复杂度为多项式的算法.另外文章还讨论了当找到一条费用最小的乘车路线规划时,如何乘坐公交车使得能最快地到达目的地,并给出了时间复杂度为多项式的算法.
在城市的公交網絡繫統中,如果通過乘公交車從點X到點Y,那麽如何乘坐(可能需要換乘公交車),使得花費最少?這是Datar和Ranade提齣的一箇開問題.該文通過對城市公交網絡繫統的分析,給齣瞭一箇解決該問題的時間複雜度為多項式的算法.另外文章還討論瞭噹找到一條費用最小的乘車路線規劃時,如何乘坐公交車使得能最快地到達目的地,併給齣瞭時間複雜度為多項式的算法.
재성시적공교망락계통중,여과통과승공교차종점X도점Y,나요여하승좌(가능수요환승공교차),사득화비최소?저시Datar화Ranade제출적일개개문제.해문통과대성시공교망락계통적분석,급출료일개해결해문제적시간복잡도위다항식적산법.령외문장환토론료당조도일조비용최소적승차로선규화시,여하승좌공교차사득능최쾌지도체목적지,병급출료시간복잡도위다항식적산법.
