Open AccessPerbandingan Algoritma Cheapest Insertion Heuristics dan Pemrograman Dinamis untuk Penyelesaian Traveling Salesman Problem
Author(s) -
Anggar Titis Prayitno
Publication year - 2015
Publication title -
jurnal edukasi dan sains matematika
Language(s) - English
Resource type - Journals
eISSN - 2621-4202
pISSN - 2460-8904
DOI - 10.25134/jes-mat.v1i1.242
Subject(s) - heuristics , travelling salesman problem , computer science , path (computing) , dynamic programming , mathematical optimization , algorithm , mathematics , computer network
Traveling Salesman Problem (TSP) is one of combinatorics optimation problem to find the possible shorthest path that can be obtained if a salesman visit each city exactly once and return to the starting city. The shorthest path searching can be done by Cheapest Insertion Heuristics algorithm and Dynamic Programming. Each algorithm has different efficiency to find shorthest path. Algorithm efficiency is determined based on time complexity. Algorithm wich has the smallest time complexity is the most efficient algorithm. Based on the calculation result, the time complexity of Cheapest Insertion Heuristics algorithm is and Dynamic Programming is . Therefore, for Cheapest Insertion Heuristics Algorithm is more efficient algorithm than Dynamic Programming in TSP solving. Keywords : Traveling Salesman Problem, Cheapest Insertion Heuristics Algorithm, Dynamic Programming, and Algorithm time complexity.