Modul Paa

MODUL PENGANTAR ANALISIS ALGORITMA

Disusun Oleh:

Drs. Janoe Hendarto, M.Kom

ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS GADJAH MADA YOGYAKARTA 2007

DAFTAR ISI

DAFTAR ISI.......................................................................................................................... 2 BAB I PENDAHULUAN...................................................................................................... 3 BAB II UKURAN EFISIENSI ALGORITMA .................................................................... 6 BAB III TEKNIK PERANCANGAN ALGORITMA YANG EFISIEN............................ 11 BAB IV ANALISIS ALGORITMA PADA MASALAH SORTING................................. 15 BAB V ANALISIS ALGORITMA PADA MASALAH GRAF......................................... 21

2

BAB I PENDAHULUAN
Review Algoritma Algoritma adalah Kumpulan atau himpunan langkah-langkah yang berhingga untuk menyelesaikan masalah dengan menggunakan komputer, dengan aturan:  Setiap step/langkah harus DEFINITE (pasti). X ← x + (1 atau 2) // Undefinite x ← x + (Random(2) + 1) //Definite  Minimum mempunyai 1 buah Output (Input boleh tidak ada).  Harus ada Stoping Criteria atau dengan kata lain, harus bisa berhenti. X ← 0 Repeat write (x) x ← x + 2 until x = 15 //tidak berhenti, jadi stoping criterianya salah

Komponen/Langkah-langkah dari suatu Algoritma bisa berupa :  Satetment Output / Input write (x) return x print x cetak(x) 



read(x) input x scan x baca(x)

Operasi(Process) Operasi Dasar : • Aritmatik ( * , / , Mod, Div, +, - ) • Relasi ( <, >, ≤, ≥, =, ≠ ) • Logika ( and, or, not ) • Assignment ( ← ) Pengendali Proses  Percabangan : If, If .... else, case  Perulangan : For, While, Repeat .... Until.


Tahapan Penyelesaian Masalah Komputer diciptakan untuk membantu menyelesaikan masalah manusia. Masalah yang dimaksud tentunya masalah yang dapat diselesaikan dengan menggunakan computer ( computerize problems ). Adapun secara umum, langkah-langkah penyelesaian masalah dengan komputer adalah sebagai berikut :

3

MASALAH

ANALISIS MASALAH

PERANCANGAN ALGORITMA

MENURUNKAN / TO DEVICE MENYATAKAN /TO EXPRESS MENVALIDASI / TO VALIDATE MENGANALISIS / TO ANALYZE

PEMBUATAN PROGRAM KOMPUTER

UJI HASIL PROGRAM DAN DOKUMENTASI

PENYELESAIAN/ SOLUSI MASALAH Analisis algoritma adalah salah satu tahapan dari perancangan algoritma, Sedangkan perancangan algoritma adalah salah satu tahapan dari proses pemecahan masalah dengan komputer. Sebelum pembahasan analisis algoritma, terlebih dahulu kita bahas tahapan pemecahan masalah dengan komputer. Jadi untuk memecahkan masalah/problem dengan menggunakan komputer, diperlukan tahapan sebagai berikut : •

Analisis Masalah (40%) Analisis masalah adalah kegiatan mempelajari, mendalami masalah hingga mendapatkan ide-ide penyelesaian masalah (ide global).

•

Perancangan Algoritma (30%) Perancangan algoritma adalah pembuatan algoritma dimulai dari ide-ide penyelesaian masalah hingga terciptanya algoritma dalam bentuk standar (a.l. pseudocode).

4

•

Pembuatan Program Komputer (20%) Mentransfer algoritma menjadi kode program, yang sebelumnya perlu ditentukan struktur datanya.

•

Pengujian Hasil Program (5%) Running program untuk mengetahui apakah ada kesalahan, baik kesalahan sintax, running atau output/hasil.

•

Pembuatan Dokumentasi Program (5%) Pembuatan dokumentasi meliputi dokumentasi dalam program atau manual petunjuk pemakaian dan pemeliharaan program.

Jadi mengapa algoritma perlu dianilisis, untuk mengetahui kelayakan diteruskan pembuatan programnya atau tidak. Juga dapat digunakan untuk mengetahui/memprediksi waktu dan memory dari suatu algoritma.

5

BAB II UKURAN EFISIENSI ALGORITMA 1. Efisiensi Waktu Efisiensi untuk suatu algoritma tidak diukur dengan satuan waktu (detik, milidetik, dsb), karena waktu tempuh suatu algoritma sangat bergantung pada : • banyaknya data  problem size • spesifikasi komputer  Hardware (RAM, processor, dll) • compiler  software • tegangan listrik  contoh kasusnya, pemakaian notebook menggunakan daya baterai juga berpengaruh pada waktu tempuhnya karena kerja processor dapat dikatakan kurang normal. • Dll.  programmer Efisiensi waktu algoritma diukur dalam satuan n (problem size). 4 langkah untuk menentukan ukuran efisiensi waktu, antara lain : a). Menentukan problem size (n) Problem n Max/min/rata-rata Sorting/Searching n = banyaknya data Perkalian 2 matriks

A

x

pxq

B

n = max (p, q, r)

qxr Graf

banyaknya titik |v|

|v| = 4 |E| = 6

n banyaknya garis |E|

Pengolahan citra w misal : 800 x 600

h

n = banyaknya titik (w, h) w x h n h w x h 8x6

b). Menentukan operasi dominan Operasi dominan yang dimaksudkan di sini sangat bergantung pada permasalahan, dan operasi yang dilakukan yang banayaknya bergantung pada n, dengan kata lain operasi dominan merupakan operasi yang paling banyak dilakukan, sesuai konteks permasalahan.

6

Contoh : - pada algoritma menentukan max/min  operasi dominannya adalah operasi perbandingan “<” atau “>” - pada algoritma searching  operasi dominannya adalah operasi “=” - pada algoritma sorting  operasi dominannya adalah operasi “<” atau “>” operasi yang lain seperti “” tidak dominan, karena belum tentu terjadi penukaran atau perpindahan (contoh kasus : jika data yang diinputkan sudah dalam keadaan terurut) - pada algoritma menentukan rata-rata  operasi dominannya adalah penjumlahan (+) - pada algoritma perkalian 2 matriks  operasi dominannya adalah perkalian, sedangkan operasi dominan yang keduanya (2nd dominant operation) adalah penjumlahan atau pengurangan - pada algoritma menentukan modus  operasi dominannya adalah pembandingan “<” atau “>” yang terjadi dalam proses pengurutan, lalu diikuti dengan operasi dominan yang keduanya (2nd dominant operation) adalah pembandingan “=” yang terjadi dalam proses menghitung frekuensi dari masing-masing data c). Menentukan fungsi langkah  g(n) g(n) = banyak kali operasi dominan dilakukan (dalam n) contoh : max  x(1) ; min  x(1) ; for i = 2 to n do if x(i) > max then max  x(i) g(n) = n – 1 max  x(1) ; min  x(1) ; for i = 2 to n do if x(i) > max then max  x(i) if x(i) < min=then x(i)– 2 g(n) 2 (n min – 1)  = 2n max  x(1) ; min  x(1) ; for i = 2 to n do if x(i) > max then max  x(i) else . . . if x(i) < min then min  x(i) n – 1 ≤ g(n) ≤ 2n – 2 pada contoh algoritma di atas, diperoleh keadaan best case, yakni ketika data teurut ascending ; dan sebaliknya akan diperoleh keadaan worst case, yakni ketika data terurut descending atau data terbesar berada di X(1). d). Menentukan kompleksitas waktu O(f(n)) (Big Oh function) Suatu algoritma dengan fungsi langkah g(n) dikatakan mempunyai kompleksitas waktu O(f(n)) jika terdapat konstanta c>0 sedemikian hingga : g(n)≤cf(n) untuk n>n0 Algoritma MaxMin, CountingSort  g(n) = 2n-2 Algoritma BubbleSort  g(n) = n2/2-n/2

 Ο(n) Linear  O(n2) Kwadratis

7

Algoritma Perkalian 2 matrix nxn Algoritma MergeSort, QuickSort

•

 g(n) = n3 + kn 

 O(n3) Kubik O(nlogn) Logaritmis

Soal Quiz : Tentukan g(n) dan Big Oh function dari algoritma di bawah ini ! k=n while k > 0 do begin for i = 1 to n do if (x > 0) then . . . . k = k div 2 end Jawaban : g(n) = n log n + 1 O(n log n) Memahami kompleksitas waktu O(f(n) Ketika diadakan percobaan untuk mengetahui waktu tempuh beberapa algoritma dengan berbagai jumlah data yang bervariasi, diperoleh data sebagai berikut : Waktu tempuh algoritma menentukan max/min berbanding lurus dengan banyaknya data. N waktu tempuh 1.000.000 20 2.000.000 40 4.000.000 80 * waktu tempuh dalam milidetik pada O(n), yang bersifat linear, diketahui semakin besar jumlah datanya, akan semakin stabil linearitasnya. Contoh kasus : Algoritma menentukan max/min Waktu tempuh Waktu tempuh n (menggunakan else) (tanpa else) 1.000.000 10 10 10.000.000 120 110 20.000.000 150 120 30.000.000 220 170 40.000.000 290 220 50.000.000 360 290 100.000.000 720 560 Prediksi 1 Milyar 7200 5600 * waktu tempuh dalam milidetik Algoritma kuadratik n Sekuensial Bubble 10.000 580 460 20.000 1.890 1.800 30.000 4.000 4.095 40.000 6.900 7.260 50.000 10.435 11.325 100.000 36.200 45.415 Prediksi 1.000.000 3.620.000 4.541.500 * waktu tempuh dalam milidetik

8

Pada algoritma perkalian 2 matriks  g(n) = n pangkat 3 N waktu tempuh 100 40 200 320 300 730 400 1.762 500 3.425 600 5.850 700 9.160 800 13.760 900 19.360 1.000 26.380 * waktu tempuh dalam milidetik 2. Efisiensi Memory/Space Yaitu menentukan besar memory yang diperlukan oleh suatu algoritma. Kebutuhan memory (space) suatu algoritma juga tidak bisa diukur dalam satuan memory (byte, KB), karena kebutuhan memory yang sebenarnya bergantung dari banyak data dan struktur datanya. Kebutuhan memory dari suatu algoritma diukur dalam satuan problem size n. pertambahan memory terhadap n g(n) = banyak memory yang digunakan dalam n

Dalam algoritma menentukan max/min, g(n) = n + 2, f(n) = n Dalam algoritma sorting menggunakan teknik bubble/sekuensial, g(n) = n + 1, f(n) = n Dalam algoritma perkalian 2 matriks, g(n) = 3n2, f(n) bersifat kuadratis Jadi : Algoritma MaxMin  kompleksitas memorynya linear Algoritma BubbleSort  kompleksitas memorynya linear Algoritma Perkalian 2 matrix nxn  kompleksitas memorynya kwadratis 3. Kemudahan Implementasi Maksud dari kemudahan implementasi di sini adalah mengukur seberapa mudah/sederhana algoritma tersebut dibuat programnya, hal ini bisa dilihat dari teknik perancangannya atau struktur data yang digunakan. Biasanya sering digunakan dalam membandingkan suatu algoritma dengan algoritma lainnya, dan bukan diukur dengan tingkatan seperti sulit, mudah, atau pun sedang. Misalnya, bila kita membandingkan algoritma sekuensial sort dengan quick sort, ternyata algoritma sekuensial sort lebih mudah , karena quicksort menggunakan teknik devide & conquer. Pigeonhole Sort lebih mudah dibandingkan dengan Radix Sort, karena Radix Sort menggunakan queue. 9

4. Data Movement (khusus untuk masalah sorting ) Unsur ini berusaha mencari tahu banyaknya peristiwa perpindahan atau penukaran yang terjadi pada suatu algoritma sorting. Untuk mengetahui data movement ini kadang-kadang menemui kesulitan, karena mungkin tidak pasti atau mungkin diperlukan perhitungan dan penyelidikan yang lebih lanjut. 5. Stabilitas (khusus untuk masalah sorting ) Algoritma dapat bersifat stabil atau tidak stabil. Stabilitas suatu algoritma dapat dilihat dari kestabilan index data untuk data yang sama. Contoh : 7

9a

4

9b

1

9c

Index : 1 2 3 4 5 6 Setelah mengalami proses pengurutan, algoritma tersebut akan disebut stabil, jika data menjadi : 1

4

7

9a

9b

9c

Index : 5

3

1

2

4

6

10

BAB III TEKNIK PERANCANGAN ALGORITMA YANG EFISIEN 1.

Devide and Conquer

Contoh: Masalah menentukan Max dan Min dari n data : Pseudocode Procedure MaxMin(x, awal, akhir, Max, Min) Begin if akhir-awal ≤ 1 then if x(awal) ≥ x(akhir) then Max ← x(awal), Min ← x(akhir) else Max ← x(akhir), Min ← x(awal) else Begin Mid ← (awal + akhir) DIV 2 MaxMin(x, awal, mid, Max1, Min1) MaxMin(x, mid+1, akhir, Max2, Min2) if Max1 ≥ Max2 then Max ← Max1 else Max ← Max2 if Min1 ≤ Min2 then conquer Min ← Min1 else Min ← Min2 end end MaxMin dengan metode biasa → g(n)= 2n-1

devide

MaxMin dengan metode devide and conquer → g(n)=

Rekursif conquer

11

Mencari g(n) N

g(n)

2

1

4

2g(2)+2 = 4

8

2.4+2 = 10

16

2.10+2 = 22

32

2.22+2 = 46

64

2.46+2 = 94

n

n−2

Contoh lain: Algoritma Perkalian 2 Bilangan Besar n Digit Misal n=4 x = 6789 y = 2476 x z = ......... ? • • •

Problem Size = n Operasi Dominan = perkalian algoritma biasa g(n) = n2 + cn → O(n2) Dengan metode devide and conquer a=67 b=89 x=67*102 + 89 = a.10n/2 + b x a b c=24 d=76 y=24*102 = 76 = c.10n/2 + d y c d z = .... z = x.y = (a.10n/2 + b).(c.10n/2 + d) z = ac.10n + (ad+bc) 10n/2 + bd g(n) = 4g( ) + cn → O(n2) →berdasarkan teorema 4 kali rekursif (ac, ad, bc, bd) O(n2) tidak berubah menjadi lebih efisien, maka conquer perlu diubah pseudo code Begin u ← (a+b).(c+d) v ← ac w← bd z ← v.10n + (u–v−w) 10n/2 + w End maka g(n)= 3g( ) + cn

→ O(nlog 3) = O(n1,59)

TEOREMA MENCARI O(f(n)) untuk METODE DEVIDE AND CONQUER

12

jika g(n) =

maka g(n) =

2. Dynamic Programming Diselesaikan mulai data yang kecil. n = 1 → solusi = s1 n = 2 → solusi = s2 (menggunakan s1) n = 3 → solusi = s3 (menggunakan s1, s2) . . n = k → solusi = sk (menggunakan s1, s2, ..., sk-1) . . n → sn Contoh dynamic programming perkalian n matriks misal n=4 M = M1(10x20) . M2(20x50) . M3(50x1) . M4(1X100) cara 1 M1( M2 ( M3 . M4)) 50x1x100 = 5000 20x50x100 = 100.000 10x20x100 = 20.000 + 125.000 perkalian cara 2 (M1(M2 . M3) )M4 20x50x1 = 1000 10x20x1 = 200 10x1x100 = 1000 + 2200 perkalian →minimum, how? Algoritma untuk menentukan banyaknya operasi perkalian yang minimum input r0, r1, r2, ......, rn (r0=10, r1=20, r2=50, r3=1, r4=100) output m1n = min operasi perkalian yang terjadi untuk M1.....Mn (M14=2200) • Algoritma biasa 1. Cari semua kemungkinan x1, x2, x3, ....., xk 2.tentukan yang minimum Operasi dominan = perbandingan g(n)=k-1 → O(k) → O(2n) • Algoritma Dynamic programming

13

Begin

For i=0 to n do Read (ri ) For i=1 to n do mii  0 For p=1 to n-1 do For i= 1 to n-p do ji+p mij  MIN (mik + mk+1 j + ri-1 rk rj ) i≤k<j Return m1n end 3. ALGORITMA GREEDY A. Definisi Sesuai dengan namanya (greedy = rakus, serakah), greedy algorithms adalah kelompok algoritma yang selalu mengambil penyelesaian sementara/lokal yang terbaik dalam setiap langkahnya untuk menyelesaikan permasalahan. Pilihan terbaik akan diambil pada setiap langkah tanpa perlu memikirkan bagaimana pengaruhnya terhadap penyelesaian secara keseluruhan. Harapannya adalah bahwa dengan memilih penyelesaian optimal dalam setiap langkah, pada akhirnya bisa didapatkan penyelesaian menyeluruh secara optimal pula. Algoritma greedy biasanya merupakan algoritma yang paling mudah diterapkan. Algoritma ini mudah diciptakan, mudah diimplementasikan, dan efisien (cepat dalam implementasi). Meskipun demikian, tidak ada jaminan bahwa algoritma greedy bisa menyelesaikan semua permasalahan dengan optimal. B. Contoh : The Knapsack Problem Ada beberapa versi dari masalah klasik ini. Salah satunya bisa diilustrasikan sebagai berikut. Diberikan n objek dan sebuah ransel (-knapsack). Masing-masing objek i mempunyai berat wi dan vi. Ransel tersebut bisa memuat objek maksimal seberat W. Masalah yang harus dipecahkan adalah bagaimana mengisi ransel dengan objek yang nilai maksimal tanpa melewati batas kapasitas dari ransel. Dalam versi ini, diasumsikan bahwa masing-masing objek dapat dibagi menjadi bagian yang lebih kecil, sehingga kita dapat memutuskan untuk hanya membawa sebagian objek i sebanyak x1. Dengan demikian, algoritma untuk masalah ini dapat disusun sebagai berikut. n adalah jumlah objek wi adalah variabel yang menyatakan berat dari objek i, vi adalah variabel yang menyatakan nilai dari objek i, xi adalah pecahan yang menyatakan beberapa bagian dari objek i yang dimasukkan dalam ransel. Variabel berat menyatakan jumlah berat objek yagn sudah dimasukkan dalam ransel, sedangkan W adalah kapasitas dari ransel.  Inisiasi i. Untuk setiap i, set xi = 0 ii. Set berat = 0  Selama berat < W lakukan i. Pilih i, yaitu objek yang paling potensial (lihat keterangan di bawah) dari objek yang tersisa. ii. Jika berat + wi ≤ maka xi = 1 Berat = berat + wi Jika tidak maka xi = (W – berat) / wi berat = W

14

BAB IV ANALISIS ALGORITMA PADA MASALAH SORTING Radix Sort Dari segi algoritma radix sort merupakan sebuah algoritma pengurutan yang mengatur pengurutan nilai tanpa melakukan beberapa perbandingan pada data yang dimasukkan. Radix dapat diartikan sebagai posisi dalam angka. Nama lain dari radix sort adalah bucket sort ALGORITMA RADIX SORT For k = “0” to “9” do Initqueue (AQ[k]) For i = 1 to n do Enqueue(AQ[X[i]], x[i]) For k = “0” to “9” do While AQ[k] <> Nil Dequeue (AQ[X[i]], x[i]) Analisis: Bucket sort memerlukan waktu О(n) LEXICOGRAPHIC SORT

15

Stable sort yang paling banyak digunakan pada lexicographic sort adalah radix sort / bucket sort. Kompleksitas waktu lexicographic sort adalah О(dT(n)) dimana T(n) adalah kompleksitas waktu stable sort yang digunakan. Menggunakan Bucket Sort, Kompleksitas waktu bucket sort: О(n) Kompleksitas waktu lexicographic sort: g(n)=dn → О(n) Jika menggunakan queue dinamis (linked list) Data = n Kompleksitas memory = n Jika menggunakan queue statis Data = n Kompleksitas memory = m*n Dimana m = jumlah queue

Problem Size (n) = Banyaknya Data

Waktu (dalam milisecond)

100.000

16

200.000

32

500.000

47

600.000

62

900.000

78

1.000.000

94

PIGEONHOLE SORT Pigeonhole merupakan Suatu teknik penyortiran dengan cara mengalokasikan array sejumlah data yang terbesar. Sehubungan dengan alamat array berupa bilangan bulat maka data yang bisa diolah dengan teknik ini adalah berupa bilangan bulat. ALGORITMA PIGEONHOLE SORT For k = 0 To m Hole(k)  0 For i = 1 To n k  Bilangan(i) Hole(k)  Hole(k) + 1 j=1 For k = 0 To m While Hole(k) <> 0 bilangan(j)=k j  j+1 Hole(k)  Hole(k) – 1

16

JUMLAH DATA (n)

RADIX SORT

PIGEONHOLE SORT

10

0.015625

0.03125

20

0.015625

0.03125

50

0.03125

0.046875

100

0.03125

0.03125

200

0.078125

0.046875

500

0.25

0.0625

1000

0.578125

0.109375

1500

1.015625

0.140625

2000

1.640625

0.15625

5000

7.828125

0.375

10000

33.53125

0.71875

50000

1268.719

3.65625

Mergesort Vs Quicksort Mergesort  Devide & conquer approach  Menggabungkan 2 sorted array  Rekursif Algoritma void mergeSort(int numbers[], int temp[], int array_size) { m_sort(numbers, temp, 0, array_size - 1); } void m_sort(int numbers[], int temp[], int left, int right) { int mid; if (right > left) { mid = (right + left) / 2; m_sort(numbers, temp, left, mid); m_sort(numbers, temp, mid+1, right); merge(numbers, temp, left, mid+1, right); } } void merge(int numbers[], int temp[], int left, int mid, int right) { int i, left_end, num_elements, tmp_pos;

17

left_end = mid - 1; tmp_pos = left; num_elements = right - left + 1; while ((left <= left_end) && (mid <= right)) { if (numbers[left] <= numbers[mid]) { temp[tmp_pos] = numbers[left]; tmp_pos = tmp_pos + 1; left = left +1; } else { temp[tmp_pos] = numbers[mid]; tmp_pos = tmp_pos + 1; mid = mid + 1; } } while (left <= left_end) { temp[tmp_pos] = numbers[left]; left = left + 1; tmp_pos = tmp_pos + 1; } while (mid <= right) { temp[tmp_pos] = numbers[mid]; mid = mid + 1; tmp_pos = tmp_pos + 1; } for (i=0; i <= num_elements; i++) { numbers[right] = temp[right]; right = right - 1; } } Kompleksitas waktu  O(n log n) Memory yang digunakan  Array untuk input : n  Array untuk merging : n  Total : 2n Mergesot  stabil karena data yang sudah terurut, tidak berubah posisi meski dilakukan pengurutan saat data digabungkan

18

Mergesort Analisis 2 2

7 7

1 1

5

3

4

5

3

8 4

6 8

6

O(log n) * O(n)=O(n log n)

2

7

1

5

3

4

8

6

2

7

1

5

3

4

6

8

1

2

2

5

7

7

1

3

5

3

4

4

6

8

8

log n

6

n-1

Quicksort  Devide & conquer approach  Rekursif  Menggunakan pivot Algoritma : void quickSort(int numbers[], int array_size) { q_sort(numbers, 0, array_size - 1); } void q_sort(int numbers[], int left, int right) { int pivot, l_hold, r_hold; l_hold = left; r_hold = right; pivot = numbers[left]; while (left < right) { while ((numbers[right] >= pivot) && (left < right)) right--; if (left != right) { numbers[left] = numbers[right]; left++; } while ((numbers[left] <= pivot) && (left < right)) left++; if (left != right) { numbers[right] = numbers[left]; right--; } }

19

numbers[left] = pivot; pivot = left; left = l_hold; right = r_hold; if (left < pivot) q_sort(numbers, left, pivot-1); if (right > pivot) q_sort(numbers, pivot+1, right); } Kompleksitas waktu  Worst case : O(n2)  Best case : O(nlog n)  Average case : O(n log n) Memory yang digunakan  n (karena tidak menggunakan external array) Quicksort  tidak stabil karena pembanding (pivot) selalu berubah-ubah, sehingga ada kemungkinan untuk data yang nilainya sama dengan pivot akan berubah posisi

Quicksort

Data movement :

Worst case

  



Worst case jika pivot elemen paling kiri atau paling kanan L atau G berukuran n-1 dan yang lain 0 Running time n+(n-1)+(n-2)+…+2+1 O(n2)

Kompleksitas waktu :

n Merge (s) 10.000 0 20.000 0,020 30.000 0,030 40.000 0,040 50.000 0,070

Quick (s) 0 0,010 0,030 0,040 0,050

Merge

Quick

n 10.000

280.000

66.085

20.000

600.000

140.645

30.000

900.000

221.325

40.000 1.280.000

304.365

50.000 1.600.000

385.947

Jumlah perbandingan :

n 10.000 20.000 30.000 40.000 50.000

Merge 123.696 267.316 410.455 574.734 733.088

Quick 153.395 359.559 535.850 703.030 941.386

20

BAB V ANALISIS ALGORITMA PADA MASALAH GRAF A. MASALAH SHORTEST PATH (LINTASAN TERPENDEK) Persoalan lintasan terpendek yaitu menemukan lintasan terpendek antara dua atau beberapa simpul lebih yang berhubungan. Biasanya direpresentasikan dalam bentuk graf berbobot (weighted graph), yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Bobot pada sisi graf dapat menyatakan jarak antar kota, waktu pengiriman pesan, ongkos pembangunan, dan sebagainya. Contoh-contoh terapan pencarian lintasan terpendek: 1. Misalkan simpul pada graf menyatakan kota, sedangkan sisi menyatakan jalan yang menghubungkan dua buah kota. Bobot sisi graf dapat menyatakan jarak antara dua buah kota atau rata-rata waktu tempuh antara dua buah kota. Apabila terdapat lebih dari satu lintasan dari kota A ke kota B, maka persoalan lintasan terpendek di sini adalah menentukan jarak terpendek atau waktu tersingkat dari kota A ke kota B. 2. Misalkan simpul pada graf menyatakan terminal komputer atau simpul komunikasi dalam suatu jaringan, sedangkan sisi menyatakan saluran komunikasi yang menghubungkan dua buah terminal. Bobot pada graf dapat menyatakan biaya pemakaian saluran komunikasi antara dua buah terminal, jarak antara dua buah terminal, atau waktu pengiriman pesan (message) antara dua buah terminal. Persoalan lintasan terpendek di sini adalah menentukan jalur komunikasi terpenek antara dua buah terminal komputer. Lintasan terpendek akan menghemat waktu pengiriman pesan dan biaya komunikasi. Beberapa macam persoalan lintasan terpendek antara lain: a. Lintasan terpendek antara dua buah simpul tertentu (a pair shortest path). b. Lintasan terpendek antara semua pasangan simpul (all pairs shortest path). c. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain (single-source shortest path). d. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu (intermediate shortest path). ALGORITMA SHORTEST PATH
Dijkstra
Floyd 1. Algoritma Dijkstra : Pencarian Lintasan Terpendek Algoritma Dijkstra merupakan salah satu contoh algoritma greedy. Algoritma ini digunakan untuk mencari jalur terpendek dari 1 titik tertentu (disebut titik asal) dalam sebuah graf berarah ke setiap titik lainnya. Contoh konkret dari permasalah pencarian jalur terpendek ini adalah mencari jalur terpendek yang menghubungkan kota tertentu dengan setiap kota yang lain pada suatu pulau. Prinsip dari algoritma Dijkstra adalah sebagai berikut : Diasumsikan bahwa titik asal adalah 1. S adalah himpunan yang berisi titik-titik yang jalurnya sudah diketahui. Jarak adalah panjang jalur yang menghubungkan 1 ke titik tertentu. Predesesor

21

menyimpan data titik yang dilalui sebelum titik yang bersangkutan dalam jalur yang menghubungkan titik 1 dengan titik tersebut.
Inisiasi i. Masukkan 1 ke dalam himpunan S. Set jarak 1 menjadi 0. Set jalur menjadi 1 sendiri. ii. Untuk setiap titik lain, set jaraknya sesuai dengan jarak antara titik 1 dengan titik tersebut. Untuk titik yang tidak bisa dicapai secara langsung dari titik 1, jaraknya adalah Predesesor dari masing-masing titik adalah 1.
Ulangi langkah-langkah berikut sampai semua titik masuk ke dalam S i. Carilah titik di luar S yang memiliki jarak terpendek, misalkan v ii. Masukkan titik v ke dalam S iii. Untuk setiap titik di luar S, jika jaraknya ke titik 1 dengan melewati v ternyata lebih pendek dari jarak semula, set jaraknya menjadi jarak 1 ke v ditambah dengan jarak v ke titik tersebut, dan set predesesornya menjadi v. Algoritma Dijkstra bisa dikategorikan sebagai algoritma greedy karena dalam setiap langkahnya selalu mencari titik di luar himpunan S yang memiliki jarak terpendek. Dengan pemilihan yang dianggap optimal pada setiap langkah ini, diharapkan akan didapatkan penyelesaian menyeluruh yang optimal pula. Pada kenyataannya, dapat dibuktikan bahwa Algoritma Dijkstra selalu menghasilkan penyelesaian optimal [3]. Pembuktian untuk teorema ini tidak dibahas disini.

Gambar 3 : Contoh graf berarah [4]

Tabel 2 memuat hasil setiap langkah penerapan algoritma Dijkstra untuk graf terarah pada Gambar 3. Jarak dan predesesor yang dicetak tebal merupakan jarak dan predesesor yang dipakai terakhir untuk setiap titik. Sedangkan jarak dan predesesor yang dicetak miring merupakan jarak dan predesesor yang mengalami perubahan karena pemilihan suatu titik ke dalam S. Tabel 2 : Hasil setiap langkah penerapan algoritma Dijkstra untuk Gambar 3 Langkah

Titik terpilih

Titik di luar S

S

Inisisasi

1

{2,3,4,5}

{1}

1

5

{2,3,4}

{1,5}

Jarak Jarak [1] = 0, Jarak [2] = 5, Jarak [3] = 3, Jarak [4] = ∞, Jarak [5] = 2,

Predesesor Pred [1] = 1, Pred [2] = 1, Pred [3] = 1, Pred [4] = 1, Pred [5] = 1

Jarak [2] = 5, Jarak [3] = 3, Jarak [4] = 6,

Pred [2] = 1, Pred [3] = 1, Pred [4] = 5,

22

2

3

{2,4}

{1,3,5}

Jarak [2] = 4, Jarak [4] = 5,

Pred [2] = 3, Pred [4] = 3,

3

2

{4}

{1,2,3,5}

Jarak [4] = 5,

Pred [4] = 3,

4

4

{}

{1,2,3,4,5}

-

-

2. ALGORITMA FLOYD  Input graf berarah dan berbobot (V,E), dimana : V = daftar titik (node/vertex) E = daftar sisi (edge).  Jumlah bobot sisi-sisi pada sebuah jalur adalah bobot jalur tersebut.  Sisi pada E diperbolehkan memiliki bobot negatif, akan tetapi tidak diperbolehkan bagi graf ini untuk memiliki siklus dengan bobot negatif.  Algoritma ini menghitung bobot terkecil dari semua jalur yang menghubungkan sebuah pasangan titik, dan melakukannya sekaligus untuk semua pasangan titik.  Salah satu varian dari pemrograman dinamis - Memandang solusi yang akan diperoleh sebagai suatu keputusan yang saling terkait. - Solusi-solusi dibentuk dari solusi yang berasal dari tahap sebelumnya dan ada kemungkinan solusi lebih dari satu. - Prinsip  prinsip optimalitas, yaitu jika solusi total optimal, maka bagian solusi sampai suatu tahap (misalnya tahap ke-i) juga optimal. Greedy Vs Dynamic Programming Greedy  keputusan yang diambil pada tiap tahap hanya berdasarkan pada informasi yang terbatas sehingga nilai optimum yang diperoleh pada saat itu, tidak memikirkan konsekuensi yang terjadi seandainya memilih suatu keputusan pada suatu tahap. Dalam beberapa kasus, algoritma greedy gagal memberikan solusi terbaik. Dynamic Programming  mencoba untuk memberikan solusi yang memiliki pemikiran terhadap konsekuensi yang ditimbulkan dari pengambilan keputusan pada suatu tahap. Pemrograman dinamis mampu mengurangi pengenumerasian keputusan yang tidak mengarah ke solusi. PSEUDOCODE Dasar algoritma: • Asumsikan semua simpul graf berarah G adalah V = {1, 2, 3, 4, ..., n}, perhatikan subset {1, 2, 3, ..., k}. • Untuk setiap pasangan simpul i, j pada V, perhatikan semua lintasan dari i ke j dimana semua simpul pertengahan diambil dari {1, 2, ..., k}, dan p adalah lintasan berbobot minimum diantara semuanya. • Algoritma ini mengeksploitasi relasi antara lintasan p dan lintasan terpendek dari i ke j dengan semua simpul pertengahan berada pada himpunan {1, 2, ..., k-1}. • Relasi tersebut bergantung pada apakah k adalah simpul pertengahan pada lintasan p.

23

Implementasi algoritma dalam pseudocode: (Graf direpresentasikan sebagai matrix keterhubungan, yang isinya ialah bobot / jarak sisi yang menghubungkan tiap pasangan titik, dilambangkan dengan indeks baris dan kolom) (Ketiadaan sisi yang menghubungkan sebuah pasangan dilambangkan dengan Takhingga) function fw(int[1..n,1..n] graph) { // Inisialisasi var int[1..n,1..n] jarak := graph var int[1..n,1..n] sebelum for i from 1 to n for j from 1 to n if jarak[i,j] < Tak-hingga sebelum[i,j] := i // Perulangan utama pada algoritma for k from 1 to n for i from 1 to n for j from 1 to n if jarak[i,j] > jarak[i,k] + jarak[k,j] jarak[i,j] = jarak[i,k] + jarak[k,j] sebelum[i,j] = sebelum[k,j] return jarak return path }

KOMPLEKSITAS WAKTU Algoritma ini berjalan dengan waktu O(V3) karena dalam algoritmanya kita lihat bahwa terdapat 3 iterasi / perulangan. Sebenarnya IF-nya terlalu banyak karena ada pasangan jarak yang seharusnya tidak perlu dihitung lagi. Misalnya jarak terpendek dari kota Jogja ke Jogja itu sendiri. Tidak mungkin jarak terpendeknya harus melewati kota Semarang terlebih dahulu. Pastilah jarak terpendeknya adalah 0. Tapi hal itu bisa diabaikan, karena jika itu dilakukan pun, kompleksitas waktunya tetap O(V3). KOMPLEKSITAS MEMORY Kompleksitas memory dari algoritma Floyd ini adalah O(2V2) karena kita membutuhkan 2 matriks. KEMUDAHAN • Algoritmanya sederhana dan mudah diimplementasikan • Hanya menggunakan array sehingga Floyd lebih mudah dibandingkan Dijkstra. CONTOH KASUS

24

 Lintasan terpendek dari kota A ke kota G? Berapakah jaraknya? B. MASALAH MINIMUM SPANNING TREE Algoritma Prim : Misalkan sebuah perusahaan telekomunikasi akan membangun jaringan telepon yang menghubungkan kota-kota pada sebuah pulau. Ini berarti bahwa harus ada minimal sebuah jalur yang menghubungkan sebuah kota dengan setiap kota yang lain. Biaya pemasangan jalur untuk setiap pasangan kota sudah ditetapkan. Tentu saja perusahaan tersebut ingin membangun jaringan dengan biaya serendah mungkin. Jika kota-kota direpresentasikan sebagai titik dalam graf (tentu saja jenis dari graf adalah graf tak berarah) dan biaya pemasangan adalah jarak antar titik, maka penyelesaian masalah ini berkorespondensi dengan penyusunan minimum spanning tree pada graf tersebut. Suatu graf bisa dicari minimum spanning tree-nya jika graf tersebut merupakan graf terhubung (connected graph). Algoritma Prim dapat diuraikan sebagai berikut : S adalah himpunan sisi yang sudah dimasukkan pada minimum spanning tree, sedangkan T adalah himpunan titik yang sudah dimasukkan pada minimum spanning tree.
Inisiasi i. Set S sebagai himpunan kosing ii. Ambil sembarang titik pada graf, masukkan pada T
Ulangi langkah-langkah berikut selama masih ada titik yang belum masuk T i. Carilah sisi e = (u, v) yang memiliki jarak paling pendek sedemikian hingga u adalah titik yang sudah masuk T, sedangkah v adalah titik yang belum masuk T. ii. Masukkan sisi e ke dalam s. iii. Masukkan titik v ke dalam B Algoritma Prim merupakan salah satu jenis algoritma greedy karena dalam setiap pemilihan sisi, selalu dipilih sisi terpendek yang menghubungkan salah satu titik pada T dengan titik di luar T. Algoritma Prim ternyata selalu menghasilkan penyelesaian optimal [3]. Pembuktian untuk teorema ini tidak akan dibahas disini.

Gambar 1 : Contoh graf tak berarah Tabel 1 berikut memuat hasil setiap langkah penerapan algoritma Prim untuk graf pada Gambar 1. Tabel 1 : Hasil setiap langkah penerapan algoritma Prim untuk Gambar 1 Langkah Inisiasi 1 2 3

Sisi Terpilih (1,5) (1,3) (2,3)

S {} {(1.5)} {(1,3), (1,5)} {(1,3), (1,5), (2,3)}

B {1} {1,5} {1,3,5} {1,2,3,5}

25

4

(3,4)

{(1,3), (1,5), (2,3), (3,4) }

{1,2,3,4,5}

Minimum spanning tree yang dihasilkan dari proses pada algoritma Prim tersebut ditunjukkan oleh Gambar 2.

Gambar 2 : Minimum Spanning Tree yang dihasilkan dari graf pada Gambar 1

Algoritma Kruskal Algoritma ini digunakan untuk mencari minimum spanning tree. Berbeda dengan algoritma Prim, algoritma Kruskal membentuk minimum spanning tree dengan menggabungkan komponen-komponen yang terpisah dari sebuah graf. Agar lebih mudah dalam implementasinya, graf sebaiknya direpresentasikan sebagai larik yang berisi sisi-sisi dalam graf, bersama dengan panjang sisi-sisi tersebut. Secara rinci, algoritma ini dapat dituliskan sebagai berikut n adalah jumlah titik pada graf. S adalah himpunan yang memuat sisi-sisi pada minimum spanning tree.  Inisiasi Dibentuk n himpunan, masing-masing berisi titik yang berbeda pada G. Himpunanhimpunan ini menggambarkan komponen-komponen yang terpisah pada graf. Set S sebagai himpunan kosong.  Ulangi sampai S memuat n-1 sisi a. Tentukan (u,v) sebagai sisi terpendek di luar S b. Tentukan u_kom, yaitu komponen yang memuat titik u c. Tentukan v_kom, yaitu komponen yang memuat titik v d. Jika u_kom ≠ v_kom, maka : i.Gabungkan u_kom dan v_kom ii.Masukkan (u,v) pada S Sebagai contoh, tabel berikut memuat implementasi algoritma Kruskal untuk Gambar 1. Tabel 3 : Hasil Setiap langkah penerapan algoritma Kruskal untuk Gambar 1 Langkah Inisiasi 1 2 3 4

Sisi Terpendek (2,3) (1,5) (3,4) (1,3)

Komponen {1}, {2}, {3}, {4}, {5} {1}, {2,3}, {4}, {5} {1,5}, {2,3}, {4} {1,5}, {2,3}, {4} {1,2,3,4,5}

S {} {(2,3)} {(1,5),(2,3)} {(1,5), (2,3),(3,4)} {(1.3),(1,5),(2,3),(3,4)}

Dapat dilihat bahwa pada kasus ini ternyata minimum spanning tree yang dihasilkan dengan algoritma Prim ternyata terdapat sebuah teorema yang menyebutkan bahwa pencarian minimum spanning tree dengan menggunakan algoritma Kruskal akan selalu

26

mendapatkan hasil yang optimal. Pembuktian untuk teorema ini tidak akan dibahas disini.

C. TRAVELLING SALESMAN PROBLEM (Topik Khusus) Penggambaran yang sangat sederhana dari istilah Traveling Salesman Problem (TSP) adalah seorang salesman keliling yang harus mengunjungi n kota dengan aturan sebagai berikut - Ia harus mengunjungi setiap kota hanya sebanyak satu kali. - Ia harus meminimalisasi total jarak perjalanannya. - Pada akhirnya ia harus kembali ke kota asalnya. Guna memudahkan permasalahan, pemetaan n kota tersebut akan digambarkan dengan sebuah graph, dimana jumlah vertex dan edge-nya terbatas (sebuah vertex akan mewakili sebuah kota dan sebuah edge akan mewakili jarak antar dua kota yang dihubungkannya). Penanganan problem TSP ini ekuivalen dengan mencari sirkuit Hamiltonian terpendek. Graph adalah sekumpulan objek yang disebut simpul (node atau edges dalam bahasa Inggris) yang dihubungkan oleh sambungan-sambungan yang disebut sebagai sisi (lines atau vertices). Dalam suatu graf (bila tidak didefinisikan, berarti graf yang dimaksud adalah graf tidak berarah, yaitu graf yang sisi-sisinya tidak mempunyai orientasi arah), suatu garis dari titik A ke titik B diasumsikan sama dengan garis dari titik B ke titik A. Pada graf berarah, kedua arah-arah tadi dihitung sebagai jalur yang berlainan. Umumnya, graf digambarkan pada diagram sebagai sekumpulan titik (yang mewakili simpul) dihubungkan oleh garis ataupun kurva (yang mewakili sisi). Terdapat suatu atribut tambahan yang seringkali melengkapi suatu graf yaitu bobot. Bobot merupakan label dari tiap sisi pada suatu graf. Bobot biasanya merupakan bilangan real. Namun, terkadang tergantung pemakaian, bobot akan dibatasi hanya untuk bilangan rasional atau bilangan integer. Beberapa algoritma tertentu memerlukan batasan tambahan dalam nilai bobot, misal algoritma Djikstra hanya bisa berfungsi dengan benar jika bobot graf bernilai positif. Bila sebuah graf disebut tanpa keterangan tambahan, biasanya graf tersebut tidak berbobot. Berikut ini adalah gambar graf tidak berarah dan graf berbobot:

Gambar 1. Graf tidak berarah Gambar 2. Graf berbobot Suatu alur Hamilton adalah suatu alur yang mengunjungi simpul masing-masing persisnya sekali. Suatu siklus Hamilton, sirkuit Hamilton, Perjalanan atau siklus graf adalah suatu siklus yang mengunjungi simpul masing-masing tepat sekali (kecuali simpul yang merupakan tujuan awal maupun akhir, sehingga dikunjungi 2 kali). Suatu graf yang berisi suatu siklus Hamilton disebut graf Hamilton. 2. Permasalahan Permasalahan yang akan dibahas pada paper ini adalah: 1. Analisis algoritma eksak (algoritma brute force) untuk pemecahan masalah Travelling Salesman Problem ditinjau dari efisiensi waktu, memory, dan kemudahan implementasi. 2. Analisis algoritma heuristik (algoritma genetik) untuk pemecahan masalah Travelling Salesman Problem ditinjau dari efisiensi waktu, memory, dan kemudahan implementasi. 27

ALGORITMA BRUTE FORCE 1. Algoritma Brute Force Definisi Brute Force : • Brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya didasarkan pada pernyataan masalah (problem statement) dan definisi konsep yang dilibatkan. • Algoritma brute force memecahkan masalah dengan sangat sederhana, langsung dan dengan cara yang jelas (obvious way). • Contoh-contoh penggunaan brute force: menghitung an (a > 0, n adalah bilangan bulat taknegatif), mengalikan dua matrik berukuran n x n, mencari elemen terbesar (atau terkecil). Karakteristik Algoritma Brute Force • Algoritma brute force umumnya tidak “cerdas” dan tidak mangkus, karena ia membutuhkan jumlah langkah yang besar dalam penyelesaiannya. Kadang-kadang algoritma brute force disebut juga algoritma naif (naïve algorithm). • Algoritma brute force seringkali merupakan pilihan yang kurang disukai karena ketidakmangkusannya itu, tetapi dengan mencari pola-pola yang mendasar, keteraturan, atau trik-trik khusus, biasanya akan membantu kita menemukan algoritma yang lebih cerdas dan lebih mangkus. • Untuk masalah yang ukurannya kecil, kesederhanaan brute force biasanya lebih diperhitungkan daripada ketidakmangkusannya. Algoritma brute force sering digunakan sebagai basis bila membandingkan beberapa alternatif algoritma yang mangkus. Seperti ucapan Ken Thompson (salah seorang penemu Unix), yang mengatakan: “When in doubt, use brute force”, faktanya kernel Unix yang asli lebih menyukai algoritma yang sederhana dan kuat (robust) daripada algoritma yang cerdas tapi rapuh. 2. Analisis Algoritma Brute Force Kami akan menganalisis algoritma eksak pada persoalan Traveling Salesman Problem (TSP) dan membandingkan dengan algoritma yang lain yaitu algoritma genetik yang termasuk dalam algoritma heuristik. Algoritma eksak yang digunakan adalah algoritma brute force dengan teknik exhaustive search. Exhaustive search adalah teknik pencarian solusi secara solusi brute force untuk masalah yang melibatkan pencarian elemen dengan sifat khusus. Biasanya di antara objekobjek kombinatorik seperti permutasi, kombinasi, atau himpunan bagian dari sebuah himpunan. Langkah-langkah metode exhaustive search : a. Enumerasi (list) setiap solusi yang mungkin dengan cara yang sistematis. b. Evaluasi setiap kemungkinan solusi satu per satu, mungkin saja beberapa kemungkinan solusi yang tidak layak dikeluarkan, dan simpan solusi terbaik yang ditemukan sampai sejauh ini (the best solusi found so far). c. Bila pencarian berakhir, umumkan solusi terbaik (the winner) d. Meskipun algoritma exhaustive secara teoritis menghasilkan solusi, namun waktu atau sumberdaya yang dibutuhkan dalam pencarian solusinya sangat besar. Contoh penggunaan exhaustive search/ backtracking :

28

Graph dengan n = 6 Berikut ini adalah langkah pencarian menggunakan exhaustive search

Kemudian penggunaan exhaustive search pada permasalahan TSP ini adalah sebagai berikut:  Permasalahan: Diberikan n buah kota serta diketahui jarak antara setiap kota satu sama lain. Temukan perjalanan (tour) terpendek yang melalui setiap kota lainnya hanya sekali dan kembali lagi ke kota asal keberangkatan. Dengan kata lain, permasalahan TSP ini tidak lain adalah menemukan sirkuit Hamilton dengan bobot minimum.  Algoritma exhaustive search untuk persoalan TSP: a) Enumerasikan (list) semua sirkuit Hamilton dari graf lengkap dengan n buah simpul. b) Hitung (evaluasi) bobot setiap sirkuit Hamilton yang ditemukan pada langkah a. c) Pilih sirkuit Hamilton yang mempunyai bobot terkecil. Contoh :

Gambar 3. TSP dengan n = 4, simpul awal = a

29

Tabel 1 Enumerasi Sirkuit Hamilton


Dari contoh di atas, rute perjalananan terpendek adalah a→c→b→d→a atau a→d→b→c→a dengan bobot = 32.
Untuk n buah simpul semua rute perjalanan yang mungkin dibangkitkan dengan permutasi dari n – 1 buah simpul.
Permutasi dari n – 1 buah simpul adalah (n – 1)!
Pada contoh di atas, untuk n = 6 akan terdapat: (4 – 1)! = 3! = 6 buah kemungkinan rute perjalanan.
Jika diselesaikan dengan metode exhaustive search, maka kita harus mengenumerasi sebanyak (n – 1)! buah sirkuit Hamilton, menghitung setiap bobotnya, dan memilih sirkuit Hamilton dengan bobot terkecil.
Dari algoritma exhaustive search di atas dapat dilakukan perbaikan mengenai banyaknya pencarian rute, yakni dengan diketahui bahwa setengah dari rute perjalanan adalah hasil pencerminan dari setengah rute yang lain, yaitu dengan mengubah arah rute perjalanan 1 dan 6 2 dan 4 3 dan 5 maka dapat dihilangkan setengah dari jumlah permutasi (dari 6 menjadi 3).
Ketiga buah sirkuit Hamilton yang dihasilkan adalah seperti gambar di bawah ini: a

12

12 5

10

d

a

b

9

10

8 15

c

d

15

a

b

c

d

b 5

9 8 c


Dengan demikian, untuk graf dengan n buah simpul, kita hanya perlu mengevaluasi sirkuit Hamilton sebanyak (n – 1)!/2 buah.
Untuk ukuran masukan yang besar, algoritma exhaustive search menjadi sangat tidak mangkus.
Pada persoalan TSP misalnya, untuk jumlah simpul n = 20 akan terdapat (19!)/2 = 6 × 1016 sirkuit Hamilton yang harus dievaluasi satu per satu. Dari pembahasan di atas, dapat diketahui mengenai kompleksitas algoritma brute force dengan exhaustive search pada Travelling Salesman Problem, yaitu: a. Kompleksitas waktu algoritma exhaustive search untuk persoalan TSP sebanding dengan (n – 1)! dikali dengan waktu untuk menghitung bobot setiap sirkuit Hamilton. b. Menghitung bobot setiap sirkuit Hamilton membutuhkan waktu O(n) c. Sehingga kompleksitas waktu algoritma exhaustive search untuk persoalan TSP adalah O(n ⋅ n!)

30

d. Algoritma brute force seringkali lebih mudah diimplementasikan daripada algoritma yang lebih canggih, dan karena kesederhanaannya, kadang-kadang algoritma brute force dapat lebih mangkus (ditinjau dari segi implementasi).

ALGORITMA HEURISTIK 1. Algoritma Greedy Gagasan dasar dari algorima greedy adalah membangun solusi besar di atas solusi kecil. Tidak sama dengan pendekatan lain, bagaimanapun algoritma greedy hanya mengambil solusi yang terbaik yang mereka temukan pada saat itu tanpa memperhatikan konsekuensi ke depan (prinsip ”take what you can get now!”) Apakah algoritma greedy selalu memberikan solusi optimum dari persoalan yang ada? Jika tidak, apakah ada alternatif lain untuk memperoleh solusi optimum? Pertanyaan diatas mungkin muncul pada saat disebut bahwa algoritma greedy merupakan metode yang paling popular untuk memecahkan persoalan optimasi. Metode yang digunakan untuk menjawab beberapa pertanyaan tersebut diatas adalah dengan melakukan penerapan algoritma greedy pada suatu kasus yang membutuhkan pemecahan masalah untuk persoalan optimasi. Prinsip dari algoritma greedy adalah mengambil solusi yang terbaik yang mereka temukan pada saat itu tanpa memperhatikan konsekuensi ke depan (”take what you can get now!”). Contoh Permasalahan TSP adalah sebagai berikut: Seorang sales harus mengunjungi n kota, melewati setiap kota sebanyak 1 kali, dimulai dari salah satu kota yang didefinisikan sebagai tempat asalnya dan harus kembali ke kota tersebut. Biaya transportasi antar kota tersebut telah diberikan. Program ini merepresentasikan kunjungan sales tersebut ke kota-kota yang harus dilewati dengan biaya minimum. Penyelesaian TSP adalah sebagai berikut: Misal kota-kota tersebut direpresentasikan dengan angka 1 hingga n, kota 1 sebagai kota awal dimana salesman memulai perjalanannya. Asumsikan fungsi c(i,j) adalah biaya kunjungan dari kota i ke j. Ada kemungkinan biaya c(i,j) tidak sama dengan biaya c(j,i). Kemungkinan solusi yang pasti adalah (n-1)!. Seseorang mungkin dapat menurunkannya secara sistematis, menemukan biaya untuk setiap masalah dan akhirnya mempunyai solusi dengan biaya terendah. Ini membutuhkan setidaknya (n-1)! langkah. Dengan algoritma greedy, jika salesman ada di kota i, dia akan memilih kota selanjutnya, j dimana c(i,j) merupakan biaya terkecil dari semua biaya c(i,k), dimana k merupakan kota-kota yang belum pernah dikunjungi.
Mulai dari sembarang kota.
Evaluasi semua biaya tetangga.
Ambil tetangga dengan biaya terkecil dan diulang pada langkah ke dua hingga kota telah terlewati semua. Contoh:

31

Langkah 1: Dari E pergi ke B (Total jarak = 3) Langkah 2: Dari B pergi ke A (Total jarak = 3 + 6 = 9) Langkah 3: Dari A pergi ke C (Total jarak = 9 + 5 = 14) Langkah 4: Dari C pergi ke D (Total jarak = 14 + 4 = 18) Langkah 5: Dari D kembali lagi ke E (Total jarak = 18 + 8 = 26) Perjalanan (sirkuit Hamilton) yang dihasilkan: E . B . A . C . D . E Panjang = 3 + 6 + 5 + 4 + 8 = 26 (tidak optimal) Optimal : E . B . D . C . A . E panjang = 3 + 7 + 4 + 5 + 5 = 24 Algoritmanya adalah sebagai berikut:

Dalam tiap iterasi, dicari kota tetangga yang merupakan suksesornya, maka kompleksitasnya O(n2) . Kemudahan/ kelebihan greedy: Algoritma greedy, biasanya linier ke kuadrat dan memerlukan memori ekstra sedikit/kecil. Algoritma greedy tidak selalu memberikan solusi optimum. Tetapi ketika algoritma greedy bekerja, lebih mudah untuk diterapkan dan cukup cepat untuk dilaksanakan algoritma greedy mudah untuk di coding, mudah untuk didebug, berjalan dengan cepat, dan menggunakan memori sedikit/kecil. 2. Algoritma Genetika Algoritma Genetika adalah algoritma pencarian heuristic yang didasarkan atas mekanisme evolusi biologis. Keberagaman pada evolusi biologis adalah variasi dari kromosom antar individu organisme. Variasi kromosom ini akan mempengaruhi laju reproduksi dan tingkat kemampuan organisme untuk tetap hidup. Algoritma Genetika pertama kali dikembangkan oleh John Holland dari Universitas Michigan (1975). Algortima Genetika merupakan simulasi dari proses evolusi Darwin dan operasi genetika atas kromosom. Ada beberapa istilah yang perlu dimengerti dalam algoritma genetika, diantaranya : • Populasi : sejumlah solusi yang mungkin. Populasi awal dibangun secara acak, sedangkan populasi berikutnya merupakan hasil evolusi kromosom-kromosom melalui iterasi yang disebut dengan generasi.

32

• • • • • •

Generasi : iterasi yang dilakukan untuk menentukan populasi berikutnya. Kromosom : Individu yang terdapat dalam satu populasi. Kromosom ini merupakan solusi yang masih berbentuk symbol. Allela : Nilai yang berada dalam gen Locus : Letak suatu gen berada dalam suatu kromosom Fungsi Fitness: alat ukur dalam dalam proses evaluasi yang dilalui kromosom. Nilai fitness akan menunjukkan kualitas dari suatu kromosom dalam populasi tersebut. Offsprings : anak (generasi berikutnya) yang terbentuk dari gabungan 2 kromosom generasi sekarang yang bertindak sebagai induk (parent) dengan menggunakan operator penyilangan (crossover) maupun operator mutasi.

a. Komponen-komponen utama algoritma Genetika Ada 6 komponen utama dalam algoritma genetika, yaitu : 1. Teknik Pengkodean Ada beberapa teknik pengkodean, diantaranya : a. Pengkodean Biner Pada pengkodean biner, setiap kromosom akan terdiri dari deretan bilangan biner, sehingga allele setiap gen-nya ada dua, yaitu bernilai 0 atau 1. Contoh : kromosom A dengan panjang kromosom 8 : 1 1 0 0 1 1 0 1 b. Pengkodean Permutasi Pada pengkodean permutasi, setiap kromosom terdiri atas deretan angkan yang menyatakan posisi dalam suatu urutan. Nilai dalam suatu locus dalam satu kromosom tidak boleh ada yang sama. Contoh : pada permasalahan TSP (Travelling Salesman Problem), dimana seorang sales harus mengantarkan barang dengan melewati beberapa kota. Syaratnya dia tidak boleh melewati kota yang sama. Missal ada 5 kota : 1 2 3 4 5, maka contoh pengkodeannya : misal untuk kromosom A : 5 3 2 1 4. c. Pengkodean Nilai Yaitu setiap kromosom akan dikodekan ke dalam nilai-nilai tertentu, biasanya nilainya bernilai real. Contoh : pada pencarian bobot pada Jaringan Syaraf Tiruan d. Pengkodean Pohon Pada Pengkodean pohon, tiap kromosom adalah pohon dari objek-objek seperti fungsi atau perintah dalam bahasa pemrograman. 2. Prosedur Inisialisasi Ukuran populasi tergantung pada masalah yang akan dipecahkan dan jenis operator genetika yang akan diimplementasikan. Setelah ukuran populasi ditentukan, kemudian harus dilakukan inisialisasi terhadap kromosom yang terdapat pada populasi tersebut. Inisialisasi kromosom dilakukan secara acak, namun demikian harus tetap memperhatikan domain solusi dan kendala permasalahan yang ada. 3. Fungsi Evaluasi Ada dua hal yang harus dilakukan dalam melakukan evaluasi kromosom, yaitu : evaluasi fungsi objektif (fungsi tujuan) dan konversi fungsi objektif ke dalam fungsi fitness. Secara umum fungsi fitness diturunkan dari fungsi objektif dengan nilai yang tidak negative. 4. Seleksi Seleksi bertujuan untuk memberikan kesempatan reproduksi yang lebih besar bagi anggota poopulasi yang paling fit. Ada beberapa metode seleksi dari induk yaitu : 33

a. Rank-based fitness assignment b. Roulette wheel selection c. Stochastic universal sampling d. Local selection e. Truncation selection f. Tournament selection 5. Operator Genetika Ada 2 operator genetika yaitu : a. Operator Genetik, yaitu yang memproses gen kromosom. Operator ini meliputi crossover dan mutasi. b. Operator seleksi, yaitu yang memproses sejumlah kromosom 6. Penentuan Parameter Parameter disini adalah parameter yang menentukan keberhasilan Algoritma Genetika. Yaitu : a. Ukuran Populasi (n) , yaitu banyaknya kromosom yang mendiami satu populasi dalam satu generasi b. Probabilitas Crossover (Pc), yaitu rasio antara kromosom parents yang nantinya menjadi parents yang akan bercrossover. c. Probabilitas mutasi (Pm), yaitu rasio dari banyaknya gen dalam setiap kromosom offsprings yang akan melakukan mutasi. b. Struktur umum algoritma Genetika Algoritma Genetika Genetic Algorithm 1. [Start] Generate random population of n chromosomes (suitable solutions for the problem) 2. [Fitness] Evaluate the fitness f(x) of each chromosome x in the population 3. [New population] Create a new population by repeating following steps until the new population is complete a. [Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected) b. [Crossover] With a crossover probability cross over the parents to form new offspring (children). If no crossover was performed, offspring is the exact copy of parents. c. [Mutation] With a mutation probability mutate new offspring at each locus (position in chromosome). d. [Accepting] Place new offspring in the new population 4. [Replace] Use new generated population for a further run of the algorithm 5. [Test] If the end condition is satisfied, stop, and return the best solution in current population 6. [Loop] Go to step 2

c. TSP dengan Algoritma Genetik Algoritma Genetika merupakan salah satu algoritma alternatif yang dapat digunakan sebab prosesnya cepat dan memberikan hasil yang diinginkan. Selain itu, algoritma genetika juga mampu memberikan suatu solusi pada waktu kapanpun.

34

Bagaimana algoritma genetika dapat menyelesaikan TSP yaitu solusi direpresentasikan ke dalam suatu kromosom yang berisi dari nomor urut kota-kota selain kota asal. Masing-masing nomor urut tidak boleh muncul lebih dari satu kali di dalam kromosom sehingga satu kromosom merepresentasikan satu rute perjalanan (satu solusi) yang valid. Berikut ini ialah pseudo-code yang dibuat untuk menyelesaikan persoalan TSP dengan menggunakan Algoritma Genetika.

35

Contoh Persoalan TSP yang Diselesaikan Dengan Algoritma Genetika Berikut contoh persoalan TSP yang diselesaikan dengan menggunakan algoritma genetika. Terdapat 5 buah kota yang akan dilalui oleh seorang pedangang keliling, misalnya Kota A,B,C,D,E. Perjalanan dimulai dari kota A dan berakhir di kota A. Jarak antar kota diperlihatkan pada graf berikut:

Persoalan TSP tersebut akan diselesaikan dengan menggunakan algoritma genetika. Kriteria berhenti ditentukan terlebih dahulu yaitu apabila setelah dalam beberapa generasi berturut-turut diperoleh nilai fitness yang terendah tidah berubah. Pemilihan nilai fitness yang terendah sebagai syarat karena nilai tersebut yang merepresentasikan jarak terdekat yang dicari pada persoalan TSP ini. Ada 4 kota yang akan menjadi gen dalam kromosom yaitu kota-kota selain kota asal. a. Inisialisasi Misalkan kita menggunakan 6 buah populasi dalam satu generasi, yaitu Kromosom[1] = [B D E C] Kromosom[2] = [D B E C] Kromosom[3] = [C B D E] Kromosom[4] = [E B C D] Kromosom[5] = [E C B D] Kromosom[6] = [C D E B] P[6] = 0,033 / 0,207 = 0,159 b. Evaluasi Kromosom Kemudian kita akan menghitung nilai fitness dari tiap kromosom yang telah dibangkitkan pada langkah a di atas. Fitness[1] = AB+BD+DE+EC+CA = 7 + 2 + 6 + 3 + 5 = 23 Fitness[2] = AD+DB+BE+EC+CA = 9 + 2 + 8 + 3 + 5 = 27

36

Fitness[3] = AC+CB+BD+DE+EA = 5 + 7 + 2 + 6 + 9 = 29 Fitness[4] = AE+EB+BC+CD+DA = 9 + 8 + 7 + 4 + 9 = 37 Fitness[5] = AE+EC+CB+BD+DA = 9 + 3 + 7 + 2 + 9 = 30 Fitness[6] = AC+CD+DE+EB+BA = 5 + 4 + 6 + 8 + 7 = 30 c. Seleksi Kromosom Oleh karena pada persoalan TSP yang diinginkan yaitu kromosom dengan fitness yang lebih kecil akan mempunyai probabilitas untuk terpilih kembali lebih besar maka digunakan inverse. Q[i] = 1 / Fitness[i] (1) Q[1] = 1 / 23 = 0,043 Q[2] = 1 / 27 = 0,037 Q[3] = 1 / 29 = 0,034 Q[4] = 1 / 37 = 0,027 Q[5 = 1 / 30 = 0,033 Q[6] = 1 / 30 = 0,033 Total = 0,043 + 0,037 + 0,034 + 0,027 + 0,033 + 0,033 = 0,207 Untuk mencari probabilitas kita menggunakan rumus berikut : P[i] = Q[i] / Total (2) P[1] = 0,043 / 0,207 = 0,208 P[2] = 0,037 / 0,207 = 0,179 P[3] = 0,034 / 0,207 = 0,164 P[4] = 0,027 / 0,207 = 0,130 P[5] = 0,033 / 0,207 = 0,159 P[6] = 0,033 / 0,207 = 0,159 Dari probabilitas di atas terlihat bahwa kromosom ke-1 memiliki fitness paling kecil oleh karena itu memiliki probabilitas untuk terpilih pada generasi selanjutnya lebih besar daripada kromosom lainnya. Untuk proses seleksi kita menggunakan roulette-wheel, untuk itu kita terlebih dahulu mencari nilai komulatif dari probabilitasnya. C[1] = 0,028 C[2] = 0,028+0,179 = 0,387 C[3] = 0,387+0,164 = 0,551 C[4] = 0,551+0,130 = 0,681 C[5] = 0,681+0,159 = 0,840 C[6] = 0,840+0,159 = 1 Proses roulete-wheel adalah membangkitkan nilai acak R antara 0-1. Jika R[k]
37

Kromosom[4] = [5] = [E C B D] Kromosom[5] = [4] = [E B C D] Kromosom[6] = [6] = [C D E B] d. Crossover (pindah silang) Pindah silang pada TSP dapat diimplementasikan dengan skema order crossover. Pada skema ini, satu bagian kromosom dipertukarkan dengan tetap menjaga urutan kota yang bukan bagian dari kromosom tersebut. Kromosom yang dijadikan induk dipilih secara acak dan jumlah kromosom yang dicrossover dipengaruhi oleh parameter crossover probability (ñc). Misal kita tentukan ñc = 25%, maka diharapkan dalam 1 generasi ada 50% (3 kromosom) dari populasi mengalami crossover. Pertama kita bangkitkan bilangan acak R sebanyak jumlah populasi yaitu 6 kali. R[1] = 0,451 R[2] = 0,211 R[3] = 0,302 R[4] = 0,877 R[5] = 0,771 R[6] = 0,131 Kromosom ke-k yang dipilih sebagai induk jika R[k] < ñc. Maka yang akan dijadikan induk adalah kromosom[2], kromosom[3], dan kromosom[6]. Setelah melakukan pemilihan induk, proses selanjutnya adalah menentukan posisi crossover. Hal tersebut dilakukan dengan membangkitkan bilangan acak antara 1 sampai dengan panjang kromosom-1. Dalam kasus TSP ini bilangan acaknya adalah antara 1-3. Misal diperoleh bilangan acaknya 1, maka gen yang ke1 pada kromosom induk pertama diambil kemudian ditukar dengan gen pada kromosom induk kedua yang belum ada pada induk pertama dengan tetap memperhatikan urutannya. Bilangan acak untuk 3 kromosom induk yang akan dicrossover : C[2] = 2 C[3] = 1 C[6] = 2 Proses crossover : Kromosom[2] = Kromosom[2] >< Kromosom[3] = [B D E C] >< [C B D E] = [B D C E] Kromosom[3] = Kromosom[3] >< Kromosom[6] = [C B D E] >< [C D E B] = [C D E B] Kromosom[6] = Kromosom[6] >< Kromosom[2] = [C D E B] >< [B D E C] = [C D B E] Populasi setelah di-crossover : Kromosom[1] = [D B E C] Kromosom[2] = [B D C E] Kromosom[3] = [C D E B] Kromosom[4] = [E C B D] Kromosom[5] = [E B C D] Kromosom[6] = [C D B E]

38

e. Mutasi Pada kasus TSP ini skema mutasi yang digunakan adalah swapping mutation. Jumlah kromosom yang mengalami mutasi dalam satu populasi ditentukan oleh parameter mutation rate(ñm). Proses mutasi dilakukan dengan cara menukar gen yang dipilih secara acak dengan gen sesudahnya. Jika gen tersebut berada di akhir kromosom, maka ditukar dengan gen yang pertama. Pertama kita hitung dulu panjang total gen yang ada pada satu populasi: Panjang total gen = jumlah gen dalam 1 kromosom * jumlah Kromosom (3) = 4 * 6 = 24 Untuk memilih posisi gen yang mengalami mutasi dilakukan dengan membangkitkan bilangan acak antara 1 – Panjang total gen yaitu 1- 24. Misal kita tentukan ñm = 20 %. Maka jumlah gen yang akan dimutasi adalah = 0,2*24 = 4,8 = 5 5 buah posisi gen yang akan dimutasi, setelah diacak adalah posisi 3, 7, 10, 20, 24. Proses mutasi : Kromosom[1] = [D B C E] Kromosom[2] = [B D E C] Kromosom[3] = [C E D B] Kromosom[4] = [E C B D] Kromosom[5] = [D B C E] Kromosom[6] = [E D B C] Proses algoritma genetik untuk 1 generasi telah selesai. Maka nilai fitness setelah 1 generasi adalah: Fitness[1] = AD+DB+BC+CE+EA = 9 + 2 + 7 + 3 + 9 = 30 Fitness[2] = AB+BD+DE+EC+CA = 7 + 2 + 6 + 3 + 5 = 23 Fitness[3] = AC+CE+ED+DB+BA = 5 + 3 + 6 + 2 + 7 = 23 Fitness[4] = AE+EC+CB+BD+DA = 9 + 3 + 7 + 2 + 9 = 30 Fitness[5] = AD+DB+BC+CE+EA = 9 + 2 + 7 + 3 + 9 = 30 Fitness[6] = AE+ED+DB+BC+CA = 9 + 6 + 2 + 7 + 5 = 29 Sebelumnya telah ditentukan criteria berhenti yaitu bila setelah dalam beberapa generasi berturut-turutdiperoleh nilai fitness yang terendah tidah berubah. Pada 1 generasi telah terlihat bahwa terdapat nilai fitness terkecil yang tidak berubah. Apabila perhitungan dilanjutkan hingga ke generasi ke-N maka diyakinkan bahwa nilai fitness yang terendah tetap tidak akan berubah. Walaupun perhitungan cukup dijabarkan hingga generasi ke-1 saja namun solusi yang mendekati optimal telah didapatkan. Oleh karena itu, terbukti bahwa algoritma genetika dapat menyelesaikan persoalan TSP. Kelebihan :
algoritma genetika akan menghasilkan solusi yang lebih optimal pada setiap generasinya. Hal tersebut terlihat dari nilai fitness tiap generasi.
solusi dapat diperoleh kapanpun karena solusi dihasilkan pada generasi ke berapapun.
algoritma genetika tidak harus membutuhkan waktu yang lama karena tidak semua kemungkinan dicoba, tergantung pada kriteria berakhirnya.

39

Referensi Aho, Alfred V., Hopcroft, John, E. dan Ullman, Jeffrey, D., 1974, The Design and Analysis of Computer Algorithms, Addisaon-Wesley, California. Brassard, G, dan Bratley, P. 1986, Fundamentals of Algorithmics, Prentice Hall, New Jersey. Greedy Algorithm http.//www.nist.gov/dads/HTML/greedyalgo.html Greedy Algorithms http.///www.ese.ohio-state.edu/~gurari/course/cis680/cis680Ch17.html Horowitz, E., 1978, Fundamentals of Computer Algorithms, Computer Science Press, Inc., Maryland. Kruse, R.L, 1991, Data Structures and Program Design, Prentice Hall of India, New Delhi.

40