DUST15

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)   Greed...

Sakelar rentang nonblocking minimal adalah perangkat yang dapat menghubungkan input N ke keluaran N dalam kombinasi apapun. Penggunaan switch yang paling umum dari tipe ini adalah pertukaran telepon . Istilah "non-blocking" berarti jika tidak rusak, selalu bisa melakukan koneksi. Istilah "minimal" berarti memiliki beberapa komponen yang paling sedikit, dan oleh karena itu biaya minimal. Secara historis, di switch telepon, koneksi antara penelepon disusun dengan relay elektromekanis besar dan mahal, switch Strowger . Sifat matematis dasar dari switch Strowger adalah bahwa untuk setiap masukan ke saklar, ada satu keluaran. Sebagian besar teori rangkaian switching matematis mencoba menggunakan properti ini untuk mengurangi jumlah switch yang diperlukan untuk menghubungkan kombinasi input ke kombinasi output. Pada tahun 1940-an dan 1950-an, para insinyur di Bell Laboratories memulai serangkaian penyelidikan matematika lanjutan untuk mengurangi...

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 ...

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...