Re: [JUG-Indonesia] [Tanya] Greedy Algorithm dan Tree Pruning

2010-06-09 Thread Y. Yudhistira 
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=greedyAlg

2010/6/10 Feris Thia 

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

Re: [JUG-Indonesia] [Tanya] Greedy Algorithm dan Tree Pruning

2010-06-10 Thread Andrian Kurniady 
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 

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

Re: [JUG-Indonesia] [Tanya] Greedy Algorithm dan Tree Pruning

2010-06-10 Thread Nanda Firdausi 
The wikipedia entry seems easier to understand.

http://en.wikipedia.org/wiki/Greedy_algorithm


--
Nanda Firdausi Muhammad
http://satukubik.com


2010/6/10 Y. Yudhistira 

>
>
> http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=greedyAlg
>
> 2010/6/10 Feris Thia 
>
>
>>
>> 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
>>
>
>
>
> 
>

Re: [JUG-Indonesia] [Tanya] Greedy Algorithm dan Tree Pruning

2010-06-12 Thread Feris Thia 
Hi Bung Yudhistira,

2010/6/10 Y. Yudhistira 

>
>
> http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=greedyAlg
>

Thanks, dengan contoh lagi :)

Regards,

Feris

Re: [JUG-Indonesia] [Tanya] Greedy Algorithm dan Tree Pruning

2010-06-12 Thread Feris Thia 
Hi Bung Andrian Kurniady,

Penjelasan singkat dan paling bisa dimengerti sejauh ini :)

Ternyata sering ikut Google Code jam dan ikut interview di Google ya ?
 Senang banget dengan sharingnya, semoga tidak keberatan jika ke depan saya
bisa tanya2 tentang algoritma lain seperti Genetic Algorithm, dll.

Again ... thanks banget ya. Really appreciate it.

Regards,

Feris

2010/6/10 Andrian Kurniady 

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

Re: [JUG-Indonesia] [Tanya] Greedy Algorithm dan Tree Pruning

2010-06-12 Thread Feris Thia 
Hi Bung Nanda,

2010/6/10 Nanda Firdausi 

> The wikipedia entry seems easier to understand.
>
> http://en.wikipedia.org/wiki/Greedy_algorithm
>

Have tried that entry initially. But feel a need to hear others that
practically ever tried the algorithm. Nevertheless, thanks for the share.


> --
> Nanda Firdausi Muhammad
> http://satukubik.com
>

Regards,

Feris