Mengimplementasikan Uninformed UCS (Uniform Cost Search) menggunakan Visual C#
UCS method merupakan metode pencarian yang termasuk ke dalam uninformed method dimana metode pencariannya tidak menggunakan/ tidak memiliki pengetahuan dasar (knowledge/ heuristic) sebagai bantuan untuk mencari solusi dari suatu permasalahan. Metode ini sekilas mirip dengan salah satu uninformed method juga, yaitu BFS method. Prinsip dasar pencarian solusi mereka berdua sama, yaitu membuat masalah ke dalam tree list sebelumnya, kemudian melakukan pengecekan terhadap node–node (Puzzle State) yang ada didalam tree list tersebut. Perbedaannya terletak pada penambahan variabel cost sebagai properties pada UCS method untuk mengetahui pada level berapa solusi ditemukan.
Metode–metode pencarian ini dipelajari pada mata kuliah AI (Artificial Intelligence). Biasanya bahan yang bisa dijadikan kasus pada kuliah ini berkisar pada 3×3 puzzle dan mencari path dari kota asal ke kota tujuan. Namun disini hanya membahas 3×3 puzzle sebagai contoh implementasi dari UCS method.
Diberikan kasus puzzle yang first state nya seperti ini 
, dan goal state seperti ini 
. Kita diminta untuk menggerakkan blok “0” (untuk mempermudah penyelesaian kasus, blok kosong diganti dengan blok “0”) sedemikian rupa sehingga mencapai goal state. Dengan menganggap first state sebagai ancestor pada tree list, maka child nya adalah pemindahan 4 arah blok “0” tersebut (pemindahan ke atas, ke kanan, ke bawah, ke kiri). Untuk lebih mempermudah, berikut struktur data yang disajikan ke dalam tree list.
Konsep dasar sudah dibahas, sekarang menuju ke sesi C# code nya. Sebelumnya, dibutuhkan sebuah penyimpan nilai puzzle state diatas ke dalam sebuah array atau list yang disebut fringe, tapi lebih baik kalau kita menggunakan list (lihat perbedaannya list dengan array). Fringe tersebut menyimpan list of current puzzle state yang biasanya bertipe integer. Jadi, kita butuh sebuah list lagi yang menyimpan nilai – nilai sebuah current puzzle state yang disimpan secara linear. Sebagai contoh current puzzle state berikut yang mana apabila di matrix kan, akan menjadi seperti berikut: { [0, 0] = 0, [0, 1] = 1, [0, 2] = 2, [1, 0] = 3, [1, 1] = 4, [1, 2] = 5, [2, 0] = 6, [2, 1] = 7, [2, 2] = 8 }. Nah, dari matrix ini akan kita pindahkan ke linear list dengan bentuk berikut { [0] = 0, [1] = 1, [2] = 2, [3] = 3, [4] = 4, [5] = 5, [6] = 6, [7] = 7, [8] = 8 }.
Note: Apabila tidak mengerti tentang array [0, 0] = 0 berarti [row, column] = value, atau array [0] = 0 berarti [index] = value.
Apa saja input variable yang dibutuhkan? Yang pasti yaitu row untuk menyimpan nilai baris, column untuk menyimpan nilai kolom, fringe sebagai list of puzzle state, startPosition sebagai list nilai–nilai first puzzle state, dan endPosition sebagai list nilai–nilai goal puzzle state. Buat sebuah class baru, misalkan class UCSMethod.
public partial class UCSMethod
{
private List<int> endPosition = new List<int>();
private List<int> startPosition = new List<int>();
private List<List<int>> fringe = new List<List<int>>();
private int row = 0;
private int column = 0;
}
Tambahkan method Solve() ke dalam class UCSMethod tersebut. Method ini berfungsi sebagai tempatnya coding.
private void Solve()
{
int zeroPosition = 0;
this.index = 0;
this.fringe.Add(this.startPosition);
}
Dari code diatas, ada attribute baru index, yang berfungsi untuk meng-counter nilai index untuk setiap puzzle state yang di generate. Ada juga zeroPosition yang berfungsi untuk mencari nilai 0 (zero) di dalam puzzle state. Tambahkan index ke dalam class UCSMethod.
public partial class UCSMethod
{
…
private int index = 0;
}
Note: child pada tree didapat dari pemindahan blok “0” ke 4 arah. Jadi, sebelum memindahkan blok “0”, kita harus mendapatkan di index berapa yang bernilai 0 itu berada pada parent (atau puzzle state).
Sekarang, lihat struktur data berikut. Untuk panduan, lihat kembali list tree diatas.
Kita mulai pengecekan pada fringe first element, apakah sama dengan endPosition, kalau tidak sama kita generate child nya dari first element tersebut. Sebelumnya kita harus mencari zeroPosition first element. Setelah zeroPosition nya ketemu, kita lanjutkan dengan pemindahan zeroPosition puzzle state tersebut. Untuk pemindahan pertama, zeroPosition akan mencoba berpindah ke atas. Jika perpindahan tersebut masih di dalam range nya matrix, perpindahan tersebut akan membuat sebuah puzzle state baru yang akan dimasukkan ke dalam fringe. Begitu seterusnya untuk proses ke kanan, ke bawah, dan ke kiri. Setelah itu, kembali lagi ke fringe, cek lagi fringe second element, kalau tidak sama dengan endPosition, generate lagi child nya, lalu masukkan lagi ke dalam fringe.
Lalu tambahkan code berikut kedalam method Solve() yang berasal dari algoritma diatas.
Nah, ada beberapa fungsi baru disini, yaitu IsSame, FindZeroPosition, dan ZeroTryToMove. Code untuk 3 method diatas akan dijelaskan di bawah ini, jangan lupa untuk memasukkan ke dalam class UCSMethod.
Ada 4 method baru dari method ZeroTryToMove. Tambahkan 4 method berikut ke dalam class UCSMethod.
Kalau kita review lagi, ada 7 method yang ada di dalam class UCSMethod dan ada 6 attribute di dalam class UCSMethod.
Kesimpulan
Untuk kasus yang sederhana dimana hanya blok “0” yang berpindah – pindah, maka solusi akan bisa dicari. Namun untuk kasus yang sederhana juga tetapi yang dipindah – pindahkan tidak hanya blok “0” saja (misalkan blok “4” kita tukar dengan blok “5”), maka proses komputasi nya akan menjadi sangat rumit dan bahkan terjadinya overflow dalam proses pencarian solusi. Diharapkan nantinya ada sebuah pembatas untuk mencegah terjadinya proses overflow tersebut. Misalkan jika waktu pencarian solusinya lebih dari 20 second atau jumlah puzzle state yang ada di fringe lebih dari 10000, maka proses pencarian bisa dihentikan.
Mengapa overflow bisa terjadi? Hal ini didapat dari UCS Method yang termasuk ke dalam kategori worst searching. Kenapa disebut demikian? Pertama, pasti ada child yang sama dengan parent nya (Tebak kenapa). Hal ini tentunya memperlambat dalam proses pengecekan dimana mungkin terjadi nya pengecekan lebih dari sekali untuk puzzle state yang sama. Kedua, tidak adanya heuristic/ knowledge. Ibaratnya proses UCS ini sangat dominan di prosesor, sedangkan pemanfaatan memori kecil sekali. Tentu saja dengan tidak adanya heuristic/ knowledge ini, maka pemakaian resource komputer sangat tidak optimal. Namun, keuntungan dari penggunaan UCS Method adalah metode yang sangat murah dan sederhana. Yang pasti solusi pasti terpecahkan tapi bisa jadi tidak optimal.
