Jumat, 21 Mei 2010

Contoh Algoritma divide dan conquer

• Skema Umum Algoritma Divide and Conquer

procedure DIVIDE_and_CONQUER(input n : integer)
{ Menyelesaikan masalah dengan algoritma D-and-C.
Masukan: masukan yang berukuran n
Keluaran: solusi dari masalah semula
}
Deklarasi
r, k : integer
Algoritma
if n .... n0 then {ukuran masalah sudah cukup kecil }
SOLVE upa-masalah yang berukuran n ini
else
Bagi menjadi r upa-masalah, masing-masing berukuran n/k
for masing-masing dari r upa-masalah do
DIVIDE_and_CONQUER(n/k)
endfor
COMBINE solusi dari r upa-masalah menjadi solusi masalah semula }
endif


• Jika pembagian selalu menghasilkan dua upa-masalah yang berukuran sama:

procedure DIVIDE_and_CONQUER(input n : integer)
{ Menyelesaikan masalah dengan algoritma D-and-C.
Masukan: masukan yang berukuran n
Keluaran: solusi dari masalah semula
}
Deklarasi
r, k : integer

Algoritma
if n ... n0 then {ukuran masalah sudah cukup kecil }
SOLVE upa-masalah yang berukuran n ini
else
Bagi menjadi 2 upa-masalah, masing-masing berukuran n/2
DIVIDE_and_CONQUER(upa-masalah pertama yang berukuran n/2)
DIVIDE_and_CONQUER(upa-masalah kedua yang berukuran n/2)
COMBINE solusi dari 2 upa-masalah
endif

Persoalan Minimum dan Maksimum (MinMaks)

Persoalan: Misalkan diketahui tabel A yang berukuran n elemen sudah berisi nilai integer. Kita ingin menentukan nilai minimum dan nilai maksimum sekaligus di dalam tabel tersebut.

Penyelesaian dengan Algoritma Brute Force

procedure MinMaks1(input A : TabelInt, n : integer,
output min, maks : integer)
{ Mencari nilai minimum dan maksimum di dalam tabel A yang berukuran n elemen, secara brute force.
Masukan: tabel A yang sudah terdefinisi elemen-elemennya
Keluaran: nilai maksimum dan nilai minimum tabel
}
Deklarasi
i : integer

Algoritma:
min... A1 { inisialisasi nilai minimum}
maks...A1 { inisialisasi nilai maksimum }
for i...2 to n do

if Ai <> maks then
maks...Ai
endif

endfor

sumber :Bahan Kuliah ke-5 IF2251 Strategi Algoritmik
Algoritma Divide and Conquer Departemen Teknik Informatika
Institut Teknologi Bandung
2004

Algoritma Divide & Conquer

Dalam ilmu komputer , Devide dan Conquer (D & C) adalah penting desain algoritma berdasarkan multi-bercabang rekursi . Sebuah algoritma devide dan conquer rekursif bekerja dengan memecah masalah menjadi dua atau lebih sub-masalah yang sama (atau terkait) jenis, sampai ini menjadi cukup sederhana untuk dipecahkan secara langsung.. Solusi ke sub masalah kemudian dikombinasikan untuk memberikan solusi bagi masalah yang asli.

Teknik dasar dari algoritma ini efisien untuk semua jenis masalah, seperti sortasi (misalnya, quicksort , menggabungkan jenis ), mengalikan jumlah besar (misalnya Karatsuba ), analisis sintaksis (misalnya, top-down parser ), dan menghitung Fourier diskrit transformasi ( FFTs ).

Di sisi lain, kemampuan untuk memahami dan desain algoritma D & C adalah keterampilan yang membutuhkan waktu untuk menguasai. Seperti ketika membuktikan suatu teorema dengan induksi, itu perlu untuk menggantikan masalah yang asli oleh umum atau masalah yang lebih rumit untuk mendapatkan rekursi berjalan, dan tidak ada metode sistematis untuk menemukan generalisasi yang tepat.

Divide: membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama),

Conquer: memecahkan (menyelesaikan) masing-masing upa-masalah (secara rekursif), dan

Combine: mengabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.

Obyek permasalahan yang dibagi :
masukan (input) atau instances yang berukuran n seperti:
- tabel (larik),
- matriks,
- eksponen,
- dll, bergantung pada masalahnya.

Tiap-tiap masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif.

Sumber disini

Minggu, 02 Mei 2010

Algoritma Kruskall

Algoritma Kruskal adalah algoritma dalam teori graph yang menemukan suatu pohon rentang minimum untuk terhubung dalam graf berbobot . Ini berarti menemukan subset dari tepi yang membentuk sebuah pohon yang mencakup setiap titik , di mana berat total dari semua tepi di atas pohon diminimalkan.. Jika grafik tidak terhubung, maka menemukan hutan rentang minimum (pohon rentang minimum untuk setiap komponen terhubung ) . Algoritma Kruskal adalah contoh dari algoritma rakus . Algoritma ini pertama kali muncul dalam Prosiding American Mathematical Society , hal 1956. Algoritma lain untuk masalah ini termasuk Algoritma Prim , Reverse-Hapus algoritma , dan algoritma Borůvka's

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

Graph : kumpulan dua himpunan yaitu himpunan titik ( vertex / simpul / node ) dan kumpulan dari garis ( edge )
Tree : graph tak berarah yang terhubung dan tidak mengandung sirkuit.
Sirkuit : simpul awal = simpul akhir


PR

Soal : Buatlah Minimum Spanning Tree + Total Cost !!

Jawab :

Gunakan Algoritma Kruskall

--------------Edge-----Cost----

  1. ----- (C,D )----- 2
  2. ------( A,F )----- 4
  3. ------( C,E )----- 4
  4. ------( B,C )----- 5
  5. ------( A,C )----- 6

Maka Spanning Tree-nya adalah:




















Sehingga total costnya adalah : 21

Sumber : pertama

Terima kasih telah mengunjungi blog saya... Jangan lupa tinggalkan comment karena masih newbie jadi butuh banyak pencerahan hehe...

 

Site Info

Followers

Bobo Magazine Copyright © 2009 Blogger Template Designed by Bie Blogger Template