JURNAL DIGIT, Vol.1, No. 2, November 2011, pp. 132~142 ISSN:2088-589X
132
Implementasi Pohon Merentang Minimum Dalam Menentukan Prioritas Pemeliharaan Jalur Jalan Kota Dengan Biaya Minimal Imran Djafar(1), Abdul Ibrahim (2) STMIK Dipanegara Makassar Perintis Kemerdekaan Km. 9 Makassar, 0411-587194/ 081342460232 E-mail:
[email protected] Abstrak Penelitian ini bertujuan bagaimana mengimplemtasikan algoritma pohon merentang minimum (Minimum Spanning Tree disingkat MST) dalam hal ini algoritma prim, kruskal dan brute force kedalam sebuah program aplikasi dengan bahasa pemrograman Visual Basic. Program ini berfungsi untuk menentukan solusi terbaik dengan biaya minimal dalam pencarian jalur prioritas dalam pemeliharaan jalan-jalan utama kota. Peta jalan utama kota diabstraksikan kedalam graf bentuk matriks ketetanggaan, yang menggunakan teknik pembobotan jalan secara multi criteria weight. Selain itu yang ingin diukur adalah kompleksitas waktu algoritma MST, apakah sudah sesuai dengan dasar teori laju pertumbuhan notasi big O atau tidak?. Penelitian ini kami lakukan di kota Makassar, dengan melakukan 2 tahapan; pengujian program algoritma MST yaitu validasi dan pengujian program, validasi program adalah uji coba beberapa matriks graf terhubung lengkap Kemudian pengujian program MST masalah perbaikan jalan dengan memasukkan graf matriks data biaya pemeliharan jalan dengan keluaran berupa pohon merentang minimum matriks data pemeliharaan jalan kota, dan daftar nama jalan-jalan kota MST.Hasil penelitian ini menunjukkan bahwa pengujian program sudah sesuai dengan algoritma MST, selain itu terlihat bahwa algoritma prim, lebih efisien dibanding kruskal, sedangkan brute force tidak efisien dibandingkan dengan prim dan kruskal. Kata kunci: Graf, full connected graf, minimum spanning tree, matriks ketetanggaan, algoritma prim, kruskal, dan brute force. Abstract The aim of the study was implement the algorithm of minimum spanning tree that is Prim algorithm, Kruskal algorithm and brute force to a visual basic language program. This program functions to determinine the best solution with minimum cost for road maintenance. The road map was abstracted to a matrix graph in the form of adjacency matrix using multi criteria weight by calculating several values. The values consisted of traffic class, road condition, and condition of drainage system. The complexity during minimum spanning tree algoritm was measured to find out the appropriateness of the growth rate of big O notation theory.The study was conducted in Makassar in two stages: the test of minimum spanning tree algorithmic program by validating was a trial of several matrices fully connected to edge random value and similar edge vale, and incomplete connected graph matrix. The minimum spanning tree test was conducted by including matrix graph of road maintenance, and the list of street names of minimum spanning tree.The result of study indicate that the program testing has been compatible with the mimimum spanning tree algorithm is more efficient than kruscal, whereas Brute force is not efficient compared to Prim and Kruskal. Keywords: Graf, full connected graf, minimum spanning tree, matriks adjacency, prim, kruskal, and brute force algorihtm. 1.
Pendahuluan Banyak permasalahan yang dapat dimodelkan dengan menggunakan graf, khususnya di bidang teknologi informasi. Salah satunya adalah masalah dalam pencarian bobot terpendek, atau termurah guna meminimal biaya. Banyak aplikasi yang membutuhkan adanya pencarian jarak / jalur terpendek dari suatu graf. Salah satu cabang dari teori graf yang banyak dikembangkan saat ini adalah penggunaan teori pohon. Konsep pohon dianggap sebagai salah satu konsep yang paling populer saat ini dan banyak digunakan untuk menyelesaikan beberapa masalah yang ditemui manusia dalam kehidupan sehariJURNAL DIGIT Vol. 1, No. 2, November 2011:132 - 142
ISSN: 2088-589X
133
harinya. seperti ketika hendak direntangkan jaringan kabel listrik yang menghubungkan sejumlah lokasi dengan panjang kabel yang digunakan sependek-pendeknya mungkin, melihat pengelompokan data yang tersebar pada suatu ruang, ataupun pada perencanaan jaringan transportasi/distribusi barang seperti membangun jalur kereta api yang menghubungkan sejumlah kota ataukah seorang salesman yang mengadakan kunjungan sejumlah kota sebanyak n kota, dimana salesman tersebut harus mengunjungi seluruh kota tersebut dengan meminimal jarak perjalanan. Dari fenomena tersebut maka akan dirancang aplikasi konsep pohon yaitu pohon merentang minimum atau Minimum Spanning Tree disingkat MST untuk menyelesaikan permasalahan jalur terpendek, jalur termurah, jalur tercepat atau jalur yang minimal dengan mengunjungi seluruh simpul atau node pada suatu graf pohon. Saat ini terdapat beberapa algoritma untuk penentuan pohon merentang minimum, namun pada penelitian ini, kami hanya menggunakan tiga algoritma yang cukup mapan untuk menyelesaikan permasalahan ini yaitu algoritma prim, algoritma kruskal dan brute-force. Ketiga algoritma ini sama-sama menerapkan strategi greedy dalam pencarian solusi terbaik (best solutions), Salah satu permasalahan yang kami angkat adalah bagaimana cara untuk penentuan jalur-jalur jalan utama dalam area kota, yang harus mendapatkan prioritas pertama dalam pemeliharaan jalan dikarenakan dana pemeliharaan yang terbatas, sehingga kesemua jalan utama dalam area kota, masih tetap terhubung satu sama lain, dengan kata lain, penentuan jalur yang menghubungkan beberapa simpul atau lokasi sehingga jalur tersebut merupakan jalur yang paling minimal. Untuk pencapaian hasil, maka akan digunakan suatu metode untuk menyelesaikan masalah Pohon Merentang Minimum (Minimum Spanning Tree) yaitu Algoritma Kruskal, Algoritma Prim dan Bruteforce. 2. Dasar Teori 2.1. Notasi “O” Tugas yang dilakukan oleh komputer untuk menyelesaikan masalah biasanya berupa tugas yang serupa, tetapi dilakukan berulang-ulang (iterasi). Banyakya perulangan yang harus dilakukan oleh komputer menentukan lama waktu proses (running time). Seringkali jumlah perulangan yang harus dilakukan dipengaruhi oleh jumlah data yang diproses. Perbedaan waktu proses sebagai fungsi jumlah data yang di[roses sangat erat hubungannya dengan laju pertumbuhan (rate of growth) algoritma yang bersangkutan. Laju pertumbuhan menunjukkan faktor kelipatan waktu proses seiring dengan kenaikan jumlah data. Jika jumlah data dilipat duakan, berapa faktor perubahan lama waktu proses yang dibutuhkan? Dalam computer, laju pertumbuhan dinyatakan dengan notasi-O (dibaca notasi big-oh/ O-besar). Notasi-O memberikan cara untuk menyatakan laju pertumbuhan algortima secara global/aproksimasi dan tidak memperhatikan perbedaan faktor konstanta serta perbedaan-perbedaan lain yang tidak begitu berpengaruh (Moh.Sjukani, 2009). 2.2. Kompleksitas Algoritma Kompleksitas waktu, T(n),diukur dari jumlah tahapan komputasi yang dibutuhkan u menjalankan algoritma sebagai fungsi dari ukuran masukan n. Kompleksitas ruang, S(n), diukur dari memori yang digunakan oleh struktur data yang terdapat di dalam algoritma sebagai fungsi dari ukuran masukan n. Kompleksitas waktu dibedakan atas tiga macam [8]: 1. Tmax(n) : kompleksitas waktu untuk kasus terburuk (worst case), kebutuhan waktu maksimum. 2. Tmin(n) : kompleksitas waktu untuk kasus terbaik (best case), kebutuhan waktu minimum. 3. Tavg(n): kompleksitas waktu untuk kasus rata-rata (average case) kebutuhan waktu secara rata-rata. 2.3. Graf Awamnya, diagram yang tersusun atas titik dan garis yang menghubungkan dua titik . Letak (posisi) titik, dan panjang dan bentuk lekukan garis tidak penting (Lawi, Armin.Dr.Eng, 2008).
Gambar 1. Contoh graf JURNAL DIGIT Vol. 1, No. 2, November 2011:132 - 142
JURNAL DIGIT
ISSN: 2088-589X
134
Graf G adalah pasangan terurut himpunan V dan E,
. Himpunan V disebut himpunan simpul (titik) dari graf G, ditulis V(G). Himpunan E disebut himpunan rusuk (sisi atau garis) dari graf G yang menghubungkan simpul dalam V, ditulis E(G). Graf dengan nama G selanjutnya ditulis G(V, E). Pada graf G contoh Gbr. 1.1 diperoleh: V(G) = { a1, a2, a3, a4, a5} dan E(G) = {e1, e2, e3, e4, e5, e6, e7} Graf G(V, E) dimana V himpunan hingga graf G disebut graf hingga. Graf G(V, E) dimana V himpunan tak-hingga graf G disebut graf tak-hingga. 2.3. Definisi Graf Pohon Graf terhubung G yang tidak memuat siklus disebut pohon. Simpul dengan derajat 1 dalam pohon disebut daun (atau simpul ujung). Simpul yang berderajat 2 atau lebih disebut simpul cabang (atau simpul dalam atau simpul internal). Kumpulan beberapa pohon disebut hutan.
Gambar 2. Graf Teorema; Pandang graf T dengan v buah simpul dan e buah rusuk. Pernyataan-pernyataan berikut adalah ekuivalen. 1. T adalah pohon. 2. T tidak memiliki siklus dan e = v – 1. 3. T terhubung dan e = v – 1. 4. T tidak memiliki siklus dan bagaimanapun caranya apabila 1 rusuk ditambahkan, terdapat 1 siklus yang terjadi. 5. T terhubung dan setiap rusuk dari T adalah rusuk potong (jembatan) dariT. 6. Untuk setiap 2 simpul dalam T, hanya terdapat satu lintasan sederhana (Lawi, Armin.Dr.Eng, 2008).
2.4. Pohon Merentang Minimum Jika G adalah graf berbobot, maka bobot pohon merentang T dari G didefinisikan sebagai jumlah bobot semua sisi di T. Pohon merentang yang berbeda mempunyai bobot yang berbeda pula. Di antara semua pohon merentang di G, pohon merentang yang berbobot minimum dinamakan pohon merentang minimum (minimum spanning tree). 2.5. Algoritma Kruskal Teorema 2.5 Pandang graf G (V, E) dengan n buah simpul. Berikut ini adalah langkah algoritma Kruskal untuk mencari pohon merentang minimal dari G. Langkah-1: Untuk i = 1, pilih rusuk e1 dengan bobot minimal. Langkah-2: Jika i = n – 1, selesai. Jika tidak, lanjutkan step-3. Langkah-3: i buah rusuk yang dipilih menjadi unsur himpunan S. Kemudian, pilih ei+1 dari himpunan E – S. Di sini, ei+1 adalah rusuk dengan bobot minimal dari subgraf terinduksi rusuk (S ∪ {ei+1})G yang tidak memiliki siklus. Pseudo-code untuk MST dengan algoritma Kruskal(G,ω) 1. A ← Φ 2. For each vertex ν∈ V[G] 3. Do MAKE-SET (ν) 4. Sort the edges of E into nondecreasing order by weight ω 5. For each edge (u,ν) ∈ E, taken in nondecreasing order by weight 6. Do if FIND-SET (u) ≠ FIND-SET (v) 7. then A ← A ∪ {(u, v)} 8. UNION (u, v) 9. Return A Implementasi Pohon Merentang Minimum Dalam Menentukan Prioritas Pemeliharaan Jalur Jalan Kota Dengan Biaya Minimal – (Imran Djafar)
ISSN: 2088-589X
135
Gambar 3. Flowchart program algoritma Kruskal 2.6. Algoritma Prim Teorema 2.6 Pandang graf G (V, E) dengan n buah simpul, berikut ini langkah-langkah dari algoritma prim : *Langkah 1: ambil sisi graf G yang berbobot minimum, masukkan ke dalam T. *Langkah 2: pilih sisi ( u,v ) yang mempunyai bobot minimum dan bersisian dengan simpul di T, tetapi ( u,v ) tidak membentuk sirkuit di T. Tambahkan ( u,v ) ke dalam T. *Langkah 3: ulangi langkah 2 sebanyak n – 2 kali. *Setiap langkah seluruhnya di dalam algoritma Prim adalah 1 + ( n - 2 ) = n – 1, yaitu sebanyak jumlah sisi di dalam pohon perentang dengan n buah simpul. Pseudo-code untuk MST dengan Algoritma Prim (G,ω,r) 1. For each u ∈ V [G] 2. do key [u] ← ∞ 3. л [u] ← NIL 4. Key [r] ← 0 5. Q ← V [G] 6. While Q ≠ Φ 7. Do u ← EXTRACT-MIN (Q) 8. for each v ∈ Adj [u] 9. do if v ∈ Q and ω (u,v) < key[v] 10. then л[v] ← u 11. key[v] ← ω(u,v) sumber: (Cormen, Leiserson, Rivest.,1990).
JURNAL DIGIT Vol. 1, No. 2, November 2011:132 - 142
JURNAL DIGIT
ISSN: 2088-589X
136
Gambar 4. Flowchart program algoritma Prim 2.7. Algoritma Brute-force Teorema 2.7; Mencari semua kombinasi pohon merentang yang mungkin dibentuk dari graf lalu dipilih jumlah bobot pohon merentang yang minimum. Algoritma Brute-force merupakan suatu metode pencarian hasil, dimana semua kemungkinan yang ada akan ditelusuri sehingga membutuhkan waktu yang lama. Algoritma Brute-force dapat diterapkan untuk kasus MST, dimana proses perulangannya menggunakan rumus kombinasi. Berikut adalah rumus untuk mencari kombinasi :
C ( n, m ) =
n! m!(n − m)!
Dimana : C ( n, m )= Kombinasi m objek diambil dari n buah objek. n= Jumlah semua lintasan yang memungkinkan. m= Banyaknya lintasan yang hanya dapat digunakan sehingga membentuk suatu pohon, dimana m = jumlah node – 1.
Implementasi Pohon Merentang Minimum Dalam Menentukan Prioritas Pemeliharaan Jalur Jalan Kota Dengan Biaya Minimal – (Imran Djafar)
ISSN: 2088-589X
137
Gambar 5. Flowchart program Brute force 2.8. Kompleksitas Algoritma Prim
Algoritma Prim mempunyai kompleksitas waktu asimptotik O (E+V log V). kompleksitas untuk asimptotik algoritma Prim agak sulit dianalisis karena menggunakan Fibonacci heap dalam mengimplementasikan minimum antrian prioritas (min-priority queue) Q, dimana Q adalah struktur data antrian dari simpul-simpul V yang diatur sesuai dengan operasi kamus (dictionary operations) untuk mekasnisme FIFO. (Cormen, Leiserson, Rivest.,1990). Simpul dan bobot pada graf direpresentasikan ke dalam matriks. Untuk mencari suatu sisi, maka algoritma Prim akan mencari kedua arah yaitu baris dan kolom graf G kemudian akan dilihat bobotnya. 2.9. Kompleksitas Algoritma Kruskal Anggaplah E adalah jumlah sisi pada graf G dan V adalah jumlah simpul. Algoritma kruskal memiliki kompleksitas asimptotik O(E log E), atau ekuivalen dengan O(E log V). Keduanya dinyatakan equivalen karena: - E paling banyak adalah V2 dan log V2 = 2 x logV atau O(log V). - Apabila kita mengabaikan simpul terpencil, V≤2E, jadi log V dapat disubstitusi dengan O(log E) Kita dapat menerima batasan karena : Pertama urutkan sisi berdasarkan bobot menggunakan pengurutan perbandingan (comparison sort) dengan waktu O(E log E); hal ini menyebabkan langkah “menghilangkan sisi dengan bobot minimum dari S” untuk dioperasikan pada waktu konstan. Kemudian kita gunakan sebuah struktur data himpunan disjoint untuk menjaga simpul mana yang terdapat pada suatu komponen. Kita membutuhkan operasi sebanyak O(E), dua buah operasi pencarian, dan mungkin sebuah penggabungan untuk setiap sisi. Sebuah struktur data himpunan disjoint sederhana seperti himpunan hutan disjoint dengan penggabungan berdasarkan rangking dapat menjalankan operasi O(E) pada waktu O(E log V). Dengan demikian total waktu asimptotiknya menjadi O(E log E) = O(E log V). (Cormen, Leiserson, Rivest.,1990). 2.10. Kompleksitas Algoritma Brute-force Algoritma brute force akan menghitung sebanyak C(n, 2) = n(n – 1)/2 pasangan titik dan memilih pasangan titik yang mempunyai jarak terkecil. Kompleksitas algoritma adalah O(n2).
JURNAL DIGIT Vol. 1, No. 2, November 2011:132 - 142
ISSN: 2088-589X
JURNAL DIGIT
138
2.11. Sistem Penilaian Jalan
Dengan menjumlahkan nilai nilai keseluruhan keadaan maka didapatkan nilai kondisi jalan. Uru tan Prior it as d ih itun g. d eng an m em ak ai ru m us sebagai berikut : Urutan Prioritas = 17 - (Kelas LHR + Nilai-Kondisi Jalan) Kelas LHR = Kelas.lalu-lintas untuk pekerjaan Pemeliharaan Nilai Kondisi Jalan = Nilai yang diberikan terhadap kondisi jalan 3.
Desain Penelitian Peta Makassar Digital
Buat penomoran, pelabelan, dan tracking untuk setiap simpang jalan kota Makassar (perlimaan, perempatan, pertigaan, perduaan jalan utama kota)
Peta jalan-jalan utama dalam bentuk Graf Matriks Data.
Hasil berupa Matriks Data Graf Pohon Merentang Minimum (Minimum Spanning Tree) dan Data Jalan MST. Input Bobot berdasarkan Multi criteria weight diambil dari kalkulasi nilai kelas lalu lintas, nilai konsidi jalan, dan nilai kondisi sistem dranaise
Buat Matriks ketetanggaannya kedalam Mic. Excell
Simpan dengan extensi *.dat yang berisikan adjacensy matriks (file teks)
Jalankan Program Pohon Merentang Minimum, dengan Algoritma Kruskal, Prim dan Brute-force, dengan inputan file teks
a
Gambar 6. Desain penelitian
4.
Pengujian Algoritma Program Mst Pengujian algoritma MST, dibagi atas dua bagian, yaitu pertama; validasi program MST, dan kedua yaitu pengujian program MST pada masalah pemeliharan jalan. Pengukuran dilakukan sebanyak sepuluh kali percobaan pada setiap satu ukuran matriks yang berbeda (dapat dilihat pada lampiran 4), data matriks yang digunakan berukuran 3x3 hingga 66x66. Hasil pengukuran kemudian ditotal kemudian dirata-ratakan lalu dimasukkan kedalam tabel hasil komputasi waktu untuk melihat pertumbuhan kompleksitas waktunya. 4.1. Validasi Program MST Uji coba beberapa data matriks ketetanggaan untuk mendapatkan sebuah data dan grafik pertumbuhan kompleksitas waktu pada setiap algoritma MST untuk; a.
Graf terhubung lengkap (full connected graph) dengan nilai edge random Pada tabel 1 memperlihatkan hasil komputasi ketiga algoritma MST. Tampak hasil total waktu yang ditunjukkan oleh algoritma prim masih lebih baik (efisien) dibandingkan dengan algoritma kruskal, sedangkan untuk brute-force terlihat sangat kurang efisien karena waktu yang dibutuhkan sangat lama dibandingkan dengan prim dan kruskal.
Implementasi Pohon Merentang Minimum Dalam Menentukan Prioritas Pemeliharaan Jalur Jalan Kota Dengan Biaya Minimal – (Imran Djafar)
ISSN: 2088-589X
139 Tabel .1 Hasil Komputasi Waktu Matriks Full Connected Random T Rerata Lama Waktu Komputasi 10 x Percobaan Ukuran jumlah jumlah (detik) No node edge Brute Matriks Prim Kruskal Force 1 3x3 3 3 1.09 1.08 1.10 2 4x4 4 6 1.10 1.06 1.23 3 5x5 5 10 1.10 1.06 1.23 4 6x6 6 15 1.09 1.06 5.50 5 7x7 7 21 1.29 1.20 259.18 6 8x8 8 28 2.02 1.98 ~ 7 9x9 9 36 2.01 1.98 ~ 8 10x10 10 45 2.02 1.98 ~ 9 15x15 15 105 2.02 1.98 ~ 10 20x20 20 190 2.02 1.99 ~ 11 25X25 25 300 2.02 2.03 ~ 12 30X30 30 435 2.02 2.09 ~ 13 66X66 66 2145 2.05 4.19 ~ TOTAL
21.85
23.66
268.23
Terlihat pada gambar 7, terlihat bahwa hasil komputasi waktu Prim dan kruskal, prim jauh lebih efisien dibandingkan dengan kruskal. 6,00 4,00
Prim
2,00
Kruskal
0,00 1
3
5
7
9
11 13
Gambar 7. Grafik Hasil Komputasi Waktu Prim Dan Kruskal Full C. Random Terlihat pada gambar 8, terlihat bahwa hasil komputasi waktu Brute-force sangat kurang efisien karena waktu yang dibutuhkan sangat lama dibandingkan dengan prim dan kruskal.
Brute Force 300,00 200,00 Brute Force
100,00 0,00 1 2 3 4
5
Gambar 8. Grafik Hasil Komputasi Waktu Brute Force Full C. Random JURNAL DIGIT Vol. 1, No. 2, November 2011:132 - 142
140
ISSN: 2088-589X
JURNAL DIGIT b.
Not full connected graph dengan nilai edge bernilai acak, Pada tabel 2 memperlihatkan hasil komputasi ketiga algoritma MST. Tampak hasil total waktu yang ditunjukkan oleh algoritma prim masih lebih baik (efisien) dibandingkan dengan algoritma kruskal, sedangkan untuk brute-force terlihat sangat kurang efisien karena waktu yang dibutuhkan sangat lama dibandingkan dengan prim dan kruskal. Tabel 2. Hasil Komputasi Waktu Matriks Not Full Connected T Rerata Lama Waktu Komputasi 10 x Ukuran jumlah jumlah Percobaan (detik) No node edge Brute Matriks Prim Kruskal Force 1 3x3 3 3 1.13 1.27 1.76 2
4x4
4
6
1.15
1.32
1.57
3
5x5
4 5
6x6 7x7
5
9
1.01
1.36
1.57
6 7
10 12
1.13 1.17
1.27 1.32
1.79 2.50
6 7
8x8
8
14
1.24
1.41
4.32
9x9
9
17
1.13
1.29
18.52
8
10x10
10
23
1.02
1.45
2,283.95
9
15x15
15
31
1.64
1.67
˜
10
20x20
20
41
1.44
1.67
˜
11
25X25
25
53
1.32
1.69
˜
12
30X30
30
71
1.70
2.02
˜
13
66X66
66
132
1.72
2.03
˜
TOTAL
16.80
19.78
2,315.99
Terlihat pada gambar 9, terlihat bahwa hasil komputasi waktu Prim dan kruskal, prim jauh lebih efisien dibandingkan dengan kruskal.
2,50 2,00 1,50 Prim 1,00
Kruskal
0,50 0,00 1
3
5
7
9
11 13
Gambar 9. Grafik Hasil Komputasi Waktu Prim Dan Kruskal Not Full Connected Terlihat pada gambar 10, terlihat bahwa hasil komputasi waktu Brute-force sangat kurang efisien karena waktu yang dibutuhkan sangat lama dibandingkan dengan prim dan kruskal.
Implementasi Pohon Merentang Minimum Dalam Menentukan Prioritas Pemeliharaan Jalur Jalan Kota Dengan Biaya Minimal – (Imran Djafar)
ISSN: 2088-589X
141
Brute Force 2.500,00 2.000,00 1.500,00 1.000,00
Brute Force
500,00 0,00 12345 678 Gambar 10. Grafik Hasil Komputasi Waktu Brute Force Not Full Connected 4.2. Hasil pengujian program MST pada masalah pemeliharan jalan. a. Untuk matriks data pemeliharaan jalan Pengujian program MST, data matriks pemeliharaan jalan, sebelum proses: Jumlah Node = 66, Jumlah Edge = 89, Total Weight = 3117302100, Setelah proses didapatkan hasil data, untuk Prim: Jumlah Node= 66, Jumlah Edge= 65, Total Weight MST= 1214028750, Lama Waktu= 2,09, Sedangkan Kruskal: Jumlah Node= 66, Jumlah Edge= 65, Total Weight MST= 1214028750, Lama Waktu= 2,11. Ini dapat dilihat pada lampiran III A. Sedangkan hasil data matriks oleh program MST dengan algoritma Brute Force setelah di run dengan ukuran data matriks 66x66, hasilnya Data Type Over flow, ini disebabkan oleh tingginya kompleksitas waktu dan ruang yang dibutuhkan untuk proses tidak sebanding dengan spesfikasi prosessor dan memori komputer.
Gambar 11. matriks data pemeliharaan jalan b. Untuk data jalan pemeliharaan MST Pengujian program MST, untuk data jalan pemeliharaan MST, sebelum proses: Jumlah data jalan pemeliharaan= 89 jalan, dengan Total Weight = 3117302100, Setelah diproses oleh program MST, didapatkan hasil data jalan, untuk Prim dan Kruskal: Jumlah data jalan pemeliharaan MST= 66 jalan, dengan Total Weight MST= 1214028750. Terlihat antara kedua algoritma, prim dan kruskal, ada perbedaan pemilihan jalur jalan pemeliharaan, namun tetap sama nilai Total Weight MST yang dihasilkan antara prim dan kruskal.
Gambar 12. tampilan data pemeliharaan jalan
JURNAL DIGIT Vol. 1, No. 2, November 2011:132 - 142
JURNAL DIGIT c.
ISSN: 2088-589X
142
Untuk Visualisasi dengan peta kota oleh MapSource:
Hasil graf matriks dari proses algoritma MST, yang divisualisasikan kedalam graf peta kotaMST dengan MapSource sudah sesuai dengan teori tentang pohon merentang minimum ini terbukti dari hasil visualisasinya. Dari hasil visualisasi graf MST untuk kedua algoritma, algoritma prim dan kruskal didapatkan hasil graf mst yang berbeda, namun kedua algoritma, prim dan kruskal sama-sama menghasilkan total weight cost yang sama nilainya, ini berarti bahwa graf MST yang dihasilkan oleh kedua algoritma boleh berbeda, berbeda dalam pemilihan jalur edge (jalur jalan), namun keduanya samasama menghasikan total weight cost yang sama.
Gambar 13. Visualisasi kedalam peta 5. Kesimpulan Aplikasi yang dirancang untuk menyelesaikan masalah pemeliharaan jalan di kota Makassar diselesaikan dengan mencari MST dari graf peta jalan utama kota Makassar. Graf yang digunakan diabstraksikan kedalam bentuk matriks adjecency atau matriks ketetanggaan, untuk kemudian digunakan kedalam ketiga Algoritma MST. Algoritma Prim, Kruskal, dan Brute-Force merupakan algoritma yang digunakan untuk memecahkan permasalahan yang berhubungan dengan pencarian MST. Ada perbedaan yang dimiliki Antara algoritma Prim dan algoritma Kruskal yaitu, langkah-langkah yang diambil oleh masing-masing algoritma, jumlah langkah, dan cara penentuan pohon merentang minimumnya. Algoritma Prim lebih berorientasi pada pencarian simpul-simpul yang dihubungkan oleh sisi dengan bobot minimum. Sisi graf yang dimasukkan untuk menjadi kandidat sisi pohon merentang minimum adalah sisi yang bersisian dengan simpul sebelumnya Sedangkan pada algoritma Kruskal lebih berorientasi pada pencarian sisi-sisi yang memiliki bobot minimum lalu mengurutkannya dari sisi dengan bobot minimum hingga bobot maksimum kemudian dilakukan penyaringan terhadap sisi yang membentuk sirkuit. Pada algoritma Kruskal, proses mengurutkan inilah yang membuat Kruskal kalah efisien dibandingkan dengan algoritma Prim. Hal ini terbukti dari hasil percobaan yang diberikan pada table-tabel. Algoritma Brute force merupakan suatu metode pencarian hasil, dimana semua kemungkinan yang ada akan ditelusuri sehingga membutuhkan waktu yang sangat lama pada prosesnya dibandingkan dengan algoritma prim dan kruskal. Algoritma Brute Force mencari semua kombinasi pohon merentang yang mungkin dibentuk dari graf lalu dipilih jumlah bobot pohon merentang minimumnya, ini terbukti dari hasil percobaan.
Daftar Pustaka [1] Cormen, Leiserson, Rivest. Introduction to Algorithms. 1990. The MIT Press. Massachusetts Institute of Technology. [2] Direktorat Jenderal Bina Marga Direktorat Pembinaan Jalan Kota, Tata Cara Penyusunan Program Pemeliharaan Jalan Kota, 1990, Jakarta. [3] Goodaire, Edgar G ; Parmenter, Michael M. Discrete Mathematics with Graph Theory. 1998. Prentice Hall, Inc. New Jersey. [4] Lawi, Armin. Dr.Eng, 2008.Materi Ajar Matakuliah Matematika Diskrit. Universitas Hasanuddin, Indonesia. [5] Liu, C.L. Element of Discrete Mathematics 2nd.1985. McGraw-Hill,Inc. [6] Suarga, Ph.D., 2007 .Algoritma Pemrograman, Penerbit Andi, Yogyakarta. [7] Moh.Sjukani.2009. Struktur Data (Algoritma & Struktur Data 2) dengan C, C++ Edisi 3, Mitra Wacana Media, Jakarta. [8] Munir,Rinaldi. 2001. Matematika Diskrit. Cetakan Pertama. Informatika. Bandung. Implementasi Pohon Merentang Minimum Dalam Menentukan Prioritas Pemeliharaan Jalur Jalan Kota Dengan Biaya Minimal – (Imran Djafar)
