Pencarian heuristik

• Pencarian heuristik
 Ada 4 macam metode dalam pencarian heuristik:
1). Pembangkit & Pengujian (Generate and Test)
2.) Pendakian Bukit (Hill Climbing)
3.) Pencarian Terbaik Pertama (Best First Search)
4.) Simulated Annealing

• Pencarian terbaik pertama ( Best First Search)
merupakan kombinasi dari metode depth-first search dan metode breadth-first search
dengan mengambil kelebihan dari kedua metode tersebut. Pada metode best-first search, ini , pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah,
jika ternyata node pada lebih yang lebih tinggi ternyata memiliki nilai heuristik yang lebih buruk. Kemudian penentuan node berikutnya adalah node yang terbaikyang pernah dibangkitkan, yaitu dengan cara menngunakan informasi yamg terdiri atas biaya perkiraan dan biaya sebenarnya.
 Ada 2 jenis Pencarian Terbaik Pertama ( Best First Search), yaitu :
a.) Greedy Best First Search
 biaya perkiraan f(n) = h(n)
b.) A*
• biaya perkiraan + biaya sebenarnya
• f(n) = g(n) + h(n)
 Cara Untuk mengimplementasikan metode ini yaitu dengan menggunakan graph keadaan, dan dibutuhkan 2 antrian yang berisi node-node,yaitu:
- OPEN,* berisi node,node yang sudah dibangkitkan,namun belum diuji.
- CLOSED, * Umumnya berupa antrian berprioritas yang berisi elemen-elemen dengan nilai

heuristik tertinggi
* berisi node-node yang sudah diuji

 Algoritma:
1.) Pertama Tempatkan node awal A pada antrian OPEN.
2.) Kemudian Kerjakan langkah-langkah berikut hingga tujuan ditemukan atau antrian OPEN sudah kosong:
3.) Ambil node terbaik dari OPEN;
4.) Bangkitkan semua successornya;
5.) Untuk tiap-tiap successor kerjakan:
6.) Jika node tersebut belum pernah dibangkitkan sebelumnya,kemudian evaluasi node tersebut dan masukkan ke OPEN;
7.) Jika node tersebut sudah pernah dibangkitkan sebelumnya,setelah itu ubah parent jika lintasan baru lebih menjanjikan.dan langkah terakhir adalah hapus node tersebut dari antrian OPEN

Masalah, Ruang Keadaan dan Pencarian

Untuk membangun sistem yang mampu menyelesaikan

masalah, perlu dipertimbangkan 4 hal:

– Mendefinisikan masalah dengan tepat

• Spesifikasi yang tepat mengenai keadaan awal

• Solusi yang diharapkan

– Menganalisis masalah serta mencari beberapa

teknik penyelesaian masalah yang sesuai

– Merepresentasikan pengetahuan yang perlu untuk

menyelesaikan masalah

– Memilih teknik penyelesaian masalah yang terbaik

Ruang Keadaan

(State Space)

• Suatu ruang yang berisi semua keadaan yang

mungkin

• Sehingga secara umum, untuk mendeskripsikan

masalah dengan baik, harus:

– Mendefinisikan suatu ruang keadaan

– Menetapkan satu atau lebih keadaan awal

– Menetapkan satu atau lebih tujuan

– Menetapkan kupulan aturan

• Ada beberapa cara untuk merepresentasikan

Ruang Keadaan

Penyelesaian masalah

secara umum

• Mendefinisikan suatu ruang keadaan;

• Menetapkan satu atau lebih keadaan awal;

• Menetapkan satu atau lebih tujuan;

• Menetapkan kumpulan aturan

Metode Pencarian dan

Pelacakan

• Untuk mengukur perfomansi metode pencarian,

terdapat empat kriteria yang dapat digunakan :

– Completeness : apakah metode tersebut menjamin

penemuan solusi jika solusinya memang ada?

– Time complexity : berapa lama waktu yang

diperlukan?

– Space complexity : berapa banyak memori yang

diperlukan

– Optimality : apakah metode tersebut menjamin

menemukan solusi yang terbaik jika terdapat

beberapa solusi berbeda?

Dua teknik pencarian dan pelacakan

– Pencarian buta (blind search)

• Pencarian melebar pertama (Breadth – First

Search)

• Pencarian mendalam pertama (Depth – First

Search)

– Pencarian terbimbing (heuristic search)

• Pendakian Bukit (Hill Climbing)

• Pencarian Terbaik Pertama (Best First Search

Pencarian Melebar Pertama

(Breadth-First Search)

• Semua node pada level n akan dikunjungi

terlebih dahulu sebelum level n+1

• Mulai dari akar terus ke level 1 dari kiri ke

kanan

• Kemudian ke level selanjutnya hingga solusi

Ditemukan

Keuntungan

– Tidak akan menemui jalan buntu

– Menjamin ditemukannya solusi (jika solusinya

memang ada) dan solusi yang ditemukan pasti

yang paling baik

– Jika ada satu solusi maka bread-first search akan

Menemukannya

• Kelemahannya

– Membutuhkan memori yang cukup banyak

– Membutuhkan waktu yang cukup lama

Pencarian mendalam pertama

(Depth-First Search)

• Proses pencarian dilakukan pada semua

anaknya sebelum dilakukan pencarian ke

node-node yang selevel

• Keuntungan

– Memori yang relatif kecil

– Secara kebetulan, akan menemukan

solusi tanpa harus menguji lebih banyak

lagi

Pencarian buta

(blind search)

• Kekurangan

– Memungkinkan tidak ditemukannya

tujuan yang diharapkan

– Hanya akan mendapatkan 1 solusi pada

setiap pencarian

...weellcome too TAS...

...2 minnggoe aggie TAS niieh...
..jatttah maend berrkurrang...
...huhuuuhhu...
...miinggoe deppand gag bissa poellanx cammpung giie...
..addda make uup classs...
..huuuuwwwaaaa....
...betttte,....

xg quu dapped darri SI..???

Ngaaapppa iia milllih SI ???
Gagg tauuuw….????!!!
Hahahahaha…..
Cz settauw qu denngan jammand moderrnisasii niie perrkemmbangan tekknologi semmmakind lammma cmakkind majjju …
Makkka darri ittoe karrna pullla qu gappteg ,, makka qu ammbiil SI biiar gag gappteg giie ….
Hehehehe….
Tyyyuuuz, looog dii dunniaa kerrja jammmand cekkaraang dii buttuhiind bannnend xg memmpunyaiii keahhliiand berrhubunggand dennanndh Mr. kooMp .
Tyyuuuss , loog ennnagna dii SI tuuuwh , qtta dappped iiend illmu TI jogga ….
Ennnag khannd …???
Hehehehe….

....adda appa dii FTI...???

Teppadnya tanggal 24 auggustus mpe 30 auggustus 2008 qu mulllai berrraksi di kammpuus , dimuullai dengaan ospek xg diii addain fakkulltas qu , iaallah fakultas Teknologi Informasi. Leebbih teppadna MakkraB …!!
saaT ittu MakkraB-nya diii addaiin dii Panntaran .
buuusssyeeedtthd daaah …..
wakktuuu mpe sannna naex truk,, puaannnas,,bug…..passsir end debbbu berrterbangaan dammanna”….???!!!
Tyyyus,,,
Clamma tieggha harriie qu ma kelllompok qu hiddoep dii bawwah kakkkie gunnung Pantarrran , booyooLallliiie …..
Clammma ittoe pulla kammmie tiddag mannndii …. ( buud makkkand tetttep dunndk . )
Betttapppa bauuna qtta caad ittoe ?@?
Buud di cannna qu nemmuind temmend” xg bissa kommpax caad mellakkukan smw keggiatand xg diii curruh udda end uni qtta
( cebbuttan pannitia pendammping makkkrab ) .
Caad ittoe merruppakand kennnangand xg taag terrrluppakand .
Kaarrna dii sittoelah qtta salling mengennal attoe ma laaieend ……
Huhuhuhuhuhu….. T_T

vivie's profile

……………………………..Halllu smuuaaa………………..……
Knalliend namma qu Vivi Kusuma Dewiii……. Qu laaahiier dii kotta zolllow naan puuuannnassssss buud goood , oon 10 feebrruarii 1991………………Qu annack keddua darri tiegga berrcoddarra ,, Kakag qu cowox ,, daan addeg qu cewex……. Kaddta temmend – temmend , qu tuuwh gag cewex baaannedh dallam pennampilland buud qu jogga gag cowog bannedh…… buud kaddta my pammily,, qu tuwh cewex bannendh….???? Biinguung euuy ….?@?
Laaanjjud………….
Kaddta temmend – temmend , qu tuuwh rajjind , sukka menabbung buud boorroz ,sukka mennolong , daan tiddak sommbong buud cuuex .……!!
…………………………….Huhuhuhuhu………………………………..
Eend kaddta my pammily , qu tuuwh piinteer , pattuh maa orrtuu buud sukka baanndtaah , temmpad currhad mama eend pappa , eend rajjind kee gerreja ………………….. :)
…………………………….Heeeeeeemmmmm…………………………
Qu tuuwh sukka bannend maa warrna” nettrall , buud qu jogga sukka warrna piinx…?? ....hehehehe…..
Qu palling gag sukka ma kuuccing end binnatang” xg qu liiiad buud qu gag takkud juust jiijjaig ajja ngelliatnya , hahaha , except anjjing……. ?!!
Qu tuuwh sukka bannendh makkand naasgoor ( allias nassi gorreng ) , ennnd sotto …… buud quu gag sukka ma worrtel end pissang ! ……huhuhuhu……
………………… cuukkup cekkiand ajja introduce my cellf ………………….
……………………………………….. theeeenkzz ………………………………….
…………………………………………... G_b_u……………………………………...