Greedy algorithm: basically pick the "reasonable local optima" rather than evaluating the whole thing. Interpretasi Greedy algorithm lumayan bervariasi. The strict interpretation requires mathematical proof of correctness (dalam kasus tertentu dapat dibuktikan bahwa local optima dapat membawa algoritmanya ke global optimum). The less strict interpretation basically says greedy algorithm = pick local optima (berdasarkan suatu fungsi, yang bisa juga merupakan suatu fungsi heuristik).
Heuristics itu basically penggunaan suatu "fungsi heuristik" untuk menilai mana yang langkah yang optimal. Fungsi heuristic ini biasanya lebih sederhana dan jauh lebih cepat dari evaluate the whole tree -> hasil dari fungsinya digunakan in lieu of the full tree traversal, jadi semakin bagus fungsinya, semakin akurat hasil yang didapatkan. Kalo saya menganggapnya sih heuristics search itu untuk mencari solusi yang "kira - kira cukup bagus" rather than absolute best solution, sedangkan fungsi heuristik ya fungsi value "kira - kira" dari suatu state. Heuristic search biasanya tidak perlu dibuktikan optimalitynya, karena fungsinya sendiri kan memang "kira - kira" saja. -Kurniady 2010/6/10 Feris Thia <feris.mi...@phi-integration.com> > > > Hi All, > > Sori kalau agak OOT tapi milis ini juga tentang programming kan ? hehehe > > Mau tanya dong, ada yang bisa jelasin tentang hubungan Greedy Algorithm > dengan rekonstruksi tree data structure yang kita buat ? > > Kasusnya saya begini, di data mining ada salah satu model konstruksi > pengambilan keputusan dengan tree based structure => decision tree. Namun, > dalam beberapa kasus pruning tree harus dilakukan karena ada tipe decision > yang rekursif dan tidak ada akhir jadi harus "dipotong" tapi tetap mencapai > kesimpulan yang sama. > > Nah, pruning ini kadang memakan sangat lama jadi perlu dibantu beberapa > algoritma heuristic. Salah satu yang terbaik katanya greedy algorithm. Nah, > sampai disini otak saya kayanya sejauh ini belum nangkap total. Jadi lebih > baik saya "kosongkan" dulu semua konsep yang saya tahu dan coba menanyakan > penjelasan dari berbagai sumber. > > Ada yang bisa kasih pencerahan sedikit untuk Greedy Algorithm ini? > > Sebelum dan sesudahnya saya ucapkan banyak terima kasih nih. > > Regards, > > Feris > > >
