Algoritma tamak

Isi kandungan

Penyelesaian yang Boleh dilaksanakan
Algoritma tamak
Contoh - Pendekatan tamak
Aplikasi Algoritma tamak

Dalam tutorial ini, anda akan mengetahui apa itu Algoritma Greedy. Anda juga akan mendapat contoh pendekatan tamak.

Algoritma tamak adalah pendekatan untuk menyelesaikan masalah dengan memilih pilihan terbaik yang ada pada masa ini, tanpa perlu risau akan hasil yang akan datang. Dengan kata lain, pilihan terbaik tempatan bertujuan menghasilkan hasil terbaik di peringkat global.

Algoritma ini mungkin bukan pilihan terbaik untuk semua masalah. Ia mungkin memberikan hasil yang salah dalam beberapa kes.

Algoritma ini tidak pernah kembali untuk membalikkan keputusan yang dibuat. Algoritma ini berfungsi dalam pendekatan top-down.

Kelebihan utama algoritma ini ialah:

Algoritma lebih senang dijelaskan .
Algoritma ini dapat berfungsi lebih baik daripada algoritma lain (tetapi, tidak dalam semua kes).

Penyelesaian yang Boleh dilaksanakan

Penyelesaian yang boleh dilaksanakan adalah penyelesaian yang memberikan penyelesaian yang optimum untuk masalah tersebut.

Algoritma tamak

Sebagai permulaan, set penyelesaian (mengandungi jawapan) kosong.
Pada setiap langkah, item ditambahkan ke dalam set penyelesaian.
Sekiranya set penyelesaian dapat dilaksanakan, item semasa disimpan.
Jika tidak, item tersebut ditolak dan tidak pernah dipertimbangkan lagi.

Contoh - Pendekatan tamak

 Masalah: Anda mesti membuat perubahan sejumlah menggunakan sekecil mungkin duit syiling. Jumlah: $ 28 Syiling yang ada: syiling $ 5 syiling $ 2 syiling $ 1 syiling

Penyelesaian:

Buat set penyelesaian kosong = ().
syiling = (5, 2, 1)
jumlah = 0
Sementara jumlah ≠ 28, lakukan perkara berikut.
Pilih duit syiling C dari syiling yang berjumlah + C <28.
Sekiranya C + jumlah> 28, kembalikan penyelesaian.
Lain, jumlah = jumlah + C.
Tambahkan C ke set penyelesaian.

Sehingga 5 lelaran pertama, set penyelesaian mengandungi 5 syiling $ 5. Selepas itu, kita mendapat duit syiling 1 $ 2 dan akhirnya, duit syiling 1 $ 1.