The TSP is NP-Complete problem. The state space for the TSP is reduced through the reduction of the branching factor. The state space reduction increases as the number of nodes N increases. The Nearest Neighbor NN algorithm has been used N times. Each time we start at different node. All edges that are not involved by any N tours will be eliminated from the graph. We called them unpaved edges. Eliminating unpaved edges reduce sharply the state space. The Branch-and-Bound algorithm is used for the reduced state space to find the optimal path.
2nd Mosharaka International Conference on Communications and Signal Processing (MIC-CSP 2012)
Congress
2012 Global Congress on Communications and Signal Processing (GC-CSP 2012), 6-8 April 2012, Barcelona, Spain
Pages
53-57
Topics
Network Modeling and Simulation Communication Networks
ISSN
2227-331X
DOI
BibTeX
@inproceedings{342CSP2012,
title={Reduction of the State Space for the Travelling Salesman Problem (TSP) Through Elimination of Unpaved Edges},
author={Kamal R. Al-Rawi},
booktitle={2012 Global Congress on Communications and Signal Processing (GC-CSP 2012)},
year={2012},
pages={53-57},
doi={}},
organization={Mosharaka for Research and Studies}
}
