Penyelesaian masalah melalui proses pencarian atau searching

Metode Pemecahan Masalah (Problem Solving Method)

Nama : Rendy Noviantono

Kelas  : 3KA10

Npm   : 15115757

Dosen : Essy Malays Sari Sakti

a. Pengertian Metode Pemecahan Masalah (Problem solving Method)

Metode pemecahan masalah (problem solving) adalah penggunaan metode dalam kegiatan pembelajaran dengan jalan melatih siswa menghadapi berbagai masalah baik itu masalah pribadi atau perorangan maupun masalah kelompok untuk dipecahkan sendiri atau secara bersama-sama.

Penyelesaian masalah merupakan proses dari menerima tantangan dan usaha – usaha untuk menyelesaikannya sampai menemukan penyelesaiannya. menurut Syaiful  Bahri Djamara (2006 : 103) bahwa:

Metode problem solving (metode pemecahan masalah) bukan hanya sekedar metode mengajar tetapi juga merupakan suatu metode berfikir, sebab dalam problem solving dapat menggunakan metode lain yang dimulai dari mencari data sampai kepada menarik kesimpulan.

Menurut N.Sudirman (1987:146) metode problem solving adalah cara penyajian bahan pelajaran dengan menjadikan masalah sebagai titik tolak pembahasan untuk dianalisis dan disintesis dalam usaha untuk mencari pemecahan atau jawabannya oleh siswa. Sedangkan menurut  Gulo (2002:111) menyatakan bahwa problem solving adalah metode yang mengajarkan penyelesaian masalah dengan memberikan penekanan pada terselesaikannya suatu masalah secara menalar.

Senada dengan pendapat diatas Sanjaya (2006:214) menyatakan pada metode pemecahan masalah, materi pelajaran tidak terbatas pada buku saja tetapi juga bersumber dari peristiwa – peristiwa tertentu sesuai dengan kurikulum yang berlaku. Ada beberapa  kriteria pemilihan bahan pelajaran untuk metode pemecahan masalah yaitu:

a)      Mengandung isu – isu yang mengandung konflik bias dari berita, rekaman video dan lain – lain

b)      Bersifat familiar dengan siswa

c)      Berhubungan dengan kepentingan orang banyak

d)     Mendukung tujuan atau kompetensi yang harus dimiliki siswa sesuai kurikulum yang berlaku

e)      Sesuai dengan minat siswa sehingga siswa merasa perlu untuk mempelajari

Dalam pelaksanaan pembelajaran sehari-hari  metode pemecahan masalah banyak digunakan guru bersama dengan penggunaan metode lainnya. Dengan metode ini guru tidak memberikan informasi dulu  tetapi informasi diperoleh siswa setelah memecahkan masalahnya. Pembelajaran pemecahan masalah berangkat dari masalah yang harus dipecahkan melalui praktikum atau pengamatan.

Suatu soal dapat dipandang sebagai “masalah” merupakan hal yang sangat relatif. Suatu soal yang dianggap sebagai masalah bagi seseorang, bagi orang lain mungkin hanya merupakan hal yang rutin belaka. Dengan demikian, guru perlu berhati-hati dalam menentukan soal yang akan disajikan sebagai pemecahan masalah. Bagi sebagian besar guru untuk memperoleh atau menyusun soal yang benar-benar bukan merupakan masalah rutin bagi siswa mungkin termasuk pekerjaan yang sulit. Akan tetapi hal ini akan dapat diatasi antara lain melalui pengalaman dalam menyajikan soal yang bervariasi baik bentuk, tema masalah, tingkat kesulitan, serta tuntutan kemampuan intelektual yang ingin dicapai atau dikembangkan pada siswa.

Pembelajaran problem solving merupakan bagian dari pembelajaran berbasis masalah (PBL). Menurut Arends (2008 : 45) pembelajaran berdasarkan masalah merupakan suatu pendekatan pembelajaran di mana siswa mengerjakan permasalahan yang otentik dengan maksud untuk menyusun pengetahuan mereka sendiri.

Pada pembelajaran berbasis masalah siswa dituntut untuk melakukan pemecahan masalah-masalah yang disajikan dengan cara menggali informasi sebanyak-banyaknya, kemudian dianalisis dan dicari solusi dari permasalahan yang ada. Solusi dari permasalahan tersebut tidak mutlak mempunyai satu jawaban yang benar artinya siswa dituntut pula untuk belajar secara kritis. Siswa diharapkan menjadi individu yang berwawasan luas serta mampu melihat hubungan pembelajaran dengan aspek-aspek yang ada di lingkungannya.

Dari pendapat di atas maka dapat disimpulkan metode pembelajaran problem solving adalah suatu penyajian materi pelajaran yang menghadapkan siswa pada persoalan yang harus dipecahkan atau diselesaikan untuk mencapai tujuan pembelajaran. Dalam pembelajaran ini siswa di haruskan melakukan penyelidikan otentik untuk mencari penyelesaian terhadap masalah yang diberikan. Mereka menganalisis dan mengidentifikasikan masalah, mengembangkan hipotesis, mengumpulkan dan menganalisis informasi dan membuat kesimpulan.

b.Manfaat dan Tujuan dari  Metode Pemecahan Masalah (Problem Solving Method)

 Manfaat dari penggunaan metode problem solving pada proses belajar mengajar untuk mengembangkan pembelajaran yang lebih menarik. Menurut Djahiri (1983:133) metode problem solving memberikan beberapa manfaat antara lain :

a)         Mengembangkan sikap keterampilan siswa dalam memecahkan permasalahan, serta dalam mengambil kepuutusan secara objektif dan mandiri

b)         Mengembangkan kemampuan berpikir para siswa, anggapan yang menyatakan bahwa kemampuan berpikir akan lahir bila pengetahuan makin bertambah

c)         Melalui inkuiri atau problem solving kemampuan berpikir tadi diproses dalam situasi atau keadaan yang bener – bener dihayati, diminati siswa serta dalam berbagai macam ragam altenatif

d)        Membina pengembangan sikap perasaan (ingin tahu lebih jauh) dan cara berpikir objektif – mandiri, krisis – analisis baik secara individual maupun kelompok

Berhasil tidaknya suatu pengajaran bergantung kepada suatu tujuan yang hendak dicapai. Tujuan dari pembelajaran problem solving adalah sebagai berikut.

1)      Siswa menjadi terampil menyeleksi informasi yang relevan kemudian menganalisisnya dan akhirnya meneliti kembali hasilnya.

2)      Kepuasan intelektual akan timbul dari dalam sebagai hadiah intrinsik bagi siswa.

3)       Potensi intelektual siswa meningkat.

4)      Siswa belajar bagaimana melakukan penemuan dengan melalui proses melakukan penemuan.

c. Langkah – Langkah Metode Pemecahan Masalah (Problem Solving Method)

Penyelesaian masalah menurut J.Dewey dalam bukunya W.Gulo (2002:115) dapat dilakukan melalui enam tahap  yaitu

Tahap – Tahap	Kemampuan yang diperlukan
1)      Merumuskan masalah	Mengetahui dan merumuskan masalah secara jelas
2)      Menelaah masalah	Menggunakan pengetahuan untuk memperinci menganalisa masalah dari berbagai sudut
3)      Merumuskan hipotesis	Berimajinasi dan menghayati ruang lingkup, sebab – akibat dan alternative penyelesaian
4)      Mengumpulkan dan mengelompokkan data sebagai bahan pembuktian hipotesis	Kecakapan mencari dan menyusun data menyajikan data dalam bentuk diagram,gambar dan tabel
5)      Pembuktian hipotesis	Kecakapan menelaah dan membahas data, kecakapan menghubung – hubungkan dan menghitung Ketrampilan mengambil keputusan dan kesimpulan
6)      Menentukan pilihan penyelesaian	Kecakapan membuat altenatif penyelesaian kecakapan dengan memperhitungkan akibat yang terjadi pada setiap pilihan

Penyelesaian masalah Menurut David Johnson dan Johnson dapat dilakukan melalui kelompok dengan prosedur penyelesaiannya dilakukan sebagai berikut (W.Gulo 2002 : 117):

1.      Mendifinisikan Masalah

Mendefinisikan masalah di kelas dapat dilakukan sebagai berikut:

a)Kemukakan kepada siswa peristiwa yang bermasalah, baik melalui bahan tertulis maupun secara lisan, kemudian minta pada siswa untuk merumuskan masalahnya dalam satu kalimat sederhana (brain stroming). Tampunglah setiap pendapat mereka dengan menulisnya dipapan tulis tanpa mempersoalkan tepat atau tidaknya, benar atau salah pendapat tersebut.

b)   Setiap pendapat yang ditinjau dengan permintaan penjelasan dari siswa yang bersangkutan. Dengan demikian dapat dicoret beberapa rumusan yang kurang relevan. Dipilih rumusan yang tepat, atau dirumuskan kembali (rephrase, restate) perumusan – perumusan yang kurang tepat. akhirnya di kelas memilih satu rumusan yang paling tepat dipakai oleh semua. 

2.      Mendiagnosis  masalah

Setelah berhasil merumuskan masalah langkah berikutnya ialah membentuk kelompok kecil, kelompok ini yang akan mendiskusikan sebab – sebab timbulnya masalah

3.   Merumuskan Altenatif Strategi

Pada tahap ini kelompok mencari dan menemukan berbagai altenatif tentang cara penyelesaikan masalah. Untuk itu kelompok harus kreatif, berpikir divergen, memahami pertentangan diantara berbagai ide, dan memiliki daya temu yang tinggi

4.   Menentukan dan menerapkan Strategi

Setelah berbagai altenatif ditemukan kelompok, maka dipilih altenatif mana yang akan dipakai. Dalam tahap ini kelompok menggunakan pertimbangan- pertimbangan yang cukup cukup kritis, selektif, dengan berpikir kovergen

5.   Mengevaluasi Keberhasilan Strategi

Dalam langkah terakhir ini kelompok mempelajari :

(1). Apakah strategi itu berhasil (evaluasi proses)?

(2). Apakah akibat dari penerapan strategi itu (evaluasi hasil) ?

Berdasarkan pendapat para ahli, maka dapat disimpulkan langkah – langkah yang harus diperhatikan oleh guru dalam memberikan pembelajaran problem solving sebagai berikut:

1.      Merumuskan masalah

Dalam merumuskan masalah kemampuan yang diperlukan adalah kemampuan mengetahui dan merumuskan suatu masalah.

2.      Menelaah masalah

 Dalam menelaah masalah kemampuan yang diperlukan adalah menganalisis dan merinci masalah yang diteliti dari berbagai sudut.

3.      Menghimpun dan mengelompokkan data sebagai bahan pembuktian hipotesis

Menghimpun dan mengelompokkan data adalah memperagakan data dalam bentuk bagan, gambar, dan lain-lain sebagai bahan pembuktian hipotesis.

4.      Pembuktian hipotesis

Dalam pembuktian hipotesis kemampuan yang diperlukan adalah kecakapan menelaah dan membahas data yang telah terkumpul.

5.      Menentukan pilihan pemecahan masalah dan keputusan

Dalam menentukan pilihan pemecahan masalah dan keputusan kemampuan yang diperlukan adalah kecakapan membuat alternatif pemecahan, memilih alternatif pemecahan dan keterampilan mengambil keputusan.

d.  Kelebihan dan Kekurangan Pemecahan Masalah (Problem Solving Method)

Pembelajaran problem solving ini memiliki keunggulan dan kelemahan. Adapun keunggulan model pembelajaran problem solving diantaranya yaitu melatih siswa untuk mendesain suatu penemuan, berpikir dan bertindak kreatif, memecahkan masalah yang di hadapi secara realistis, mengidentifikasi dan melakukan penyelidikan, menafsirkan dan mengevaluasi hasil pengamatan, merangsang perkembangan kemajuan berpikir siswa untuk menyelesaikan masalah yang dihadapi dengan tepat, serta dapat membuat pendidikan sekolah lebih relevan dengan kehidupan khususnya dunia kerja.

Sementara kelemahan model pembelajaran problem solving itu sendiri seperti beberapa pokok bahasan sangat sulit untuk menerapkan metode ini. Misalnya terbatasnya alat-alat laboratorium menyulitkan siswa untuk melihat dan mengamati serta akhirnya dapat menyimpulkan kejadian atau konsep tersebut. Dalam pembelajaran problem solving ini memerlukan alokasi waktu yang lebih panjang dibandingkan dengan metode pembelajaran yang lain.

Daftar Pustaka 

Arends, Richard I. (2008) . Learning to Teach Belajar untuk Mengajar. (Edisi Ketujuh/ Buku Dua). Terjemahan Helly Pajitno Soetjipto & Sri Mulyantini Soetjipto. Yogyakarta: Pustaka Pelajar

 

Dhajiri, Ahmad Kosasih. (1985). Strategi Pengajaran Afektif-Nilai-Moral-VCT dan Games dalam VTC. Bandung : Jurusa PMPKn IKIP

Gulo, W. (2002). Strategi Belajar Mengajar. Jakarta : PT. Grasindo

Sardiman. (1996). Interaksi dan Motivasi Belajar Mengajar. Jakarta: PT. Grafindo.

Sudirman,dkk.(1987.)Ilmu Pendidikan. Bandung: Remadja Karya

Syaiful Bahri Djamara dan Drs Aswan Zain . (2006) Strategi Belajar Mengajar,  Jakarta : Rineka Cipta

Pengertian Pemecahan Masalah

Pemecahan Masalah

Pemecahan masalah adalah suatu proses terencana yang perlu dilaksanakan agar memperoleh penyelesaian tertentu dari sebuah masalah yang mungkin tidak didapat dengan segera (Saad & Ghani, 2008:120).

Pendapat lainnya menyatakan bahwa pemecahan masalah sebagai usaha mencari jalan keluar dari suatu kesulitan (Polya, 1973:3). Menurut Goldstein dan Levin, pemecahan masalah telah didefinisikan sebagai proses kognitif tingkat tinggi yang memerlukan modulasi dan kontrol lebih dari keterampilan rutin atau dasar (Rosdiana & Misu, 2013:2).

Beberapa pengertian pemecahan masalah dapat disimpulkan sebagai berikut (Syaiful, 2012: 37):

1.     Kemampuan pemecahan masalah merupakan tujuan umum pengajaran matematika, bahkan sebagai jantungnya matematika. 

2.     Pemecahan masalah meliputi metode, prosedur, dan strategi merupakan proses inti dan utama dalam kurikulum matematika. 

3.     Pemecahan masalah merupakan kemampuan dasar dalam belajar matematika. Pada saat memecahkan masalah matematika, siswa dihadapkan dengan beberapa tantangan seperti kesulitan dalam memahami soal. Hal ini disebabkan karena masalah yang dihadapi bukanlah masalah yang pernah dihadapi siswa sebelumnya.

Tahapan Pemecahan Masalah 

Ada empat tahap pemecahan masalah yaitu; (1) memahami masalah, (2) merencanakan pemecahan, (3) melaksanakan rencana, (4) memeriksa kembali (Polya, 1973:5). Diagram pemecahan masalah Polya dapat dilihat pada Gambar berikut.

Diagram Pemecahan Masalah Polya

 Dari diagram tahapan pemecaham masalah diatas, dapat dirincikan sebagai berikut (Polya, 1973:5-17):

a. Memahami masalah (understand the problem) 

Tahap pertama pada penyelesaian masalah adalah memahami soal. Siswa perlu mengidentifikasi apa yang diketahui, apa saja yang ada, jumlah, hubungan dan nilai-nilai yang terkait serta apa yang sedang mereka cari. Beberapa saran yang  dapat membantu siswa dalam memahami masalah yang kompleks: (1) memberikan pertanyaan mengenai apa yang diketahui dan dicari, (2) menjelaskan masalah sesuai dengan kalimat sendiri, (3) menghubungkannya dengan masalah lain yang serupa, (4) fokus pada bagian yang penting dari masalah tersebut, (5) mengembangkan model, dan (6) menggambar diagram.

b. Membuat rencana (devise a plan) 

Siswa perlu mengidentifikasi operasi yang terlibat serta strategi yang diperlukan untuk menyelesaikan masalah yang diberikan. Hal ini bisa dilakukan siswa dengan cara seperti: (1) menebak, (2) mengembangkan sebuah model, (3) mensketsa diagram, (4) menyederhanakan masalah, (5) mengidentifikasi pola, (6) membuat tabel, (7) eksperimen dan simulasi, (8) bekerja terbalik, (9) menguji semua kemungkinan, (10) mengidentifikasi sub-tujuan, (11) membuat analogi, dan (12) mengurutkan data/informasi.

c. Melaksanakan rencana (carry out the plan) 

Apa yang diterapkan jelaslah tergantung pada apa yang telah direncanakan sebelumnya dan juga termasuk hal-hal berikut: (1) mengartikan informasi yang diberikan ke dalam bentuk matematika; dan (2) melaksanakan strategi selama proses dan perhitungan yang berlangsung. Secara umum pada tahap ini siswa perlu mempertahankan rencana yang sudah dipilih. Jika semisal rencana tersebut tidak bisa terlaksana, maka siswa dapat memilih cara atau rencana lain.

d. Melihat kembali (looking back)

 Aspek-aspek berikut perlu diperhatikan ketika mengecek kembali langkah-langkah yang sebelumnya terlibat dalam menyelesaikan masalah, yaitu: (1) mengecek kembali semua informasi yang penting yang telah teridentifikasi; (2) mengecek semua perhitungan yang sudah terlibat; (3) mempertimbangkan apakah solusinya logis; (4) melihat alternatif penyelesaian yang lain; dan (5) membaca pertanyaan kembali dan bertanya kepada diri sendiri apakah pertanyaannya sudah benar-benar terjawab.

Sementara itu, menurut Krulik dan Rudnick (Carson, 2007: 21 -22), ada lima tahap yang dapat dilakukan dalam memecahkan masalah yaitu sebagai berikut:

1.     Membaca (read). Aktifitas yang dilakukan siswa pada tahap ini adalah mencatat kata kunci, bertanya kepada siswa lain apa yang sedang ditanyakan pada masalah, atau menyatakan kembali masalah ke dalam bahasa yang lebih mudah dipahami. 

2.     Mengeksplorasi (explore). Proses ini meliputi pencarian pola untuk menentukan konsep atau prinsip dari masalah. Pada tahap ini siswa mengidentifikasi masalah yang diberikan, menyajikan masalah ke dalam cara yang mudah dipahami. Pertanyaan yang digunakan pada tahap ini adalah, “seperti apa masalah tersebut”?. Pada tahap ini biasanya dilakukan kegiatan menggambar atau membuat tabel. 

3.     Memilih suatu strategi (select a strategy). Pada tahap ini, siswa menarik kesimpulan atau membuat hipotesis mengenai bagaimana cara menyelesaikan masalah yang ditemui berdasarkan apa yang sudah diperoleh pada dua tahap pertama.

4.     Menyelesaikan masalah (solve the problem). Pada tahap ini semua keterampilan matematika seperti menghitung dilakukan untuk menemukan suatu jawaban. 

5.     Meninjau kembali dan mendiskusikan (review and extend). Pada tahap ini, siswa mengecek kembali jawabannya dan melihat variasi daro cara memecahkan masalah. 

Sedangkan Dewey (Carson 2008: 39) menyatakan tingkat pemecahan masalah adalah sebagai berikut:

1.     Menghadapi masalah (confront problem), yaitu merasakan suatu kesulitan. Proses ini bisa meliputi menyadari hal yang belum diketahui, dan frustasi pada ketidakjelasan situasi. 

2.     Pendefinisian masalah (define problem), yaitu mengklarifikasi karakteristik-karakteristik situasi. Tahap ini meliputi kegiatan mengkhususkan apa yang diketahui dan yang tidak diketahui, menemukan tujuan-tujuan, dan mengidentifikasi kondisi-kondisi yang standar dan ekstrim. 

3.     Penemuan solusi (inventory several solution), yaitu mencari solusi. Tahap ini bisa meliputi kegiatan memperhatikan pola-pola, mengidentifikasi langkah-langkah dalam perencanaan, dan memilih atau menemukan algoritma. 

4.     Konsekuensi dugaan solusi (conjecture consequence of solution), yaitu melakukan rencana atas dugaan solusi. Seperti menggunakan algoritma yang ada, mengumpulkan data tambahan, melakukan analisis kebutuhan, merumuskan kembali masalah, mencobakan untuk situasi-situasi yang serupa, dan mendapatkan hasil (jawaban).

5.     Menguji konsekuensi (test concequnces), yaitu menguji apakah definisi masalah cocok dengan situasinya. Tahap ini bisa meliputi kegiatan mengevaluasi apakah hipotesis-hipotesisnya sesuai?, apakah data yang digunakan tepat?, apakah analisis yang digunakan tepat?, apakah analisis sesuai dengan tipe data yang ada?, apakah hasilnya masuk akal?, dan apakah rencana yang digunakan dapat diaplikasikan di soal yang lain?. 

Daftar Pustaka

• Polya, G. 1980.  On Solving Mathematical Problems in High School. New Jersey: Princeton Univercity Press.
• Saad,N.Ghani, S& Rajendran N.S 2005. The Sources of Pedagogical Content Knowledge (PCK) Used by Mathematics Teacher During Instructions: A Case Study. Departement of Mathematics. Universiti Pendidikan Sultan Idris.

Searching: Uninformed & Informed

Searching adalah mekanisme pemecahan masalah yang paling umum di dalam kecerdasan buatan. Di dalam permasalahan-permasalahan kecerdasan buatan, urutan langkah-langkah yang dibutuhkan untuk memperoleh solusi merupakan suatu isu yang penting untuk diformulasikan. Hal ini harus dilakukan dengan mengidentifikasikan proses try and error secara sistematis pada eksplorasi setiap alternatif jalur yang ada.

Algoritma searching di dalam kecerdasan buatan yang umumnya dikenal adalah

1. Uninformed Search Algorithm

Algoritma yang tidak memberikan informasi tentang permasalahan yang ada, hanya sebatas definisi dari algoritma tersebut.

2. Informed Search Algorithm

Walaupun dengan menggunakan Uninformed Search Algorithm, banyak permasalahan dapat dipecahkan, namun tidak semuanya dari algoritma tersebut dapat menyelesaikan masalah dengan efisien

Uninformed Search Algorithm

Uninformed Search sering disebut juga dengan Blind Search. Istilah tersebut menggambarkan bahwa teknik pencarian ini tidak memiliki informasi tambahan mengenai kondisi diluar dari yang disediakan oleh definisi masalah. Yang dilakukan oleh algoritma ini adalah melakukan generate dari successor dan membedakan goal state dari non-goal state. Pencarian dilakukan berdasarkan pada urutan mana saja node yang hendak di-expand.

1. Breadth First Search (BFS)

Pencarian dengan Breadth First Search menggunakan teknik dimana langkah pertamanya adalah root node diekspansi, setelah itu dilanjutkan semua successor dari root node juga di-expand. Hal ini terus dilakukan berulang-ulang hingga leaf (node pada level paling bawah yang sudah tidak mempunyai successor lagi).

2. Uniform Cost Search (UCS)

Pencarian dengan Breadth First Search akan menjadi optimal ketika nilai pada semua path adalah sama. Dengan sedikit perluasan, dapat ditemukan sebuah algoritma yang optimal dengan melihat kepada nilai tiap path di antara node-node yang ada.

Selain menjalankan fungsi algoritma BFS, Uniform Cost Search melakukan ekspansi node dengan nilai path yang paling kecil. Hal ini bisa dilakukan dengan membuat antrian pada successor yang ada berdasar kepada nilai path-nya (node disimpan dalam bentuk priority queue).

3. Depth First Search (DFS)

Teknik pencarian dengan Depth First Search adalah dengan melakukan ekspansi menuju node yang paling dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari node itu. Setelah node itu selesai diekspansi, maka node tersebut akan ditinggalkan, dan dilakukan ke node paling dalam lainnya yang masih memiliki successor yang belum diekspansi.

4. Depth Limited Search

Pencarian menggunakan DFS akan berlanjut terus sampai kedalaman paling terakhir dari tree. Permasalahan yang muncul pada DFS adalah ketika proses pencarian tersebut menemui infinite state space. Hal ini bisa diatasi dengan menginisiasikan batas depth pada level tertentu semenjak awal pencarian. Sehingga node pada level depth tersebut akan diperlakukan seolah-olah mereka tidak memiliki successor.

5. Iterative Deepening Depth First Search

Iterative deepening search merupakan sebuah strategi umum yang biasanya dikombinasikan dengan depth first tree search, yang akan menemukan berapa depth limit terbaik untuk digunakan. Hal ini dilakukan dengan secara menambah limit secara bertahap, mulai dari 0,1, 2, dan seterusnya sampai goal sudah ditemukan.

6.   Bidirectional Search

Pencarian dengan metode bidirectional search adalah dengan menjalankan dua pencarian secara simultan, yang satu dikerjakan secara forward dari initial state menuju ke goal, sedangkan yang satu lagi dikerjakan secara backward mulai dari goal ke initial state. Yang kemudian diharapkan bahwa kedua pencarian itu akan bertemu di tengah-tengah.

Informed Search Algorithm

Informed Search sering disebut juga dengan Heuristic Search. Pencarian dengan algoritma ini menggunakan knowledge yang spesifik kepada permasalahan yang dihadapi disamping dari definisi masalahnya itu sendiri. Metode ini mampu menemukan solusi secara lebih efisien daripada yang bisa dilakukan pada metode uninformed strategy.

Pada pencarian dengan menggunakan metode Uniform Cost Search (salah satu bagian dari Uninformed Search Algorithm), kita membandingkan nilai pada path yang ada, dan kemudian akan melakukan ekspansi pertama kali pada path dengan nilai yang terkecil. Nilai path ini biasanya dilambangkan dengan g(n). Lebih lanjut lagi dari metode pencarian tersebut, pada Informed Search Algorithm, kita akan mengenal nilai estimasi (prediksi) dari satu node ke node yang lainnya. Nilai estimasi ini biasanya dilambangkan dengan h(n). Jika n adalah goal node, maka nilai h(n) adalah nol.

1. Greedy Best First Search

Metode pencarian ini melakukan ekspansi node yang memiliki jarak terdekat dengan goal. Namun, ekspansi yang dilakukan pada metode ini menggunakan evaluasi node hanya dengan melihat kepada fungsi heuristiknya. Dengan kata lain, yang dibandingkan untuk penentuan ekspansi node adalah nilai estimasi/prediksinya saja.

                     f(n) = h(n)

2. A* Search

Bentuk dari Best First Search yang paling dikenal adalah algoritma pencarian A* (dibaca dengan “A-star”). Sedikit berbeda dengan Greedy yang hanya melihat kepada nilai h(n), pencarian dengan A* melihat kepada kombinasi nilai dari pathnya yaitu g(n) dengan nilai estimasi yaitu h(n).

                    f(n) = g(n) + h(n)

Uninformed and Informed Search Exercise

Gambar 3 Uninformed dan Informed Search Problem

Apabila diberikan kondisi tree seperti gambar di atas, dimana biaya lintasan (path), dan nilai prediksi/estimasi diberikan, maka kita dapat melakukan simulasi proses ekspansi node untuk algoritma Uniform Cost Search, Greedy Best First Search, dan A* Search.

1. Uniform Cost Search

Proses ekspansi pada Uniform Cost Search dihitung berdasarkan nilai lintasan g(n) sehingga proses akan berjalan sebagai berikut:

f = {S};

f = {C, A, K};  // 1, 2, 2

f = {A, K, D};  // 2, 2, 2

f = {K, D, B};  // 2, 2, 4

f = {D, L, B};  // 2, 3, 4

f = {L, E, B};  // 3, 3, 4

f = {E, B};     // 3, 4

f = {B, F};     // 4, 4

f = {F, H, G};  // 4, 6, 7

f = {G, H, G};  // 5, 6, 7

f = {H, G};     // 6, 7

Proses eksplorasi node dimulai dari S sebagai initial state. Eksplorasi node dari S akan menuju ke A, C, K sebagai successornya. Pada simulasi eksplorasi di atas, untuk mempermudah proses eksplorasi maka dituliskan dengan C, A, K karena urutannya dituliskan secara ascending dari nilai g(n) terkecil sehingga akan dihasilkan urutan node yang akan dieksplorasi selanjutnya. Pada eksplorasi node selanjutnya, nilai g(n) diakumulasikan dari node awal sampai pada node current yang baru dieksplorasikan.

Dari proses di atas, maka dihasilkan jumlah ekspansi node sebanyak 10 kali, dan path yang dilalui dengan menggunakan algoritma Uniform Cost Search adalah S-C-D-E-F-G.

2. Greedy Best First Search

Proses ekspansi dengan menggunakan algoritma Greedy Best First Search adalah dengan merujuk pada nilai estimasinya yaitu h(n). Berbeda halnya dengan nilai g(n) yang diakumulasikan, nilai h(n) tidak diakumulasikan. Proses eksplorasi akan berjalan seperti berikut ini:

f = {S};

f = {A, C, K};       // 2, 4, 5

f = {B, C, K};       // 3, 4, 5

f = {G, C, H, K};    // 0, 4, 4, 5

f = {C, H, K};       // 4, 4, 5

Proses yang dilakukan pada Greedy Best First Search sama seperti Uniform Cost Search, namun parameter yang digunakan hanya nilai estimasinya.

Dari proses di atas, maka dihasilkan jumlah ekspansi node sebanyak 4 kali, dan path yang dilalui dengan menggunakan algoritma Greedy Best First Search adalah S-A-B-G.

3. A* Search

Eksplorasi node dari metode A* dilakukan dengan cara menjumlahkan kombinasi nilai path g(n) dan nilai estimasi h(n). Penjumlahan dari nilai tersebut akan dibandingkan untuk menentukan node mana dulu yang akan dieksplorasikan. Prosesnya akan berjalan sebagai berikut ini:

f = {S};

f = {A, C, K};  // 4, 5, 7

f = {C, K, B};  // 5, 7, 7

f = {D, K, B};  // 5, 7, 7

f = {E, K, B};  // 5, 7, 7

f = {F, K, B};  // 5, 7, 7

f = {G, K, B};  // 5, 7, 7

f = {K, B};     // 7, 7

Dari proses di atas, maka dihasilkan jumlah ekspansi node sebanyak 7 kali, dan path yang dilalui dengan menggunakan algoritma A* Search adalah S-C-D-E-F-G.

http://socs.binus.ac.id/2013/04/23/uninformed-search-dan-informed-search/