Identifikasi Berbagai Jenis Algoritma Pengacakan

SainsKomputer - Setelah pada postingan sebelumnya Kita sudah mengupas terkait definisi Algoritma dan cara kerjanya, kali ini Kita akan mempelajarinya lebih dalam lagi terkait salah satu Algoritma yang sering digunakan pada kehidupan sehari-hari yaitu Algoritma pengacakan. Algoritma pengacakan adalah algoritma yang menggunakan keacakan dalam logikanya. Mereka dapat diimplementasikan untuk mengurangi kompleksitas ruang dan waktu berjalan. Beberapa algoritma pengacak masih memiliki waktu berjalan deterministik (artinya kompleksitas waktu ditentukan) atau yang lain di mana kompleksitas waktunya bergantung pada variabel acak. Ini dapat didefinisikan secara luas sebagai algoritma Las Vegas atau Monte Carlo.

Kompleksitas waktu adalah perkiraan lama waktu untuk menjalankan suatu algoritma atau seberapa efisien algoritma yang ditulis.

Apa itu Algoritma Las vegas?

Seperti yang sudah tertulis di atas, algoritma pengacak ini memiliki kompleksitas waktu yang ditentukan, tetapi mereka masih menghasilkan secara umum lebih cepat daripada versi non-acak dari algoritma yang sama. Algoritma Las Vegas bekerja seperti ini:

Waktu berjalan ditentukan
Jika algoritma selesai dalam waktu berjalan itu, itu benar
Jika algoritma tidak dapat diselesaikan dalam waktu yang sudah ditentukan, tidak ada solusi yang ditemukan

Karena sifatnya ini, berarti Algoritma Las Vegas selalu dapat menjamin kompleksitas waktu skenario kasus terburuk namun tetap tidak dapat memberikan batasan waktu karena waktu berjalan masih bervariasi dengan input.

Contoh: Pengacak Quick Sort

Algoritma quick sort adalah algoritma pengurutan yang tidak menggunakan memori tambahan. Ini menggunakan dasar bagi dan taklukkan untuk menyortir atau lebih tepatnya dengan memecah kumpulan data menjadi dua bagian berdasarkan nilai pivot yang dipilih. Pada prinsipnya nilai pivot yang dipilih ini akan ditempatkan pada posisinya disetiap akhir proses partisi. Setelah proses partisi selesai dan menempatkan pivot pada posisinya yang tepat maka proses pengurutan dilanjutkan secara rekursif untuk mengurutkan data bagian kiri dari pivot dan bagian kanan dari pivot tersebut.. Kita dapat mengatakan bahwa algoritma beroperasi seperti ini:

Pilih elemen (i) pivot menggunakan generator angka acak
Buat dua sub-array yang lebih kecil dari i dan lebih besar dari i
Kemudian lakukan quicksort pada sub-array, mengeluarkan yang diurutkan penuh

Jika Kamu menjalankan program diatas, Kamu bisa mengamati di baris 31 data array yang sengaja urutannya diacak. setelah program dijalankan maka Kamu akan mendapatkan hasil sebagai berikut.

Dalam skenario terburuk, elemen pivot akan menjadi item pertama atau terakhir. Kita tahu bahwa penyisipan/penghapusan membutuhkan O(1) dan partisi membutuhkan O(n). Karena jika pivot adalah yang pertama dan terakhir, partisi akan membuat 2 sub-array berukuran 0 (karena tidak ada elemen yang melewati yang terakhir ataupun sebelum yang pertama), dan salah satu berukuran O(n-1). Oleh karena itu saya beranggapan waktu berjalan sebagai perbandingan berpasangan dan karena itu akan dibiarkan dengan waktu berjalan O(n^2).

Namun, jika pivot acak bukan elemen pertama atau terakhir dalam array, Kita mesti mengurangi kompleksitas waktu Kita, jika elemen tengah dipilih sebagai pivot, array akan dipartisi menjadi dua setiap kali, dengan catatan meninggalkan Kita dengan kompleksitas waktu sebesar O(n log n) karena pohon rekursi memiliki kedalaman O(log n), dan setiap level membutuhkan O(n) untuk menyelesaikannya. Ini juga berarti bahwa kompleksitas waktu rata-rata akan tetap pada O(n log n) meskipun ada kemungkinan 1/n kasus rata-rata ini terjadi karena kedalaman pohon rekursi dan waktu yang diperlukan untuk menyelesaikan satu tingkat pohon tidak mengubah.

Apa itu Algoritma Monte Carlo?

Jenis umum lain dari algoritma pengacakan adalah Monte Carlo. Algoritma ini berbasis probabilitas, tergantung pada input, ia memiliki probabilitas untuk menghasilkan hasil yang salah atau tidak valid. Secara umum, dapat dikatakan bahwa algoritma Monte Carlo tidak selalu memiliki hasil benar tetapi dalam pemprosesan lebih cepat dari Las Vegas, sedangkan algoritma Vegas cenderung lebih lambat dari Monte Carlo namun selalu menghasilkan hasil yang benar. Oleh karena itu dapat disimpulkan bahwa algoritma Monte Carlo adalah algoritma yang kuat, dengan tingkat keberhasilan yang tinggi, umumnya lebih baik untuk diterapkan daripada Las Vegas karena waktu berjalannya lebih pendek, dan dapat diulang jika solusi tidak ditemukan terlebih dahulu.

Contoh: π Perkiraan

Masalah perkiraan Pi adalah pertanyaan wawancara umum untuk pekerjaan pengembang yang menerapkan pendekatan gaya Monte Carlo.

Kita tahu bahwa Pi adalah rasio keliling lingkaran dengan diameternya. Untuk berhasil memperkirakannya, kita dapat mengambil langkah-langkah berikut:

Gunakan kotak dengan sumbu x dan y dari -1 hingga 1
Hasilkan titik acak pada grafik
Hitung jumlah titik yang berada dalam jarak 1 dari titik asal (X), dan titik yang tidak termasuk dalam kategori ini (Y).
Karena rasio lingkaran dengan luas seluruh grafik sama dengan rasio di dalam jarak 1 dengan yang di luar, kita dapat mengatakan:

πr^2/4r^2 ≈ X/Y

Ini juga berarti bahwa semakin banyak titik acak yang dihasilkan, semakin akurat perkiraan Kita.

Contoh: Algoritma Karger untuk pemotongan minimum

Contoh lain di mana algoritma Monte Carlo dapat diimplementasikan adalah pada penggunaan algoritma Karger ketika menemukan potongan minimum dari suatu graf (artinya jumlah tepi terkecil yang membagi graf menjadi dua bagian). Ini berfungsi untuk grafik tidak berarah dan tidak berbobot.

Buat salinan grafik yang dikontrak
Kondisikan loop terkontrol saat ada lebih dari 2 simpul
Pilih tepi acak (u, v) dalam grafik salinan
Gabungkan dua simpul di tepi menjadi satu simpul
Hapus loop
Kembalikan potongan dengan dua simpul

Karena algoritma Karger adalah algoritma Monte Carlo, pemotongan minimum tidak selalu ditemukan, probabilitas algoritma menemukan pemotongan minimum adalah >= 1/n^2. Jika ada potongan min unik dalam grafik, dan ada M tepi di potongan min dengan E total tepi. Algoritma Karger akan menemukan pemotongan min dengan sukses hanya jika tidak ada tepi En-Em yang dihilangkan selama perulangan (iterasi).

M: tepi dalam potongan minimum
E: total tepi
V: simpul

Event 1: Sebuah edge dari En-Em dipilih pada iterasi pertama
Event 2: Sebuah edge dari En-Em dipilih pada iterasi kedua
Acara 3: Tepi dari En-Em dipilih dalam iterasi ketiga
dll.

Pemotongan minimum akan berhasil ditemukan jika tidak ada peristiwa yang terjadi oleh karena itu probabilitasnya didefinisikan sebagai P(Total Peristiwa').

Algoritma ini dapat diterapkan pada banyak situasi:

Untuk memperkuat jaringan
Optimalisasi jaringan
Masalah cluster dan pencocokan

Contoh: Algoritma Freivald untuk verifikasi produk matriks

Masalah lain yang dapat diselesaikan secara efisien dengan pendekatan Monte Carlo adalah pengecekan produk matriks.

Ambil 3 matriks A, B dan C. Kita dapat menggunakan algoritma Freivald untuk memeriksa apakah C adalah produk dari A dan B.

Kita dapat melakukan ini dengan pendekatan sederhana, menemukan produk dari A dan B, dan melihat apakah itu cocok dengan C. Algoritma memiliki peluang untuk berjalan dalam waktu O(n^log7) menggunakan perkalian matriks Tegangan. Algoritma Freivald dapat digunakan (yang berjalan dalam O(n^2) dengan peluang sukses yang tinggi untuk memverifikasi suatu produk dalam waktu O(kn^2). Ini adalah peluang sukses yang tinggi karena probabilitas kegagalan kurang dari 2 ^-k.

Pendekatan umum untuk ini adalah:

Hasilkan vektor acak 0,1 dari n*1, v
Hitung produk dari A dan Bv dan kurangi dari Cv
Jika hasilnya 0 maka kembalikan benar, jika tidak salah
Metode ini bekerja karena kita tahu bahwa jika C adalah produk, maka mengurangkannya dari produk A dan B akan sama dengan 0.

Contoh di atas dapat diimplementasikan dengan Python sebagai berikut:

Algoritma Kota Atlantik

Algoritma ini adalah campuran antara Las Vegas dan Monte Carlo. Ini sebagian besar cepat dan sebagian besar benar. Sayangnya, ada sedikit kasus di mana gaya ini jarang diterapkan karena prosesnya yang sulit.

Algoritma Pengacak Lainnya

Fisher-Yates Shuffle

Contoh lain di mana algoritma acak dapat diimplementasikan adalah pengocokan array. Ini berarti kita akan menampilkan permutasi acak dari array yang diberikan, masing-masing dengan probabilitas yang sama untuk menjadi output. Kita dapat mencapai ini dengan menggunakan algoritma pengacakan Fisher-Yates, yang beroperasi dalam waktu O(n), kemudian kita dapat menggunakan generator bilangan acak semu, yang bekerja dalam waktu O(1).

Algoritma bekerja dengan memulai indeks terakhir dari array, dan secara acak menukarnya dengan elemen lain dalam array. Kita kemudian mengulangi ini, kecuali setiap kali mengurangi ukuran array yang dilihat dengan 1. Ini akan berakhir pada indeks pertama, di mana Kita akan diberikan permutasi acak dari input.

Pengambilan Sampel Waduk

Adaptasi dari shuffle Fisher-Yates adalah pengambilan sampel reservoir (waduk/wadah). Ini adalah saat kita ingin dapat mengambil sampel secara acak k item dari aliran yang panjangnya n. Aliran biasanya terlalu besar untuk dimasukkan ke dalam memori utama, jadi karena itu tidak sepenuhnya diketahui oleh algoritma, aliran ini hanya dapat melihat bagian aliran yang sedang dikerjakannya, selain itu, aliran tersebut tidak dapat melihat item sebelumnya dalam aliran . Dalam hal ini Kita mesti dapat mengambil sampel secara acak pada ukuran k kapan saja.

Dengan menggunakan probabilitas variabel, Kita dapat melakukan ini dengan mempertahankan reservoir berukuran k, sambil mengganti elemen arus di reservoir dengan probabilitas berdasarkan jumlah elemen di sungai.

Jika k = 1, maka kita dapat mengimplementasikannya sebagai berikut:

Simpan elemen pertama sebagai elemen reservoir
Untuk setiap elemen (i), ganti item reservoir dengannya, dengan probabilitas 1/i

Karena Kita ingin dapat mengambil sampel sejumlah elemen (k) dari aliran Kita, Kita dapat menyesuaikan algoritma menjadi:

Simpan input pertama dari aliran (k) sebagai elemen reservoir
Untuk setiap elemen (i), ganti reservoir dengan itu, dengan probabilitas k/i

Pengambilan sampel reservoir digunakan dalam banyak aplikasi yang berbeda, termasuk server web (di mana mungkin ada aliran/trafic tak terbatas) dan database (untuk menguji kueri yang optimal).

Menguji bilangan prima

Pengujian primalitas adalah area lain di mana pengacakan digunakan secara luas. Teorema Kecil Fermat didefinisikan sebagai:

If n is prime, then for every a, 1 < a < n-1,

a^n-1 = 1 mod n

a^n-1 mod n = 1

Karena ini adalah algoritma acak, ada kasus bahwa non-prima akan mengembalikan nilai true, seperti yang terlihat pada contoh sebelumnya, kesalahan ini dapat dikurangi dengan meningkatkan iterasi.

Algoritmanya menjadi sebagai berikut:

K berbanding lurus dengan probabilitas jawaban yang benar untuk bilangan bukan prima.

Bilangan prima akan selalu diidentifikasi dengan benar

Iterasi melalui k kali:

Pilihan acak antara [2, n -2]
Jika faktor persekutuan terbesar dari a dan n != 1, kembalikan false
Jika a^n-1 tidak setara dengan 1 mod n, kembalikan false
Else (lainnya), kembalikan true (artinya angkanya kemungkinan prima)

Algoritma beroperasi dalam waktu O(k log n), karena fungsi utama membutuhkan waktu O(log n), dan Kita dapat mengulanginya sebanyak k kali. Jika algoritma Kita ini gagal mengidentifikasi bilangan prima dengan benar, Kita dapat meningkatkan k untuk meningkatkan akurasi, namun ini datang pada sisi negatif dari waktu berjalan yang lebih tinggi.

Pada akhirnya kita akan mendapati Output Benar untuk 19, karena prima dan Salah untuk 15, karena tidak.

Pengaplikasian Algoritma Pengacak

Algoritma pengacak sangat berguna untuk banyak skenario masalah. beberapa diantaranya sudah ada dalam contoh yang sudah Kita bahas diatas, beberapa lainnya antara lain:

Penyortiran
Penyeimbang beban
Pemrograman matematika
Algoritma grafik
Pencacahan dan penghitungan
Derandomisasi
Komputasi Paralel
Struktur data
Identitas Aljabar

Akhir Kata

Algoritma pengacak biasanya digunakan untuk memecahkan masalah kompleksitas kasus terburuk karena algoritma pengacak dengan probabilitas tinggi untuk berhasil setiap contoh jauh lebih cepat untuk kumpulan data besar daripada pendekatan deterministik apa pun dari masalah yang sama, mereka juga umumnya lebih sederhana untuk diterapkan.

Dalam artikel ini Kita telah mendefinisikan prinsip-prinsip algoritma pengacak, menjelaskan setiap jenis, memberikan penjelasan untuk berbagai algoritma yang menggunakan keacakan dan memberikan aplikasi lain di mana algoritma acak digunakan. Sampai disini dulu pembahasan Kita pada artikel kali ini ,jika artikel ini bermanfaat untuk Kamu jangan lupa share artikel ini agar bermanfaat juga untuk teman yang membutuhkan. Sekian dan Terima Kasih sudah membaca!