Penyelesaian Travelling Salesman Problem pada Pemrograman C++ [TI Politala Alpro 2C]

BAB I
PENDAHULUAN

 

 

1.1  Latar Belakang

Laporan ini membahas tentang persoalan lintasan terpendek suatu graf dengan algoritma dijikstra dan kruskal. Saat ini banyak sekali algortimaalgoritma yang dapat digunakan untuk menyelesaikan persoalan penentuan lintasan terpendek (shortest path problem) dari suatu graf. Solusi yang didapat dari penelusuran algoritma tersebut dapat diberi nama Pathing Algorithm. Ada dua algortima yang cukup terkenal yang bisa digunakaan untuk menyelesaikan persoalan lintasan terpendek, yaitu Algoritma Dijkstra dan Algoritma BellmanFord. Tetapi pada kesempatan ini kita hanya akan membahas tentang algoritma dijkstra.

Algoritma Dijkstra adalah sebuah algoritma yang dipakai dalam memecahkan permasalahan jarak terpendek untuk sebuah graph berarah dengan bobot-bobot sisi yang bernilai positif.

Algoritma kruskal adalah sebuah algoritma dalam teori graf yang mencari sebuah minimum spanning tree untuk sebuah graf berbobot yang terhubung.

1.2  Rumusan Masalah

Rumusan masalah pada laporan ini sebagai berikut :

1. Pengertian dari algoritma Dijkstra dan Kruskal

2. Contoh kasus TSP dengan algoritma Dijkstra dan Kruskal

1.3 Tujuan dan Manfaat

Tujuan dan Manfaat pada laporan ini sebagai berukit :

1. Mengetahui pengertian dari algoritma Dijkstra dan Kruskal

2. Dapat menyelesaikan kasus TSP dengan algoritma Dijkstra dan Kruskal

1.4 Batasan Masalah

Batasan laporan ini adalah mengenai algoritma lainnya yang memiliki ciri yang sama dengan algoritma Dijkstra dan Kruskal.

 

BAB II
PEMBAHASAN

 

 

2.1 Pengertian Algoritma Dijkstra dan Kruskal

Algoritma Dijkstra dan Kruskal adalah beberapa algoritma dalam menyelesaikan jalur terpendek dari suatu graph. Maka dari itu, pembahasannya tidak jauh dengan matematika diskrit khususnya tentang graph. Graph memiliki beberapa struktur yaitu : simpul (vertex) dan sisi (edge).

Algoritma Dijkstra, (penemunya adalah seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma yang dipakai dalam memecahkan permasalahan jarak terpendek untuk sebuah graph berarah dengan bobot-bobot sisi yang bernilai positif.

Beberapa tahapan dalam algoritma Dijkstra, yaitu :

1)      Beri nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain (yang belum terisi).

2)      Set semua node “Belum terjamah” dan set node awal sebagai “Node keberangkatan”.

3)      Dari node keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan.

4)      Setelah selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.

5)      Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan lanjutkan dengan kembali ke step 3.

 

Algoritma kruskal adalah sebuah algoritma dalam teori graf yang mencari sebuah minimum spanning tree untuk sebuah graf berbobot yang terhubung. Ini berarti menemukan subset dari tepi yang membentuk sebuah pohon yang mencakup setiap titik , di mana berat total dari semua tepi di atas pohon diminimalkan.. Jika grafik tidak terhubung, maka menemukan hutan rentang minimum (pohon rentang minimum untuk setiap komponen terhubung). Algoritma Kruskal juga tergolong algoritma Greedy dalam teori graf yang digunakan untuk mencari minimum spanning tree. Algoritma ini pertama kali muncul pada tahun 1956 dalam sebuah tulisan yang ditulis oleh Joseph Kruskal. Algoritma Kruskal adalah contoh dari algoritma rakus. Algoritma ini pertama kali muncul dalam Prosiding American Mathematical Society, hal 1956.

Dasar pembentukan algoritma Kruskal berasal dari analogi growing forest. Growing forest maksudnya adalah untuk membentuk pohon merentang minimum T dari graf G adalah dengan cara mengambil satu per satu sisi dari graf G dan memasukkannya ke dalam pohon yang telah terbentuk sebelumnya. Seiring dengan berjalannya iterasi untuk setiap sisi, maka forest akan memiliki pohon yang semakin sedikit. Oleh sebab itu, maka analogi ini disebut dengan growing forest. Algoritma Kruskal akan terus menambahkan sisi – sisi ke dalam hutan yang sesuai hingga akhirnya tidak akan ada lagi forest dengan, melainkan hanyalah sebuah pohon yang merentang minimum.

Langkah-langkah utama Algoritma Kruskal adalah sebagai berikut:

1)      Atur tepi berat: paling berat pertama dan terberat terakhir.

2)      Pilih yang paling ringan tidak diperiksa tepi dari diagram.

3)      Tambahkan tepi memilih ini ke pohon, hanya jika hal itu tidak akan membuat siklus.

4)      Menghentikan proses kapanpun n – 1 tepi telah ditambahkan ke pohon.

 

2.2 Contoh kasus TSP dengan algoritma Dijkstra dan Kruskal

Seorang salesman berkelana ke 3 kota untuk menawarkan barang milik perusahaan. Jarak dari 1 kota kekota lain berbeda-beda, yaitu :

1 = kantor       

2 = kota pelaihari

3 = kota banjarmasin

4 = kota martapura

Untuk matriksnya dapat disimpulkan seperti ini :

X	1	2	3	4
1	0	58	33	9
2	58	0	67	60
3	33	67	0	0
4	9	60	0	0

 

 

Buatlah program C++ dengan menggunakan algoritma Dijkstra dan Kruskal!

Jawab :

1)      Dijkstra

 

Hasil Running :

 

2)      Kruskal

 

 

Hasil Running :

BAB III
PENUTUP

 

 

3.1 Kesimpulan

Algoritma Dijkstra merupakan sebuah algoritma yang dipakai dalam memecahkan permasalahan jarak terpendek untuk sebuah graph berarah dengan bobot-bobot sisi yang bernilai positif. Sedangkan Algoritma kruskal adalah sebuah algoritma dalam teori graf yang mencari sebuah minimum spanning tree untuk sebuah graf berbobot yang terhubung. Ini berarti menemukan subset dari tepi yang membentuk sebuah pohon yang mencakup setiap titik , di mana berat total dari semua tepi di atas pohon diminimalkan. Jadi algoritma djikstra merupakan pencarian nilai pendek dengan meggunakan bobot sisi yang bernilai positif sedangkan algoritma Kruskal dia mencari nilai minimum dengan menemukan subset dari sebuah pohon yang mencakup setiap titik.

3.2 Saran

     Sebenarnya ada banyak cara/algoritma untuk menyelesaikan rute terpendek, namun disini penyusun hanya bisa menyajikan algoritma Dijkstra dan Kruskal. Saran dari penyusun adalah silakan pembaca agar mempelajari algoritma yang lebih memudahkan.

 

DAFTAR PUSTAKA

 

 

Kusrini, & Istiyanto, J. E. (2008). PENYELESAIAN TRAVELLING SALESMAN PROBLEM DENGAN ALGORITMA CHEAPEST INSERTION HEURISTICS DAN. Algoritma dan Pemrograman, 1-6.

Rachmah, N. F. (2006). Aplikasi Algoritma Dijkstra dalam Pencarian Lintasan Terpendek Graph. Algoritma dan Pemrograman, 1-6.