EVALUASI KINERJA ALGORITMA TRAVELING SALESMAN PROBLEM DENGAN TEKNIK PEMROGRAMAN DINAMIK

Ningtyas, Dian Kusuma and Evania, Vina and Ernastuti, Ernastuti (2008) EVALUASI KINERJA ALGORITMA TRAVELING SALESMAN PROBLEM DENGAN TEKNIK PEMROGRAMAN DINAMIK. Proceeding, Seminar Ilmiah Nasional Komputer dan Sistem Intelijen (KOMMIT 2008). ISSN 1411-6286

[img]
Preview
Text
EVALUASI KINERJA ALGORITMA TRAVELING_UG.pdf - Submitted Version

Download (225Kb) | Preview

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).

Item Type: Article
Uncontrolled Keywords: jalur terpendek; pemrograman dinamik; siklus Hamiltonian; Traveling Salesman Problem.
Subjects: A General Works > AI Indexes (General)
Divisions: Fakultas Ilmu Komputer dan Teknologi Informasi > Program Studi Sistem Komputer
Depositing User: Mr Reza Chandra
Date Deposited: 27 Feb 2014 09:37
Last Modified: 27 Feb 2014 09:37
URI: http://repository.gunadarma.ac.id/id/eprint/361

Actions (login required)

View Item View Item