Analisa dan Perancangan Algoritma Ahmad Sabri, Dr Sesi 2: 16 Mei 2016
Teknik rekursif dan iteratif Algoritma rekursif adalah algoritma yang memanggil dirinya sendiri sampai tercapai kondisi yang ditetapkan Algoritma iteratif adalah algoritma yang menggunakan loop untuk mencapai solusi
Algoritma untuk menghitung n faktorial Versi rekursif
function factorial(n) if n = 0 then return 1; else return (n * factorial(n-1)); end function
Versi iteratif
r := 1; for i := 1 to n do r := r * i; end for
Algoritma untuk menghitung bilangan Fibonacci ke-n Versi rekursif
function fibo(n) if (n = 1 or n = 2) then return 1; else return fibo(n-1) + fibo(n-2); end function Ket: n ≥ 1
Versi iteratif
prev1 := 1; prev2 := 1; fibo := 0; for i := 3 to n do fibo := prev1 + prev2; prev1 := prev2; prev2 := fibo; end (Ket: n ≥ 3)
Metode dasar algoritma • Brute force • Divide and conquer • Greedy
Metode brute force Ide: Menyelesaikan masalah dengan pendekatan "langsung jadi", umumnya dilakukan berdasarkan definisi permasalahan yang ada dan batasan yang diterapkan Catatan: • Disebut juga skema "naif" • Metode brute force mengabaikan kompleksitas, namun selalu memberikan solusi • Metode brute force menjadi sangat tidak efisien jika ukuran masalah (yaitu, input data) semakin besar • Umumnya digunakan untuk menyelesaikan masalah berukuran kecil, di mana pengaruh kompleksitas tidak terlalu signifikan terhadap kinerja algoritma
Brute force: selection sort 1.Diberikan sebarang barisan bilangan integer 2.Temukan elemen terkecil pada (sub)barisan yang belum terurut 3.Tempatkan elemen terkecil tersebut pada posisi pertama dari barisan yang belum terurut tersebut 4.Kembali ke langkah 1 sampai diperoleh barisan yang terurut
Brute force: selection sort Urutkanlah barisan bilangan 51364287 secara naik, dengan metode selection sort
Beberapa masalah yang diselesaikan dengan brute force 1.Sorting 2.String matching/searching 3.Generating object
Metode divide and conquer Ide: 1.Bagilah masalah menjadi beberapa bagian masalah yang lebih kecil 2.Pecahkan setiap masalah yang lebih kecil tersebut 3.Gabungkanlah solusi masalah yang lebih kecil tersebut untuk memperoleh solusi masalah semula.
Divide and conquer: merge sort 1.Diberikan sebarang barisan bilangan integer 2.Bagilah barisan tersebut menjadi dua bagian sampai didapat bagian terkecil 3.Gabungkanlah (merge) setiap dua subbarisan yang berurutan, dengan mengurutkan bilangannya. 4.Kembali ke langkah 3 sampai diperoleh barisan semula yang telah terurut.
Divide and conquer: merge sort Urutkanlah barisan 38,27,43,3,9,82,10 dengan teknik merge sort
Metode greedy Ide: 1. Mulailah dari solusi masalah terkecil 2. Secara bertahap, bentuklah solusi untuk masalah yang lebih besar. Ulangi langkah ini sampai tercapai solusi masalah semula.
Dengan menemukan solusi lokal, "diharapkan" solusi global dapat ditemukan Algoritma greedy memberikan solusi, namun belum tentu diperoleh solusi terbaik
Greedy: masalah pohon rentangan minimal Algoritma Kruskal 1. Mulai dengan himpunan semua simpul pada graf G tanpa mengikutsertakan ruasnya 2. Tambahkan sebuah ruas berbobot terkecil yang tidak menghasilkan loop. Jika ada terdapat beberapa ruas dengan bobot terkecil yang sama, pilih salah satunya secara sebarang. 3. Kembali ke langkah 2, sampai semua simpul terhubung.
Algoritma Prim 1. 2. 3. 4. 5. 6.
Mulai dengan himpunan semua simpul pada G tanpa mengikutsertakan ruasnya Tentukan simpul awal. Hubungkan simpul ini dengan simpul terdekatnya Kategorikan simpul yang sudah terhubung sebagai C, dan simpul yang belum terhubung sebagai C’ Pilih sebuah simpul berkategori C’ yang dapat dihubungkan dengan salah satu simpul berkategori C dengan ruas berbobot terkecil. Hubungkan kedua simpul tersebut, dan dari keduanya, ubah simpul yang berkategori C’ menjadi C. Kembali ke langkah 3 sampai semua simpul terhubung.
Greedy: masalah pohon rentang minimal Sebuah jaringan TV kabel berencana membangun jaringan kabel yang menghubungkan stasiun pusat di kota 1 menuju kelima kota lainnya (2,..,6), berdasarkan diagram jarak berikut. Dengan pertimbangan ekonomis, panjang kabel yang digunakan harus seminimal mungkin. Tentukan diagram jaringan kabel yang perlu dibangun.
Sumber: Operations Research, Hamdy Taha
• Algoritma Kruskal (dengan metode greedy) selalu menemukan solusi terbaik untuk masalah pohon rentangan minimal • Namun, metode greedy tidak selalu menemukan solusi terbaik untuk masalah traveling salesman
