METODE PROGRAM DINAMIS PADA PENYELESAIAN TRAVELING SALESMAN PROBLEM

Hermianus Yunus, Helmi, Shantika Martha

Abstract


Traveling Salesman Problem (TSP) merupakan masalah pada graf dalam membentuk sebuah sirkuit untuk melewati semua simpul dengan total bobot dari sisi pembentuk sirkuit minimum. Program Dinamis merupakan salah satu metode yang dapat digunakan untuk menyelesaikan TSP. Program Dinamis adalah metode penyelesaian dengan menguraikan solusi menjadi beberapa tahap atau iterasi sedemikian hingga solusi dari persoalan tersebut dapat dipandang sebagai serangkaian keputusan yang saling berkaitan. Penelitian ini membahas tentang mengkaji penggunaan Program Dinamis pada penyelesaian TSP untuk menentukan sirkuit dengan bobot minimum dan melewati semua simpul dari graf. Berdasarkan arah dan bobotnya jika diambarkan dalam bentuk graf, TSP simetris merupakan jenis graf tidak berarah dan berbobot kemudian TSP asimetris adalah graf berarah dan berbobot. Penyelesaian TSP dapat menggunakan Program Dinamis rekursif maju dan rekursif mundur karena mempunyai solusi optimal yang sama. Hasil penyelesaian TSP menggunakan Program Dinamis dengan rekursif maju diperoleh berdasarkan solusi optimal dari iterasi ke-1 sampai iterasi ke-t. Sirkuit diperoleh dengan merekonstruksi simpul yang dilewati dari iterasi ke-1 sampai iterasi ke-t dan bobot minimum dari sirkuit tersebut berdasarkan solusi pada iterasi ke-t.

Kata Kunci: rekursif maju, sirkuit


Full Text:

PDF


DOI: http://dx.doi.org/10.26418/bbimst.v4i03.12428

Refbacks

  • There are currently no refbacks.