~ Algoritma Greedy ~

-
Secara harfiah,  greedy  berarti rakus atau tamak.
Algoritma  Greedy  merupakan  algoritma sedarhana
dan lempang yang paling populer untuk pemecahan
persoalan  optimasi (maksimum atau  minimum).
Prinsip  greedy   adalah: “take what you  can  get
now!”, yang digunakan dalam konteks positif.[7]
Ada tiga pendekatan dalam  menyelesaikan
persoalan  Integer Knapsack dengan algoritma
Greedy:
1)  Greedy by profit. 
Pada setiap langkah,  knapsack diisi dengan objek
yang mempunyai keuntungan terbesar. Strategi ini
mencoba memaksimumkan keuntungan dengan
memilih objek yang paling menguntungkan terlebih
dahulu.
2)  Greedy by weight.
Pada setiap langkah,  knapsack diisi dengan objek
yang mempunyai berat paling  ringan. Strategi ini
mencoba memaksimumkan keuntungan dengan
memasukkan sebanyak mungkin objek ke dalam
knapsack.
3)  Greedy by density. 
Pada setiap langkah,  knapsack diisi dengan objek
yang mempunyai densitas,  pi  /wi  terbesar.   Strategi
ini mencoba  memaksimumkan keuntungan  dengan
memilih objek yang mempunyai keuntungan per unit
berat terbesar.

Komentar

Posting Komentar

Postingan populer dari blog ini

~ TOPOLOGICAL SORTING ~

-
Gambar
Di bidang ilmu komputer , semacam topologi atau urutan topologi dari graf berarah adalah urutan linear simpulnya sehingga untuk setiap tepi yang diarahkan uv dari simpul u ke simpul v , u datang sebelum v dalam pemesanan. Misalnya, simpul grafik dapat mewakili tugas yang harus dilakukan, dan ujung-ujungnya mungkin merupakan kendala yang harus dilakukan satu tugas sebelum yang lain; Dalam aplikasi ini, pemesanan topologi hanyalah urutan yang valid untuk tugas. Pemesanan topologis dimungkinkan jika dan hanya jika grafik tidak memiliki siklus terarah , yaitu jika merupakan grafik asiklik terarah (DAG). Setiap DAG memiliki paling sedikit satu pemesanan topologi, dan algoritma dikenal untuk menyusun urutan topologi setiap DAG dalam waktu linier . Contoh Aplikasi penyortiran topologi kanonik adalah penjadwalan urutan pekerjaan atau tugas berdasarkan ketergantungan mereka. Pekerjaan diwakili oleh simpul, dan ada tepi dari x ke y jika pekerjaan x harus ...
Baca selengkapnya

~ AHO-CORASICK ALGORITHM ~

-
Gambar
Algoritma Aho-Corasick Dalam ilmu komputer , algoritma Aho-Corasick adalah algoritma pencarian string yang ditemukan oleh Alfred V. Aho dan Margaret J. Corasick. [1] Ini adalah sejenis algoritma pencocokan kamus yang menempatkan elemen dari serangkaian string terbatas ("kamus") dalam teks masukan. Ini cocok dengan semua senar secara bersamaan. Kompleksitas algoritma linier di sepanjang senar ditambah panjang teks yang dicari ditambah jumlah output yang sesuai. Perhatikan bahwa karena semua kecocokan ditemukan, ada jumlah kuadrat dari kecocokan jika setiap pertandingan substring (misalnya kamus = a , aa , aaa , aaaa dan string masukan adalah aaaa ). Secara informal, algoritma ini membangun sebuah mesin negara yang terbatas yang menyerupai sebuah trie dengan tambahan link antara berbagai node internal. Tautan internal tambahan ini memungkinkan transisi yang cepat antara korespondensi string yang gagal (misalnya pencarian kucing dalam trie...
Baca selengkapnya

~ Algoritma Edmonds-Karp ~

-
Gambar
Dalam ilmu komputer , algoritma Edmonds-Karp adalah implementasi metode Ford-Fulkerson untuk menghitung aliran maksimum dalam jaringan arus pada waktu O ( V E 2 ). Algoritma ini pertama kali diterbitkan oleh Yefim Dinitz pada tahun 1970  dan diterbitkan secara independen oleh Jack Edmonds dan Richard Karp pada tahun 1972. [3] Algoritma Dinic mencakup teknik tambahan yang mengurangi waktu berjalan ke O ( V 2 E ). Algoritma Algoritma ini identik dengan algoritma Ford-Fulkerson , kecuali bahwa urutan pencarian saat menemukan jalan augmenting didefinisikan. Jalur yang ditemukan pastilah jalan terpendek yang memiliki kapasitas yang tersedia. Ini bisa ditemukan dengan pencarian yang luas , karena kita membiarkan tepi memiliki panjang satuan. Waktu berjalan O ( V E 2 ) ditemukan dengan menunjukkan bahwa setiap jalur augmenting dapat ditemukan pada waktu O ( E ), bahwa setiap kali setidaknya satu dari ujung E menjadi jenuh (tepi yang memiliki ar...
Baca selengkapnya