Sejarah, Definisi dan Cara Kerja Algoritma Divide and Conquer

 Nama : Rian Pebriawan

Npm : 21312026

Kelas : IF 21A

Sejarah Algoritma Devide dan Conquer

        Pada zaman dahulu, divide and conquer merupakan strategi militer yang dikenal dengan nama divide ut imperes. Saat ini strategi tersebut menjadi strategi fundamental di dalam ilmu komputer dengan nama divide and conquer. Algoritma divide and conquer ini ditemukan oleh seorang ilmuwan Rusia bernama Anatolii Alexeevich Karatsuba pada tahun 1960. Pada mulanya beliau menemukan algoritma yang lebih mangkus untuk mengalikan dua buah bilangan bulat yang besar.

Definisi Divide and Conquer

        Dividide and conquer merupakan algoritma yang sangat popular di dunia ilmu komputer. Divide and conquer merupakan algorita yang berprinsip memecah – mecah suatu permasalahan yang terlalu besar menjadi bagian – bagian kecil, sehingga lebih mudah untuk diselesaikan. Langkah – langkah umum algoritma untuk divide and conquer adalah, sebagai berikut :

• Divide membagi masalah menjadi beberapa upamasalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama).
• Conquer memecahkan atau menyelesaikan masing – masing upa-masalah secara rekursif
• Combine menggabungkan solusi masing – masing upa-masalah sehingga membentuk solusi masalah semula.

Berikut ini merupakan skema umum dari algoritma divide and conquer :

Cara Kerja Algoritma Divide and Conquer

        Dengan menggunakan bahasa dan library yang tepat, kita dapat membagi-bagikan setiap bagian rekursif (left = ... dan right = ...) ke satu unit kerja baru, yang dikenal dengan nama thread. Mekanisme pada sistem operasi atau compiler kemudian akan membagi-bagikan tugas pembagian dan perhitungan lanjutan agar dapat dijalankan secara paralel, misalnya dengan membagikan tugas ke dalam beberapa core prosesor, atau bahkan ke dalam mesin lain (jika terdapat sistem dengan banyak mesin).

        Dengan membagi-bagikan pekerjaan ke dalam banyak unit, tentunya pekerjaan akan lebih cepat selesai! Teknik memecah-mecah pekerjaan untuk kemudian dibagikan kepada banyak pekerja ini dikenal dengan nama divide and conquer.

        Singkatnya, setelah membagikan list menjadi dua bagian terus menerus sampai bagian terkecilnya, kita menjumlahkan kedua nilai list tersebut, seperti pada gambar berikut:

Implementasi algoritma Algoritma Branch and Bound

Nama : Rian Pebriawan
NPM : 21312026
Kelas : IF 21A

Metode Branch and Bound adalah sebuah teknik algoritma yang secara khusus mempelajari bagaimana caranya memperkecil Search Tree menjadi sekecil mungkin.

Sesuai dengan namanya, metode ini terdiri dari 2 langkah yaitu :

1. Branch yang artinya membangun semua cabang tree yang mungkin menuju solusi. 
2. Bound yang artinya menghitung node mana yang merupakan active node (E-node) dan node mana yang merupakan dead node (D-node) dengan menggunakan syarat batas constraint (kendala).

Teknik Branch and Bound

Ada beberapa teknik dalam Branch and Bound yaitu: 

1. FIFO Branch and Bound
   Adalah teknik Branch and Bound yang menggunakan bantuan queue untuk perhitungan Branch  and Bound secara First In First Out.
   
   
2. LIFO Branch and Bound
   Adalah teknik Branch and Bound yang menggunakan bantuan stack untuk perhitungan Branch and Bound secara Last In First Out.
   
   
3. Least Cost Branch and Bound
   Teknik ini akan menghitung cost setiap node. Node yang memiliki cost paling kecil dikatakan memiliki kemungkinan paling besar menuju solusi. 

Masalah yang dapat dipecahkan with Branch and Bound

Branch and Bound dapat digunakan untuk memecahkan berbagai masalah yang menggunakan Search Tree :
–Traveling Salesman Problem
–N-Queen Problem
–15 Puzzle Problem
–0/1 Knapsack Problem
–Shortest Path

Sebagaimana pada algortima runut-balik, algoritma Branch & Bound juga merupakan metode pencarian di dalam ruang solusi secara sistematis. Ruang Solusi diorganisasikan ke dalam pohon ruang status. Pembentukan pohon ruang status. Pembentukan pohon ruang status pada algoritma B&B berbeda dengan pembentukan pohon pada algoritma runutbalik. Bila pada algoritma runut-balik ruang solusi dibangun secara Depth-First Search(DFS), maka pada algoritma B&B ruang solusi dibangun dengan skema Breadth-First Search (BFS).

Pada algoritma B&B, pencarian ke simpul solusi dapat dipercepat dengan memilih simpul hidup berdasarkan nilai ongkos (cost). Setiap simpul hidup diasosiasikan dengan sebuah ongkos yang menyatakan nilai batas (bound). Pada prakteknya, nilai batas untuk setiap simpul umumnya berupa taksiran atau perkiraan. Fungsi heuristik untuk menghitung taksiran nilai tersebut dinyatakan secara umum sebagai :

(i) = (i) + (i)

yang dalam hal ini,

(i) = ongkos untuk simpul i
(i) = ongkos mencapai simpul i dari akar
(i) = ongkos mencapai simpul tujuan dari simpul akar i (perkiraan)

Nilai digunakan untuk mengurutkan pencarian. Simpul berikutnya yang dipilih untuk diekspansi adalah simpul yang memiliki  minimum (Simpul-E). Strategi memilih simpul-E seperti ini dinamakan strategi pencarian berdasarkan biaya terkecil (least cost search).

Prinsip dari algoritma branch and bound ini adalah :

1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul solusi (goal node), maka solusi telah ditemukan. Stop.

2. Jika Q kosong, tidak ada solusi . Stop.

3. Jika Q tidak kosong, pilih dari antrian Q simpul i yang mempunyai (i) paling kecil. Jika terdapatbeberapa simpul i yang memenuhi, pilih satusecara sembarang.

4. Jika simpul i adalah simpul solusi, berarti solusi sudah ditemukan, stop. Jika simpul i bukan simpul solusi, maka bangkitkan semua anak-anaknya. Jika i tidak mempunyai anak, kembali ke langkah 2.

5. Untuk setiap anak j dari simpul i, hitung  (j), dan masukkan semua anak-anak tersebut ke dalam antrian Q.

6. Kembali ke langkah 2.