Jenis jenis Algoritma








Jenis Jenis Algoritma

 Halo sobat coding, pada kesempatan kali ini, Brainedukasi akan memberikan informasi Jenis Jenis algoritma,  lengkap sebagai pengantar di perkuliahan. berikut jenis jenis algoritma

Branch and Bound

Branch and Bound merupakan sebuah teknik algoritma yang secara khusus mempelajari bagaimana caranya memperkecil Search Tree sekecil mungkin.  pada teknik algoritma ini memiliki 2 langkah yaitu: 
Branch adalah membangun semua cabang tree yang mungkin menuju solusi. 
Bound adalah menghitung node mana yang merukan active node (E-node) dan node mana yang merupakan dead node (D-node) dengan menggunakan syarat batas constraint (kendala)

ada beberapa teknik BRAND AND BOUND, antara lain

1. LIFO Branch and Bound
merupakan teknik yang menggunakan stack untuk perhitungan Branch and Bound secara Last In    First Out

2. FIFO Branch and Bound
merupakan teknik yang menggunakan queue untuk perhitungan Branch and Bound secara First in First Out

3. Leat Cost Branch and Bound
merupakan teknik yang digunakan untuk menghitung cost setiap node, node yang memiliki cost paling kecil dikatakan memiliki kemungkinan paling besar menuju solusi.

Masalah yang dapat dipecahkan menggunakan Branch and Bound, antara lain
- Traveling Salesman Problem
- N-Queen Problem
- 15 Puzzle Problem
- 0/1 Knapsack Problem


Algoritma Brute Force

Brute Force merupakan sebuah pendekatan yang lempang ( straightforward) untuk memecahkan masalah, biasanya didasarkan pada pernyataan masalah (problem statement) dan definisi yang dilibatkan.

Algoritma Brute Force pada dasarnya adalah alur penyelesaian permasalahan dengan cara berpikir yang sederhana , langsung dengan cara yang jelas

Model Penelitian Brute Force
Model penelitian yang dilakukan adalah mengimplementasikan penggunaan algoritma brute force pada permasalahan Traveling Salesman dengan menggunakan konsep Exhaustive search.

Pemecahan masalah Graf
adapun penyelesaian masalah graph diatas sebagai berikut :
1. Enumerasikan langkah sejumlah (n-1)! jadi
2. dengan metode node = n = 4, maka didapat jumlah pilihan =(4-1)! = 3! = 3x2x1 = 6 dari graph, maka menghasilkan permutasi seperti pada tabel. 
Permasalahan yang dapat disimpulkan antara lain :

1. Mengenumerasi semua Sirkuit Hamilton dari Graph lengkap TSP
2. Menghitung Bobot setiap sirkuit Hamilton yang ditemukan pada langkah 1
3. Memilih sirkuit Hamilton yang mempunyai bobot terkecil

Analisis:

Keunggulan :

  • Algoritma Brute Force rata rata hampir dipakai untuk menyelesaikan permasalahan - permasalahan yang terjadi disekitar kira, untuk kasus TSP. pemakaian algoritma brute force menjamin penyelesaian solusi dengan baik, dalam kasus TSP. implementasi algoritma brute force dikenal dengan sebutan exhaustive search
Kelemahan :
  • Algoritma Brute Force memiliki kelemahan , dalam perncarian solusi harus membangkitkan sebanyak (n-1)!/2 untuk  jumlah node yang sedikit. pemakaian brute force sangat efisien tetapi untuk jumlah node banyak , maka algoritma ini menjadi tidak efisien  
 Kesimpulan :
  •  Penggunaan algoritma Brute Force didalam masalah pencarian cukup efisien untuk yang node nya sedikit, tetapi untuk yang node nya banyak algoritma ini menjadi sangat tidak efisien, karena itu harus menelusuri seluruh kemungkinan rute yang ada
materi lengkap proses penyelesaian kasus dengan brute force dapat mengunduh link dibawah ini
<< Materi Case Study Brute Force >>

Algoritma Greedy

Secara harfiah algoritma greedy memiliki arti tamak atau rakus,. Algoritma Greedy merupakan algoritma sederhana dan lempang yang paling populer untuk pemecahan. persoalan optimasi.
Hanya ada dua macam permasalahan optimasi, yaitu maksimasi dan minimasi. Pada algoritma greedy membentuk solusi langkah perlangkah, dalam setiap langkah terdapat banyak pilihan yang perlu di eksplorasi. Oleh karena itu setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Prinsip Algoritma Greedy adalah. "take what you can get now".

Skema Umum pada algoritma Greedy :

1. Himpunan kandidat C.

himpunan ini berisi  elemen - elemen pembentuk solusi , pada setiap langkah satu buah kandidat diambil dari himpunanya

2. Himpunan Solusi S.

himpunan ini berisi kandidat kandidat yang terpilih sebagai solusi persoalan , Dengan kata lain dengan kata lain himpunan solusi adalah bagian dari himpunan kandidat.

3. Fungsi Seleksi

fungsi ini dinyatakan dalam predikat seleksi, merupakan fungsi yang pada setiap langkah memilih kandidat yang paling memungkinkan. mencapai solusi optimal , kandidat yang terpilih pada satu langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya

4. Fungsi Kelayakan

fungsi ini dinyatakan dalam predikat layak. fungsi kelayakan ini merupakan fungsi yang memerika apakah suatu kandidat yang telah dipilih dapat memberikan solusi yang layak.

5. Fungsi Objektif

fungsi objektif ini merupakan sebuah fungsi yang memaksimumkan atau meminimumkan nilai solusi.

Dengan kata lain algoritma greedy melibatkan pencarian sebuah himpunan S. dari himpunan kandidat C. yang dalam hal ini himpunan S harus memenuhi beberapa karektistik yang ditentukan. yaitu menyatakan suatu solusi dan S dioptimasi oleh fungsi objektif.







LihatTutupKomentar