TUGAS 6

Algoritma Greedy 

1 Definisi Algoritma Greedy

Algoritma greedy adalah algoritma yang memecahkan masalah langkah demi langkah, pada setiap langkah:

1. mengambil pilihan yang terbaik yang dapat diperoleh saat itu

2. berharap bahwa dengan memilih optimum loklal pada setiap langkah akan mencapai optimum global. Algoritma greedy mengasumsikan bahwa optimum lokal merupakan bagian dari optimum global. Prinsip algoritma greedy adalah: “take what you can get now!”  Ambil apa yang anda peroleh sekarang! Prinsip ini juga dipakai dalam pemecahan masalah optimasi. Dalam kehidupan sehari-hari, kita juga pernah menggunakan prinsip greedy, misalnya: a. Memilih jurusan di Perguruan Tinggi b. Memilih jalur tersingkat dari Bandung ke Jakarta.

 1.1 Skema Umum Algoritma Greedy Persoalan optimasi dalam konteks algoritma greedy disusun oleh elemen elemen sebagai berikut :

  1. Himpunan kandidat, C. Himpunan ini berisi elemen-elemen pembentuk solusi. Pada setiap  langkah, satu buah kandidat diambil dari himpunannya.
  2. Himpunan solusi, S. Himpunan ini berisi kandidat-kandidat yang terpilih sebagai solusi  persoalan. Dengan kata lain, himpunan solusi adalah himpunan bagian dari himpunan kandidat.

 3. Fungsi seleksi (selection function) Fungsi ini dinyatakan dengan predikat seleksi. Merupakan  fungsi yang pada setiap langkah memilih kandidat yang paling memungkinkan

 1.2 Elemen-elemen algoritma greedy:

    1. Himpunan kandidat, C.
    2. Himpunan solusi, S
    3. Fungsi seleksi (selection function)
    4. Fungsi kelayakan (feasible)
    5. Fungsi obyektif

  Dengan kata lain: algoritma greedy melibatkan pencarian sebuah himpunan bagian, S, dari himpunan kandidat, C; yang dalam hal ini,S harus memenuhi beberapa kriteria yang ditentukan, yaitu menyatakan suatu solusi dan S dioptimisasi oleh fungsi obyektif.