Shortest path problem with cache dependent path lengths

被引：0

作者：

Fu, Z ^{[1
]}

Kurnia, A ^{[1
]}

Lim, A ^{[1
]}

Rodrigues, B ^{[1
]}

机构：

[1] Natl Univ Singapore, Dept Comp Sci, Singapore 117543, Singapore

来源：

CEC: 2003 CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-4, PROCEEDINGS | 2003年

关键词：

shortest path problem; cache; tabu search; Genetic Algorithms; webpages;

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

In this paper, we are motivated by the problem of finding the shortest path in a network when traversing webpages where cache size determines path length. The Shortest Path Problem with Cache-dependent Path Lengths is shown to be NP-Complete. It is a new problem for which we propose several effective heuristics, including a Dijkstra heuristic, Genetic Algorithms and Tabu Search.

引用

页码：2756 / 2761

页数：6

共 17 条

[1]

ALMEIDA V, 1996, P IEEE C PAR DISTR I

[2]

[Anonymous], 1989, GENETIC ALGORITHM SE

[3]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[4] A penalty function heuristic for the resource constrained shortest path problem [J].

Avella, P ;

Boccia, M ;

Sforza, A .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2002, 142 (02) :221-230

[5]

Bestavros A., 1995, P 4 ACM INT C INF KN

[6]

Cai X, 1997, NETWORKS, V29, P141, DOI 10.1002/(SICI)1097-0037(199705)29:3<141::AID-NET2>3.0.CO

[7]

2-H

[8]

CUNHA CR, 1997, INT S COMPUTERS COMM

[9]

Dijkstra E. W., 1959, NUMER MATH, V1, P269, DOI DOI 10.1007/BF01386390

[10] ALGORITHM-97 - SHORTEST PATH [J].

FLOYD, RW .

COMMUNICATIONS OF THE ACM, 1962, 5 (06) :345-345

← 1 2 →