Evaluasi Kinerja Algoritma Traveling Salesman Problem Dengan Teknik Pemrograman Dinamik

Abstract

Traveling Salesman Problem (TSP) dapat diilustrasikan sebagai perjalanan seorang salesman yang harus melalui semua kota yang dituju dengan jarak terpendek, dimana setiap kota hanya boleh dilalui satu kali. Solusi optimal dari TSP ialah jalur terpendek yang dapat dilalui oleh salesman tersebut. Model TSP dinyatakan dalam bentuk graf. Rute perjalanan dengan aturan pengunjungan satu dan hanya satu kali pada setiap simpul (node) dalam graf disebut dengan jalur Hamiltonian. Bila perjalanan dimulai dan berakhir di simpul yang sama maka jalur ini disebut siklus Hamiltonian. TSP merupakan suatu permasalahan permutasi; yaitu problem yang secara konvensional diselesaikan dalam waktu n! (n faktorial), untuk n buah objek. Di dalam paper ini akan dibahas mengenai implementasi algoritma TSP dengan metode pemrograman dinamis (dynamic programming) pada bahasa pemrograman Pascal. Dengan metode pemrograman dinamik (dynamic programming), TSP dapat diselesaikan dalam fungsi waktu yang eksponensial O(n22n), dimana n! > O(2n).