文章基本信息

标题：Hamiltonian cycle and TSP: A backtracking approach
本地全文：下载
作者：Dipak Patel ; Nishant Doshi ; Shakti Patel 等
期刊名称：International Journal on Computer Science and Engineering
印刷版ISSN：2229-5631
电子版ISSN：0975-3397
出版年度：2011
卷号：3
期号：04
页码：1413-1417
出版社：Engg Journals Publications
摘要：Backtracking is one of the strategies to reduce the complexity of a problem. Backtracking mainly useful when there is a no solution by going forward in that direction so we required backtracking from it to reduce the complexity and save the time. Backtracking has ability to give same result in far fewer attempts than the exhaustive or brute force method trials. This paper gives the recursive algorithm for Hamiltonian cycle and TSP (travelling salesman problem) based on the backtracking approach. If at any stage it is detected that the particular input or combination will not lead to an optimal solution than we can discard and a new input can be selected.
关键词：Algorithm; Backtrackin; Graph; Hamiltonian path; TSP