Marshal Algorithm

Hmm, “Marshal Algorithm” sekarang jadi agak populer di anak Pelatnas TOKI 2007, hehe…

Apa itu “Marshal Algorithm”? Aslinya kecelakaan sih, idenya cuma gini :

Kalau solusi kita udah parah banget, dalam artian kita bikin program dengan teknik brute force dan yakin pasti ada testcase yang bakal bikin time limit, kita bikin counter yang kemudian dicek dengan “Konstanta Marshal”, kalau udah melebihi “Konstanta Marshal” tersebut, program kita paksa untuk exit (pake halt(0) di Pascal). Untuk beberapa kasus tepat sebelum exit kita bisa tulis hasil terbaik yang kita dapetin, tapi kalau untuk beberapa kasus kita harus merandom dari beberapa kemungkinan yang belum sempat diexpand, hehe…

Emang cara yang ama sekali gak menjamin kebenaran sih. Tapi coba pikirkan, seandainya kita brute force terus hasil aslinya udah ketemu di awal, tetep aja kan brute force kita akan expand ampe kemungkinan terakhir (dan kemudian kena time limit), nah dalam kondisi tersebutlah “Marshal Algorithm” akan berjalan dengan sangat excellent, hehe…

Tapi secara resmi sebenarnya cara ini gak bisa dibilang licik, toh konsep ini bisa kita kategorikan ke dalam teknik heuristic search atau simulated annealing gitu.

May 30, 2007

Posted in Computing.