1

8. Algoritma Greedy Oleh : Ade Nurhopipah

Pokok Bahasan :

1. Minimum Connector Problem

2. Travelling Salesman Problem

Sumber :

Aldous, Joan M. ,Wilson, Robin J. 2004. Graph and Applications. Springer: UK.

Pada bab ini, kita akan membahas beberapa algoritma umum yang berkaitan dengan

konstruksi tree. Kita akan mempelajari masalah minimum connector, dan menunjukan bagaimana

solusinya dapat memberi informasi tentang penyelesaian travelling salesman problem (TSP). Kedua

topik ini melibatkan konsep spanning tree dalam graph terhubung.

Minimum Connector Problem

Misalkan kita akan membuat sebuah sistem kanal irigasi yang menghubungkan sejumlah

lokasi. Biaya penggalian dan perawatan untuk setiap kanal diketahui. Beberapa pasang lokasi tidak

dapat dihubungkan dengan sebuah kanal karena alasan geografi. Bagaimana kita dapat mendesain

kanal yang menghubungkan semua lokasi dengan biaya total yang minimal?

Masalah ini dapat diinterpretasikan dalam dua cara, tergantung pada apakah kita

mengijinkan adanya lokasi “ekstra”, di mana kanal dapat berpotongan. Sebagai contoh, pada kasus

sistem kanal dalam Gambar 8.1, kita mungkin mampu untuk mengurangi total biaya dengan

mambuat sebuah lokasi ekstra pada titik E dan menghubungkannya dengan lokasi A.

Gambar 8.1 Contoh kasus sistem kanal irigasi

Sayangnya, untuk banyak permasalahan, biaya tambahan untuk membuat lokasi ekstra

melebihi biaya jika kita membangun sistem kanal tanpa tambahan lokasi. Oleh sebab itu, kita

mengambil interpretasi kedua yang mengasumsikan bahwa setiap koneksi menghubungkan dua

lokasi, dan tidak ada lokasi baru yang boleh dibuat.

2

Kita dapat memodelkan masalah ini dengan graph, di mana lokasi diwakili dengan vertex dan

kanal diwakili dengan edge yang memiliki bobot. Bobot edge pada kasus ini mewakili banyaknya

biaya. Masalah yang akan kita selesaikan adalah bagaimana menemukan subgraph terhubung yang

melalui semua vertex dari graph yang ada, sehingga memiliki total bobot yang minimal. Subgraph

yang dimaksud adalah sebuah spanning tree, karena jika terdapat sebuah cycle, kita akan dapat

mengurangi biaya total dengan menghapus sebuah edge pada cycle tersebut. Masalah ini ditunjukan

pada Gambar 8.2.

Gambar 8.2 Representasi graph berbobot untuk sistem kanal irigasi

Pada contoh masalah yang ditunjukan Gambar 8.2, total bobotnya adalah 100. Penghapusan

sebuah edge dari cycle yang ada, dapat mengurangi total bobot, dan menghasilkan sebuah spanning

tree. Spanning tree dengan total bobot minimal diperoleh dengan menghapus dua edge yang

memiliki bobot terbesar yaitu AD dan BC. Biaya minimal yang dihasilkan adalah 16+20+10= 46. Kita

menyebut spanning tree tersebut sebagai minimum connector untuk lokasi A,B,C,D.

Definisi 8.1 Misalkan T adalah spanning tree dengan total bobot minimal dalam sebuah graph terhubung berbobot G, maka T adalah minimum spanning tree atau minimum connector pada graph G tersebut.

Masalah minimum connector dalam graph secara teoritis adalah sebagai berikut.

Minimum Connector Problem Diberikan sebuah graph berbobot, temukan minimum spanning tree pada graph tersebut.

Kita akan mempelajari dua algoritma untuk menyelesaikan masalah ini. Keduanya adalah

algoritma yang termasuk algoritma Greedy. Nama ini muncul karena pada setiap tahap kita memilih

suatu pilihan yang paling “rakus” dalam arti pilihan yang terbaik, tanpa memperhatikan efek

selanjutnya dari pilihan tersebut.

3

Algoritma Kruskal

Algoritma Kruskal diperkenalkan oleh Joseph Kruskal pada tahun 1956. Dalam menerapkan

algoritma ini, pada setiap tahap kita memilih edge yang bobotnya paling kecil, yang tidak

membentuk sebuah cycle. Berikut adalah langkah-langkah algoritma Kruskal.

Algoritma Kruskal Mulai dengan sebuah himpunan terbatas vertex, di mana setiap pasangan vertex dihubungkan dengan sebuah edge berbobot. Langkah 1 Daftar semua bobot dalam urutan naik. Langkah 2 Gambar vertex dan edge berbobot yang berkoresponden dengan bobot pertama dalam daftar yang tersedia, sedemikian rupa sehingga tidak ada cycle yang terbentuk. Hapus bobot dari daftar. Ulangi langkah 2 sampai semua vertex terhubung, lalu berhentilah. Graph berbobot yang diperoleh adalah minimum connector, dan jumlah bobot pada semua edge adalah jumlah total bobot dari minimum connector.

Catatan :

1. Ketika dua bobot atau lebih bernilai sama, akan muncul daftar dalam berbagai urutan. Bobot

tersebut berada pada daftar dalam susunan tidak turun juga tidak naik.

2. Pada algoritma ini, kita tidak perlu mendapatkan sebuah graph terhubung pada setiap tahapnya.

Kita ilustrasikan penggunaan algoritma ini dengan contoh 8.1.

Contoh 8.1

Diberikan sebuah graph berbobot berikut.

Catat bahwa, pada contoh ini, beberapa bobot memiliki nilai yang sama, sehingga mungkin

kita memiliki sebuah pilihan edge yang berbeda dan terdapat lebih dari satu minimum spanning tree.

4

Edge pertama Kita memilih sebuah edge dengan bobot minimal. Edge yang mungkin hanya satu yaitu AE dengan bobot 2.

Edge kedua Kita memilih edge dengan bobot terkecil selanjutnya, yaitu di antara AC atau CE, dengan bobot 4. Misal kita memilih CE.

Edge ketiga Kita tidak bisa memilih AC, yang juga memiliki bobot 4, karena dapat menciptakan subuah cycle ACEA, sehingga kita memilih bobot terkecil selanjutnya. Satu edge yang mungkin hanya BC dengan bobot 5.

Edge keempat Edge dengan bobot terkecil selanjutnya adalah AB dan BE, dengan bobot 6. Kita tidak bisa memilih keduanya, karena dapat menciptakan cycle ABCEA atau BCEB, sehingga kita memilih edge terkecil selanjutnya. Satu edge yang mungkin dipilih adalah DE dengan bobot 7.

Kita telah mendapatkan minimum spanning tree yang memuat semua vertex, dengan total

bobot 2+4+5+7=18.

Latihan 8.1 Pada contoh 8.1, minimum spanning tree seperti apa yang diperoleh jika pada tahap kedua, kita memilih edge AC?

Jika jumlah vertex pada graph berbobot berjumlah banyak, bobot-bobotnya biasanya

disajikan dalam bentuk tabel, seperti ditunjukan pada contoh 8.2.

5

Contoh 8.2

Tabel berikut menunjukan jarak (dalam satuan ratusan mil) di antara enam kota. Kita akan

menggunakan algoritma Kruskal untuk menemukan sebuah minimum spanning tree yang

menghubungkan kota-kota tersebut.

Edge pertama Kita memilih sebuah edge dengan bobot minimal. Edge yang mungkin hanya satu yaitu London-Paris dengan bobot 3.

Edge kedua Kita memilih edge dengan bobot terkecil selanjutnya, yaitu antara Berlin-London atau Berlin-Paris dengan bobot 7. Misal kita memilih Berlin-London.

Edge ketiga Kita tidak bisa memilih Berlin-Paris yang juga memiliki bobot 7, karena dapat menciptakan subuah cycle. Sehingga kita memilih bobot terkecil selanjutnya. Satu edge yang mungkin hanya Paris-Seville dengan bobot 8.

Edge keempat Kita memilih edge dengan bobot terkecil selanjutnya yaitu Paris-Rome dengan bobot 9.

Edge kelima Kita tidak bisa memilih Berlin-Rome dengan bobot 10, ataupun London-Seville dengan bobot 11, karena dapat menciptakan cycle. Sehingga kita memilih edge Berlin-Moscow dengan bobot 11.

Kita telah mendapatkan minimum spanning tree yang memuat semua vertex, dengan total

bobot 3+7+8+9+11=38.

6

Latihan 8.2 Tabel berikut menunjukan jarak (dalam mil) antara enam tempat di Ireland. Gunakan algoritma Kruskal untuk menemukan sebuah minimum spanning tree yang menghubungkan tempat-tempat tersebut.

Algoritma Prim

Walaupun algoritma Kruskal dapat diaplikasikan dengan mudah saat jumlah kotanya sedikit,

namun algoritma ini tidak efektif untuk implementasi komputer, karena kebutuhan penyusunan

edge dalam susunan bobot terurut naik dan kebutuhan untuk mengenali cycle yang tercipta. Kedua

kesulitan ini dapat diatasi dengan modifikasi algoritma Kruskal yang disebut dengan algoritma Prim.

Dalam aplikasi algoritma Prim ini, kita memulai dengan sebuah vertex dan membangun spanning

tree yang diinginkan edge demi edge.

Algoritma Prim Mulai dengan sebuah himpunan terbatas vertex, di mana setiap pasangan vertex dihubungkan dengan sebuah edge berbobot. Langkah 1 Pilih dan gambar sembarang vertex. Langkah 2 Temukan edge yang memiliki bobot minimal yang menghubungkan vertex yang sudah digambar dengan vertex yang belum digambar. Gambar edge berbobot ini dan vertex baru yang berkoresponden dengannya. Ulangi langkah 2 sampai semua vertex terhubung, lalu berhentilah.

Catatan :

1. Ketika ada dua buah edge atau lebih dengan bobot yang sama, pilihlah sembarang edge dari

beberapa edge tersebut.

2. Dengan konstruksi ini, kita memperoleh sebuah graph terhubung pada setiap tahapnya.

7

Contoh 8.3

Tabel berikut menunjukan jarak (dalam satuan ratusan mil) antara enam buah kota. Gunakan

algoritma Prim untuk menemukan sebuah minimum spanning tree T yang menghubungkan kota

tersebut.

Kita mulai dengan memilih sebuah vertex. Misalnya Berlin.

Edge pertama Kita memilih sebuah edge dengan bobot minimal yang menghubungkan Berlin dengan vertex lain yang tersisa. Kita dapat memilih Berlin-London atau Berlin-Paris, dengan bobot 7. Misalnya edge yang kita pilih adalah Berlin-London.

Edge kedua Kita memilih edge dengan bobot terkecil yang menghubungkan Berlin atau London ke vertex lain yang tersisa. Hanya ada satu kemungkinan yaitu London-Paris dengan bobot 3.

Edge ketiga Kita memilih edge dengan bobot terkecil yang menghubungkan Berlin,London atau Paris ke vertex lain yang tersisa. Hanya ada satu kemungkinan yaitu Paris-Seville dengan bobot 8.

Edge keempat Kita memilih edge dengan bobot terkecil yang menghubungkan Berlin, London, Paris atau Seville ke vertex lain yang tersisa. Hanya ada satu kemungkinan yaitu Paris-Rome dengan bobot 9.

Edge kelima Kita memilih edge dengan bobot terkecil yang menghubungkan Berlin, London, Paris, Seville atau Rome ke vertex lain yang tersisa. Hanya ada satu kemungkinan yaitu Berlin-Moscow dengan bobot 11.

8

Kita telah mendapatkan minimum spanning tree yang memuat semua vertex, dengan total

bobot 7+3+8+9+11=38 (ini adalah tree yang kita peoleh pada contoh 8.2)

Latihan 8.3 Pada contoh 8.3, seperti apa minimum spanning tree yang diperoleh : a. Jika pada tahap pertama kita memilih Berlin-Paris, dari pada Berlin-London? b. Jika kita memulai dengan memilih Rome sebagai vertex pertama daripada Berlin?

Teorema 8.1 Algoritma Kruskal dan algoritma Prim selalu menghasilkan sebuah spanning tree dengan bobot yang minimal.

Bukti secara garis besar

Pembuktian dilakukan dengan kontradiksi.

Misalkan algoritma tersebut menghasilkan sebuah tree T, dan terdapat sebuah spanning tree S

dengan total bobot lebih kecil dari T. Misalkan e sebuah edge dengan bobot terkecil yang ada di T,

tapi tidak di S.

Gambar 8.3 Ilustrasi pembuktian teorwma 8.1

Kita menambah edge e ke S sehingga menciptakan sebuah cycle yang memuat e. Cycle ini

akan memuat edge 𝑒′ yang tidak ada di T. Suatu subgraph, misalnya 𝑆′ dapat dihasilkan dari S

dengan mengganti 𝑒′ dengan e adalah juga sebuah spanning tree. Karena e sebuah edge dengan

bobot terkecil, maka bobot e tidak bisa melebihi bobot 𝑒′. Sehingga bobot total dari 𝑆′ tidak dapat

melebihi bobot total dari S.

Dengan mengulang prosedur ini, kita dapat mengganti S menjadi T dengan mengganti satu

edge pada satu tahap, dengan bobot yang tidak meningkat pada setiap tahapnya. Ini menunjukan

bahwa total bobot T tidak melebihi total bobot S. Sehingga ini kontradiksi dengan definisi S.

9

Travelling Salesman Problem (TSP)

TSP pertama muncul dalam bidang matematika pada Princeton University tahun 1930-an.

Sebelumnya kita telah mengenal masalah TSP, di mana seorang salesman ingin mengunjungi

sejumlah kota dan kembali ke kota asal, dengan total jarak seminimal mungkin. Kita dapat

memodelkan masalah ini dalam sebuah graph komplit berbobot. Tujuan kita adalah menemukan

sebuah cycle dengan total bobot minimal yang melewati semua vertex, atau dengan kata lain, kita

mencari sebuah cycle Hamilton dengan bobot minimal.

Travelling Salesman Problem Diberikan sebuah graph komplit berbobot, temukan cycle Hamilton dengan bobot minimal pada graph tersebut.

Algoritma Kruskal dan algoritma Prim adalah algoritma yang sederhana untuk menyelesaikan

masalah minimum connector. Kita mungkin menginginkan terdapat algoritma yang sederhana juga

untuk menyelesaikan TSP. Sayangnya, belum ada algoritma yang efisien untuk menyelesaikan TSP.

Tentu kita dapat mencoba semua cycle Hamilton yang mungkin, namun hal itu adalah tugas yang

sulit, walaupun diselesaikan oleh komputer, kecuali vertex yang ada berjumlah sedikit. Untuk TSP

yang melibatkan 100 kota, akan ada 12(99!) = 4,65 x 10155 cycle. Oleh karena itu, kita terpaksa

melihat solusi pendekatan (approximate solutions) dari masalah tersebut, yaitu mencari batas atas

dan batas bawah untuk panjang cycle Hamilton yang memiliki bobot minimum.

Batas Atas TSP

Sekarang kita akan mempelajari sebuah algoritma heuristic untuk TSP, yang merupakan

algoritma yang tidak perlu memberikan sebuah jawaban yang tepat, namun memberikan sebuah

pendekatan yang baik. Ide penyelesaian masalah ini adalah dengan membangun cycle yang diminta

langkah demi langkah, dimulai dengan satu vertex. Langkahnya sama dengan algoritma Prim, kecuali

bahwa kita akan membangun sebuah cycle bukan membangun sebuah tree.

Metode Menemukan Batas Atas untuk Solusi TSP Mulai dengan sebuah himpunan terbatas vertex, di mana setiap pasangan vertex dihubungkan dengan sebuah edge berbobot.

Langkah 1 Pilih sembarang vertex dan temukan vertex yang dihubungkan dengannya dengan sebuah bobot minimal. Gambar kedua vertex dan hubungkan dengan dua edge untuk membentuk sebuah cycle. Berikan cycle tersebut arah searah jarum jam.

Langkah 2 Temukan vertex yang belum digambar, yang dihubungkan dengan edge dengan bobot minimal ke vertex yang sudah ada di gambar.

10

Ulangi langkah 2 sampai semua vertex terhubung dengan sebuah cycle, lalu berhentilah. Cycle berbobot yang diperoleh adalah cycle Hamilton dan total bobotnya (jumlah bobot dari semua edge) adalah batas atas dari solusi TSP.

Catatan :

Pilihan yang berbeda dari vertex awal dapat menyebabkan batas atas yang berbeda. Batas atas yang

terbaik adalah batas atas yang terkecil, karena ini memberikan informasi lebih baik dari solusi

sebenarnya.

Contoh 8.4

Temukan batas atas dari solusi TSP untuk enam kota berikut.

Vertex pertama Kita mulai dengan memilih sembarang vertex. Misal kita pilih Berlin.

Vertex kedua Kota yang paling dekat dengan Berlin adalah London atau Paris dengan jarak 7. Mari kita pilih London. Kita gambar dua vertex dan dua edge yang menghubungkan mereka, dan beri sebuah cycle dengan arah searah jarum jam.

Vertex ketiga Kota yang paling dekat dengan Berlin dan London adalah Paris dengan jarak 3 dari London. Kita menyisipkan Paris di depan London pada cycle.

Vertex keempat Kota yang terdekat dengan Berlin, London dan Paris adalah Seville dengan jarak 8 dari Paris. Kita menyisipkan Seville di depan Paris pada cycle.

11

Vertex kelima Kota yang terdekat dengan Berlin, London, Paris dan Seville adalah Roma dengan jarak 9 dari Paris. Kita menyisipkan Roma di depan Paris pada cycle.

Vertex keenam Kota terakhir adalah Moscow, yang paling dekat dengan Berlin dengan jarak 11. Kita sisipkan Moscow di depan Berlin pada cycle.

Semua kota kini telah terhubung dengan cycle : Berlin-Moscow-London-Paris-Rome-Seville-

Berlin. Batas atas dari solusi yang dicari 11+18+3+9+13+15=69

Latihan 8.4 Pada contoh 8.4, batas atas seperti apa yang dihasilkan jika kita memulainya dengan Rome?

Batas Bawah TSP

Metode lain untuk menentukan pendekatan solusi untuk TSP, yang sering bekerja dengan

baik dalam masalah praktis, adalah dengan menemukan batas bawah total bobot cycle Hamilton

dengan bobot minimum. Metode ini dilakukan dengan menyelesaikan sebuah masalah minimum

connector yang berkaitan dengan masalah tersebut. Walaupun kita tidak menghasilkan sebuah

pendekatan rute, kita dapat mengetahui bahwa panjang cycle yang menjadi solusi yang benar tidak

boleh melewati batas bawah ini.

Gambar 8.4 Ilustrasi pencarian patas bawah solusi TSP

Kita ilustrasikan metode tersebut dengan graph pada Gambar 8.4. Jika kita mengambil

sebuah cycle Hamilton dengan bobot minimal pada graph komplit ini dan menghapus vertex A dan

semua edge yang insiden dengannya, maka kita mendapatkan sebuah path yang melewati vertex

yang tersisa.

12

Path seperti ini adalah spanning tree untuk graph komplit yang dibentuk dengan vertex yang

tersisa dan bobot cycle Hamilton yang diinginkan diperoleh dengan menambahkan bobot spanning

tree dengan bobot dua buah edge yang insiden dengan A. Dalam hal ini, berlaku pertidaksamaan

berikut.

Total bobot cycle Hamilton dengan bobot minimal

≥ Total bobot dari spanning

tree D,C,D,E yang terhubung +

jumlah bobot dua edge yang insiden dengan A

Sehingga batas bawah dari solusi TSP pada kasus ini adalah total bobot dari spanning tree

D,C,D,E yang terhubung ditambah jumlah bobot dua edge yang insiden dengan A. Secara umum,

kita dapat mengeneralisir bentuk dari pertidaksamaan ini untuk batas bawah untuk setiap TSP,

sebagai berikut.

Metode Menemukan Sebuah Batas Bawah untuk Solusi TSP

Langkah 1 Pilih sebuah vertex v dan hapus vertex tersebut dari graph Langkah 2 Temukan minimum spanning tree yang menghubungkan vertex yang tersisa, dan hitung total bobotnya sebagai w. Langkah 3 Temukan dua bobot terkecil, w1 dan w2, dari edge yang insiden dengan v. Langkah 4 Hitung batas bawah sebagai w+w1+w2.

Catatan :

Pilihan vertex awal yang berbeda, dapat menghasilkan batas bawah yang berbeda. Batas bawah

yang paling baik adalah batas bawah terbesar karena lebih memberi informasi tentang solusi

sebenarnya.

Contoh 8.5

Kita akan menemukan batas bawah untuk TSP pada graph berbobot berikut.

Kita mulai dengan menghapus sebuah vertex sembarang. Misal kita memilih vertex A. Maka

graph berbobot yang tersisi memiliki empat vertex B,C,D,E.

13

Minimum spanning tree yang menghubungkan vertex ini adalah tree dengan edge ED, CE, BC

dengan bobot total 7+4+5 =16. Dua edge dengan bobot terkecil yang insiden dengan A adalah AE

dan AC dengan bobot 2 dan 4. Sehingga diperoleh solusi batas bawah = 16+2+4 = 22.

Solusi sebenarnya dari masalah ini adalah cycle ACBDEA dengan total bobot 26, sehingga

batas bawah yang kita hasilkan belum memberikan pendekatan yang baik. Sebuah batas bawah yang

lebih baik (yang lebih besar dan lebih mendekati solusi yang benar) dapat diperoleh dengan

menghapus titik D bukan A. Pada kasus ini graph berbobot yang tersisa memiliki empat vertex

A,B,C,E dan memiliki dua minimum spanning tree yang menghubungkan vertex tersebut, dengan

total bobot = 2+4+5=11.

Dua edge dengan bobot terkecil yang insiden dengan D adalah DE dan DA atau DE dan DB

dengan bobot 7 dan 8. Sebuah batas bawah yang lebih baik dihasilkan yaitu 11+7+8=26, yang

ternyata merupakan solusi yang sebenarnya.

Pada contoh yang sudah tersebut, kita menemukan minimum spanning tree dengan

memeriksa diagram dengan vertex yang dihapus. Namun, untuk contoh yang lebih besar, suatu

diagram menjadi tidak efektif, dan lebih mudah bagi kita untuk mencari minimum spanning tree

dengan memakai algoritma Kruskal atau algoritma Prim.

Latihan 8.5 Pada contoh 8.5, batas bawah seperti apa yang dihasilkan jika pada langkah pertama kita menghapus : a. Vertex B? b. Vertex E? Batas bawah mana yang lebih bagus?