Simulated annealing construction of shortest paths on incomplete graphs

Title:

Simulated annealing construction of shortest paths on incomplete graphs

Creator:

Pospíchal, Jiří and Kvasnička, Vladimír

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:1da52e56-72f5-498a-8a1a-8b69033461dd
uuid:1da52e56-72f5-498a-8a1a-8b69033461dd

Subject:

simulated annealing, traveling salesman problem, and shortest paths on incomplete graphs

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

Simulated annealing construction of shortest (spanning/nonspanning and closed/open) paths on generál connected graphs is discussed. A brief graphtheoretical analysis of the problem is given. A theorem has been proved that for connected graphs the shortest paths are semielementary, that is each edge on the path is visited at most twice in opposite directions. This observation considerably reduces the search space. Tasks may be further specified depending on whether the initial and terminal vertices are given or not. Similarly, in construction of shortest open paths a subtask is considered when the path must visit a prescribed subset of graph vertices. Illustrative calculations demonstrate that the proposed method results for incomplete graphs in the paths that are dosely related to optimal solutions.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Source:

Neural network world: international journal on neural and mass-parallel computing and information systems | 2003 Volume:13 | Number:3

Harvested from:

CDK

Metadata only:

false