QUANTUM ALGORITHM FOR SOLVING THE TRAVELING SALESMAN PROBLEM

Huynh Van Duc, Bui Doan Khanh, Do Ngoc Diep

Abstract


We propose a new quantum algorithm for the Traveling Sales­man Problem (TSP). The algorithm is an extension of our recently intro­duced pattern search algorithm, which based on Hough transformation and Grover algorithm. Based on Lehmer code we directly build the circuit of acted elements of the symmetric group , and have a chance to add some heuristic informations. The result is a way of re-indexing elements of , so that a permutation that is a solution could be found at small in­dexes. The pattern search algorithm is then applied on a searching space that its size was reduced significantly.




DOI: https://doi.org/10.15625/0866-708X/49/5/1887 Display counter: Abstract : 237 views. PDF (Tiếng Việt) : 78 views.

Refbacks

  • There are currently no refbacks.


budidaya tani

Index: Google Scholar; Crossref; VCGate; Asean Citation Index

Published by Vietnam Academy of Science and Technology