Nama : Rifqi Achmad Bachtiar
Kelas : 3KA10
NPM : 15115969

PENGENALAN LOGICAL AGENT

Agen logika merupakan agen yang memiliki kemampuan bernalar secara logika. Ketika beberapa solusi tidak secara eksplisit diketahui, maka diperlukan suatu agen berbasis logika. Logika sebagai Bahasa Representasi Pengetahuan memiliki kemampuan untuk merepresentasikan fakta sedemikian sehingga dapat menarik kesimpulan (fakta baru, jawaban). Sedangkan pengetahuan merupakan komponen yang penting, sehingga terdapat perbedaan jika diterapkan pada dua agent, yakni problem solving agent dan knowledge-based agent.Agen Berbasis Pengetahuan atau Knowledge Base (KB) merupakan Himpunan representasi fakta yang diketahui tentang lingkungannya. Tiap fakta disebut sebagai sentence. Fakta tersebut dinyatakan dalam bahasa formal sehingga bisa diolah, menambahkan sentence baru ke KB. Inference Engine merupakan menentukan fakta baru yang dapat diturunkan dari pengetahuan yang sudah ada dalam KB. Agen Berbasis Pengetahuan dalam representasi, agent dapat dipandang dari knowledge level. Apa saja informasi yang diketahui? Misal sebuah robot “mengetahui” bahwa gedung B di antara gedung A dan gedung C. Agent dapat dipandang dari implementation level Bagaimana representasi informasi yang diketahuinya? Logical sentence di_antara(gdB, gdA, gdC). Natural language “Gedung B ada di antara gedung A dan gedung C”. Agen Berbasis Pengetahuan, pilihan representasi berpengaruh terhadap apa yang bisa dilakukan inference engine. Pada pendekatan deklaratif programmer memberitahu agent informasi tentang environment. Kalau informasi kurang, agen bisa melengkapinya sendiri. Jika dibandingkan dengan pendekatan prosedural programmer secara eksplisit memrogram agen untuk bertindak. Sehingga bagaimana jika program tidak benar, maka akan besar kemungkinan menyebabkan kesalahan.Agen Berbasis Pengetahuan, permasalahannya adalah bagaimana representasi yang tepat, sehingga ada dua hal yang harus diperhatikan expressive bisa menyatakan fakta tentang environment, Tractable bisa mengolah/ memproses inference engine (dengan cepat). Knowledge merupakan power atau kekuatan dari pemrograman secara deklaratif. Representasi dan penalaran membentuk suatu Intelligence.

1. KNOWLADGE BASE AGENT

Agen Berbasis Pengetahuan, Knowledge Base (KB) menyatakan apa yang “diketahui” oleh si agent Pendekatan deklaratif membangun agent: “beritahu” informasi yang relevan, simpan dalam KB. Agen dapat ditanya (atau bertanya diri sendiri) apa yang sebaiknya dilakukan berdasarkan KB. Maka sebuah agen berbasis pengetahuan harus bisa mereprentasikan world, state, action, dst. Menerima informasi baru (dan meng-update representasinya). Menyimpulkan pengetahuan lain yang tidak eksplisit (hidden property). q Menyimpulkan action apa yang perlu diambil.Agen Berbasis Pengetahuan atau Knowledge Base (KB) merupakan Himpunan representasi fakta yang diketahui tentang lingkungannya. Tiap fakta disebut sebagai sentence. Fakta tersebut dinyatakan dalam bahasa formal sehingga bisa diolah, menambahkan sentence baru ke KB. Inference Engine merupakan menentukan fakta baru yang dapat diturunkan dari pengetahuan yang sudah ada dalam KB.

2.WUMPUSWORLD

Aturan main Wumpus :
Performance measure: emas +1000, mati -1000, gerak -1, panah -10
Environment: Matriks 4×4 kamar. Initial state [1,1]. Ada gold, wumpus dan pit yang lokasinya dipilih secara acak.
Percept:
Breeze: kamar di samping lubang jebakan ada hembusan angin
Glitter: kamar di mana ada emas ada kilauan/sinar
Smell: kamar di samping Wumpus berbau busuk
Action: maju, belok kiri 90◦ , kanan 90◦ , tembak panah (hanya 1!), ambil benda
Sifat Wumpus :
(Fully) observable? Tidak, hanya bisa persepsi local
Deterministic? Ya, hasil tindakan jelas & pasti
Episodic? Tidak, tergantung action sequence
Static? Ya, gold, wumpus, pit tidak bergerak
Discrete? Ya
Single agent? Tidak
3.LOGIC IN GENERAL-MODELS AND ENTAILMENT

Logic adalah bahasa formal untuk merepresentasikan informasi sedemikian hingga kesimpulan dapat dibuat dalam pembuatan kesimpulan pasti harus menggunakan bahasa yg benar dalam pembuatan bahasa yang tepat Syntax mendefinisikan kalimat-kalimat pada bahasa kemudian Semantics mendefinisikan arti kalimat; misal, mendefinisikan kebenaran sebuah kalimat. Entailment berarti sesuatu fakta bisa disimpulkan dari (kumpulan) fakta lain Entailment dapat juga berarti sebuah hubungan antar kalimat ( syntax) yang didasarkan pada semantics kemudian Model adalah sebuah “dunia” di mana kebenaran suatu sentence bisa diuji.

Propositionan logic: Syntax

Propositional logic adalah logika paling sederhana menggambarkan ide dasar,symbol proposisi P1,P2 dll adalah sebuah kalimat.

Logika Propositional : Semantics

Tiap model menspesifikasikan true/false untuk setiap symbol proposisi.

Tabel Kebenaran untuk Inference
Logical equivalence
Dua kalimat adalah logically equivalent if bernilai true pada model yang sama: α ≡ ß iff α╞ β and β╞ α

Validity dan satisfiability

Sebuah kalimat adalah valid jika bernilai true pada semua model.
Validity dihubungkan ke inference melalui Deduction Theorem: KB ╞ α if and only if (KB  α) is valid
Sebuah kalimat adalah satisfiable jika bernilai true pada beberapa model.
Sebuah kalimat adalah unsatisfiable jika bernilai salah pada semua model.
Satisfiability dihubungkan ke inference melalui : KB ╞ α if and only if (KB α) is unsatisfiable

Resolution

Conjunctive Normal Form (CNF)
conjunction of disjunctions of literals
clauses

Resolution inference rule (for CNF):

Forward chaining

Diberikan suatu himpunan fakta dalam workingmemory, gunakan rules untuk membangkitkan fakta baru sampai goaldicapai.

•Langkah-langkah:

1)Cocokkan bagian IF dari setiap ruleterhadap fakta-fakta dalam working memory.

2)Jika ada lebih dari satu ruleyang dapat digunakan(lebih dari satu rule yang berjalan), pilih satu yang akan diaplikasikan dengan menggunakan resolusi konflik.

3)Berlakukan ruletersebut. Jika fakta baru diperoleh, tambahkan ke working memory.

4)Stop (atau exit) ketika kesimpulan ditambahkan ke working memory atau jika ada rule yang menetapkan proses berhenti.

Backward chaining

Mesin inferensi menjelajah secara mundur (backward) rantai inferesi (chain) dimulai dari tujuan (goal) dalam working memory.

•Terdiri dari 3 langkah utama:
1. Pilih rulesyang konklusi-nya sesuai dengan goal.
2. Ganti goal dengan premis dari ruleterpilih. Jadikan sebagai sub-goals.
3. Kerjakan backwardssampai semua sub-goalsbernilai true. Ini dicapai dengan:

–Ditemukannya fakta (dalam working memory) atau

–Pengguna menyediakan informasi tersebut.

Ide: bekerja backwards dari query q: membuktikan q dengan BC,
cek jika q sudah diketahui, atau
buktikan dengan BC semua premise pada beberapa rule concluding q
Avoid loops: chek jika subgoal baru sudah siap pada stack tujuan
Avoid repeated work: check if new subgoal telah terbukti benar, atau telah gagal

Logika Proposisi

Proposisi
Logika adalah metode atau teknik yang diciptakan untukmeneliti ketepatan penalaran
serta mengkaji prinsip-prinsip penalaran yang benar dan penarikan kesimpulanyang
absah.Ilmu logika berhubungan dengan kalimat-kalimat(argumen) dan hubungan yang
ada diantara kalimat-kalimat tersebut.

Referensi :
http://share.its.ac.id/pluginfile.php/1369/mod_resource/content/1/8._Propotional_Logic.pdf

Agen Logika

Posted by : bachtiar37.blogspot.com 0 Comments

Pencarian Berbentuk/heuristik search dan Eksplorasi.

Nama : Rifqi Achmad Bachtiar

Kelas : 3KA10

Npm : 15115969

1.1 Pencarian

Pencarian merupakan kegiatan mendefinisikan ruang masalah untuk

masalah yang dihadapi. Ruang masalah ini dapat digambarkan sebagai himpunan

keadaan (state) atau bisa juga sebagai himpunan rute dari keadaan awal (initial

state) menuju keadaan tujuan (goal state). Langkah kedua adalah mendefinisikan

aturan produksi yang digunakan untuk mengubah suatu state ke state lainnya.

Langkah terakhir adalah memilih metode pencarian yang tepat sehingga dapat

menemukan solusi terbaik dengan usaha yang minimal.

Metode-metode pencarian pada teknik searching diantaranya[8] :

1. Pencarian tidak berbekal informasi / buta (Blind/Un-informed Search)

a. Breadth-First Search (BFS)

b. Depth-First Search (DFS)

c. Depth-Limited Search (DLS)

d. Uniform Cost Search (USC)

e. Iterative-Deepening Search (IDS)

f. Bi-Directional Search (BDS)

2. Pencarian berbekal informasi (Heuristik)

a. Generate-and-Test

b. Hill Climbing

c. Simulated Annealing

d. Best-First Search (BFS)

e. Greedy Best-First Search

f. A* (A star)

1.2 Metode Pencarian Heuristic

Kata Heuristic berasal dari sebuah kata kerja Yunani, heuriskein, yang

berarti „mencari‟ atau „menemukan‟. Dalam dunia pemrograman, sebagian orang

menggunakan kata heuristic sebagai lawan kata dari algoritmik, di mana kata

heuristic ini diartikan sebagai suatu proses yang mungkin dapat menyelesaikan suatu masalah tetapi tidak ada jaminan bahwa solusi yang dicari selalu dapat

ditemukan. Heuristic memperbaiki proses pencarian solusi walaupun tidak harus

sampai mengatasi kasus terburuk (worst case scenario). Heuristik ini

mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan

mengorbankan kelengkapan (completeness). Algoritma ini biasanya mencari

solusi yang dekat dengan solusi terbaik dan proses pencariannya cepat dan mudah.

Terkadang algoritma ini dapat menjadi akurat dan menemukan solusi terbaik,

tetapi algoritma ini tetap disebut heuristic hingga solusi terbaik itu terbukti untuk

menjadi yang terbaik. Fungsi heuristic h(n) adalah perkiraan biaya termurah dari

node n ke node tujuan. Fungsi heuristic melambangkan cost yang akan

dikeluarkan agent jika memilih node tertentu.

1.3 Metode A* Heuristic

Metode A* dikembangkan oleh Peter Hart, Nils Nilsson, dan Bertram

Raphael, mereka juga menyebut metode tersebut dengan sebutan algoritma A,

dengan menggunakan metode ini dan dengan heuristic yang tepat menghasilkan

sebuah hasil yang optimal, yaitu A*. Secara umum, depth-first search (DFS) dan

breadth-first search (BFS) adalah dua kasus spesial dari metode A*. Algoritma

Djikstra‟s merupakan kasus yang paling special dari A*, di mana h(x) = 0 untuk

semua x [8].

Metode A* tanpa fungsi heuristic yang baik akan memperlambat pencarian

dan dapat menghasilkan rute yang tidak tepat. Fungsi heuristic yang sempurna

akan membuat metode A* langsung menuju final node tanpa harus mencari

kearah lain. Sehingga jika fungsi heuristicnya terlalu underestimate akan

menyebabkan algoritma ini beranggapan bahwa ada rute lain yang lebih baik.

Untuk fungsi heuristic yang underestimate, bila nilainya terlalu rendah akan

menyebabkan algoritma ini seperti algortima Djikstra’s yang mencari ke segala

arah yang mungkin. Hal ini dikarenakan tidak ada informasi yang cukup

mengenai masalah yang dihadapi, sehingga menyebabkan metode A* melakukan

pencarian lebih banyak dan lebih lama.

Berdasarkan ilmu komputer, A* (disebut “A star”) adalah sebuah graph

atau metode tree search yang digunakan untuk mencari jalan dari sebuah node

awal ke node tujuan (goal node) yang telah ditentukan, metode ini menggunakan

“estimasi heuristic” h(x) pada setiap node untuk mengurutkan setiap node x

berdasarkan estimasi rute terbaik yang melalu node tersebut. Dalam prosesnya

metode ini akan mengunjungi setiap node berdasarkan urutan yang dihasilkan dari

estimasi heuristic ini. Metode A* adalah salah satu contoh dari metode best-first

search.

Masalah pencarian rute di mana metode A* sering digunakan, A* secara

bertahap membangun semua rute yang mengarah mulai dari titik awal sampai

akhirnya mencapai titik akhir. Metode A* hanya membangun rute yang mungkin

digunakan untuk mencapai tujuan. Untuk mengetahui rute mana yang

memungkinkan mengarah ke titik akhir, A* menggunakan estimasi heuristic jarak

dari sembarang node ke node tujuan. Dalam kasus pencarian rute, ini bisa jadi

sama dengan jarak lurus antara dua titik, di mana biasanya merupakan perkiraan

dari jarak jalan.

Hubungan antara heuristic dengan algoritma A* [8]:

1. Apabila h(n) selalu bernilai 0, maka hanya g(n) yang akan berperan, dan

A* berubah menjadi Algoritma Dijkstra, yang menjamin selalu akan

menemukan jalur terpendek.

2. Apabila h(n) selalu lebih rendah atau sama dengan ongkos perpindahan

dari titik n ke tujuan, maka A* dijamin akan selalu menemukan jalur

terpendek. Semakin rendah nilai h(n), semakin banyak titik-titik yang

diperiksa A*, membuatnya semakin lambat.

3. Apabila h(n) tepat sama dengan ongkos perpindahan dari n ke tujuan,

maka A* hanya akan mengikuti jalur terbaik dan tidak pernah memeriksa

satupun titik lainnya, membuatnya sangat cepat. Walaupun hal ini belum

tentu bisa diaplikasikan ke semua kasus, ada beberapa kasus khusus yang

dapat menggunakannya.

4. Apabila h(n) kadangkala lebih besar dari ongkos perpindahan dari n ke

tujuan, maka A* tidak menjamin ditemukannya jalur terpendek, tapi

prosesnya cepat.

5. Apabila h(n) secara relatif jauh lebih besar dari g(n), maka hanya h(n)

yang memainkan peran, dan A* berubah menjadi BFS.

1.4 Aplikasi Metode A* Heuristic

Metode A* biasanya diaplikasikan dalam kasus pathfinding. Terdapat

beberapa hal yang perlu didefinisikan terlebih dahulu dalam kasus pathfinding

dengan penerapan algoritma A*. Adapun istilah-istilah yang akan dibahas yaitu

path, open list, closed list, nilai f, g dan n.

Algoritma ini menggunakan dua senarai yaitu open dan closed. open

adalah senarai (list) yang digunakan untuk menyimpan simpul-simpul yang

pernah dibangkitkan dan nilai heuristiknya telah dihitung tetapi belum terpilih

sebagai simpul terbaik (best node) dengan kata lain, open berisi simpul-simpul

masih memiliki peluang untuk terpilih sebagai simpul terbaik, sedangkan closed

adalah senarai untuk menyimpan simpul-simpul yang sudah pernah dibangkitkan

dan sudah pernah terpilih sebagai simpul terbaik. Artinya, closed berisi simpulsimpul

yang tidak mungkin terpilih sebagai simpul terbaik (peluang untuk terpilih

sudah tertutup).

1. Open list adalah list yang menyimpan kemungkinan path yang akan

diperiksa. Open list dibuat terurut berdasarkan nilai f. Open list digunakan

untuk menentukan secara selektif (berdasarkan nilai f) jalan yang dikira

lebih dekat menuju pada path tujuan. Open berisi simpul-simpul yang

masih memiliki peluang untuk terpilih sebagai simpul terbaik (best node).

2. Closed adalah senarai (list) untuk menyimpan simpul-simpul yang sudah

pernah dibangkitkan dan sudah pernah terpilih sebagai simpul terbaik (best

node) atau senarai yang menyimpan jalan yang sudah diperiksa dari open

list. Artinya, closed berisi simpul-simpul yang tidak mungkin terpilih

sebagai simpul terbaik (peluang untuk terpilih sudah tertutup). Kedua list

(open list dan closed list) ini bertujuan juga untuk menghindari

penelusuran jalan (rute) berulangkali yang memang sudah diidentifikasi

agar tidak masuk kembali ke dalam open list.

3. Nilai F adalah cost perkiraan suatu path yang teridentifikasi. Nilai F

merupakan hasil dari f(n).

4. Nilai G hasil dari fungsi g(n), adalah banyaknya langkah yang diperlukan

untuk menuju ke path sekarang.

5. Nilai N untuk setiap simpul (node) harus memiliki informasi nilai h(n),

yaitu estimasi harga simpul tersebut dihitung dari simpul tujuan yang

hasilnya menjadi nilai H.

Fungsi f sebagai estimasi fungsi evaluasi terhadap node n, dapat dituliskan

[8] :

f(n) = g(n) + h(n)….[2.1]

dengan :

f(n) = fungsi evaluasi ( jumlah g(n) dengan h(n) )

g(n) = biaya (cost) yang dikeluarkan dari keadaan awal sampai keadaan n

h(n) = estimasi biaya untuk sampai pada suatu tujuan mulai dari n

Pergerakan diagonal diperbolehkan, maka digunakan fungsi heuristic

Non-Manhattan Distance. Maka fungsi heuristic yang digunakan adalah sebagai

berikut :

h_diagonal(n) = – (abs(n.x-goal.x) + abs(n.y-goal.y))….[2.2]

h_orthogonal(n) = (abs(n.x-goal.x) + abs(n.y-goal.y))….[2.3]

h(n) = h_diagonal(n) + (h_orthogonal (n) – (2 * h_diagonal(n)))….[2.4]

dengan :

x = representasi titik absis

y = representasi titik ordinat

2.3.3.4 Metode Simplified Memory-Bounded A* (SMA*)

Simplified Memory-Bounded A* (SMA*) merupakan pengembangan dari

algoritma A*. Algoritma SMA* merupakan penggabungan dari greedy search

yang meminimalisir perkiraan pencarian harga dan uniform cost search yang

meminimalisir harga sampai selesai [8].

Algoritma SMA* bersifat admissible. Ini berarti apabila solusi ada, solusi

yang ditemukan pertama adalah solusi yang optimal. SMA* bersifat admissible

bila memenuhi syarat-syarat, yaitu: di dalam graph state space setiap node

memiliki successor yang terbatas, setiap arc pada graph memiliki biaya yang

lebih besar dari 0, dan heuristic untuk setiap node n, h(n)< h*(n). SMA *

dikatakan complete dan optimal dengan mengasumsikan sebuah heuristic yang

admissible dan konsisten.

Simplified Memory-Bounded A* ini dikembangkan karena algoritma A*

menggunakan banyak memory sehingga menghabiskan memory untuk pencarian.

Algoritma ini menjalankan best first search selama memory masih tersedia,

apabila memory penuh maka node dengan nilai terburuk dibuang, namun nilai

terbaik disimpan pada node atasnya. Jika ruang memory mencukupi untuk semua

node pada tree dalam jalur pencarian, maka repeated states tidak akan diulang

sehingga pencarian akan menjadi optimal.

Aturan-aturan SMA* [8]:

1. Jika mempunyai lebih dari satu simpul, maka pilih salah satu yang

mempunyai f-cost terkecil. Jangan hapus dulu simpul tersebut sebelum

mengeceknya terlebih dahulu, karena bisa jadi simpul tersebut akan

dipakai dulu oleh simpul yang lain.

2. Jika hasil f-cost dari suksesor baru yang telah dibangkitkan hasilnya lebih

kecil, maka suksesor-suksesor sebelumnya dihapus. Tetapi jika lebih

besar, maka lanjutkan dulu pencarian ke suksesor yang lebih kecil,

sebelum menghapus suksesor yang lebih besar tersebut.

3. Jika menemukan state di level yang lebih dangkal, dan mmpunyai f-cost

lebih besar, maka state tersebut juga harus dihapus.

Pencarian Berbentuk heuristik Search dan Eksplorasi

Posted by : bachtiar37.blogspot.com 0 Comments

Metode Pemecahan Masalah (Problem Solving Method)

Nama : Rifqi Achmad Bachtiar

Kelas : 3KA10

Npm : 15115969

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

Uninformed Search Algorithm

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

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.

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

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

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.

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.

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.

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)

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.

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.

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.

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/