Catatan Kuliah ku

dimana nilai heuristic masing-masing kota adalah

untuk menyelesaikan permasalahan 8 puzzle kita menggunakan metode Heuristic search yang Greddy Best

Sebelumnya sudah di jelaskan bahwa pada Greddy best nilai f(n) = h(n)
maka pada permassalahan 8 puzzle, menentukan nilai heuristic atau h(n)nya ada 2 cara
1. jumlah ubin yang salah tempat.
2. total jarak.

1. LETAK UBIN SALAH TEMPAT.
kalau kita lihat, banyak ubin yang salah tempat ada 6 buah

kita mulai menyelesaikan puzzle ini dengan patokan pada ubin kosong, jika kita lihat ada 3 pilihan yang dapat kita lakukan
1. naikkan ubin 7 (DOWN) jika kita hitung jmlah ubin yang salah tempat menjadi 7 buah.
2. turunkan ubin 1 (UP) ubin yang salah tempat = 7 buah.
3. geser ubin 4 ke kiri (RIGHT) ubin yang salah tempat = 5 buah. maka langkah ini lah yang di ambil.


selanjutnya ada 3 kemungkinan yang dapat kita lakukan
pindah kan 8 (UP) = 5 (banyak ubin yang salah tempat)
ppindahkan 6 (DOWN) = 5
pindahkan 3 (RIGHT) = 5
karena semuanya memiliki nilai f(n) yang sama, maka kita pilih ubin yang pertama kali kita pindahkan sehingga posisi ubin menjadi
[1    2]
[4 8 3]
[7 6 5]

kemudian ada 2 kemungkinan yang dapat kita lakukan
pindahkan 1 (LEFT) = f(n)=6 (ubin yang salah tempat)
pindahkan 2 (RIGHT) = f(n)=4 (kita pilih karena f(n) kecil
sehingga puzzle menjadi
[1 2   ]
[4 8 3]
[7 6 5]
pindahkan 3 (DOWN)
[1 2 3]
[4 8   ]
[7 6 5]

kembali muncul pilihan
pindahkan 8 (RIGHT) = f(n) = 3
pindahkan 5 (DOWN) = f(n) = 3
karena kedua pilihan memiliki nilai n yang sama maka kita pilih pilihan pertama (LEFT)
[1 2 3]
[4   8]
[7 6 5]

kemungkinan
pindahkan 4 (LEFT) = f(n)= 4
pindahkan 6 (DOWN) = f(n)= 3 (dipilih)
[1 2 3]
[4 6 8]
[7   5]
pindah 5 (LEFT) = f(n)=3 (dipilih)
pindah 7 (RIGHT) = f(n)=3
[1 2 3]
[4 6 8]
[7 5  ]

pindah 8 (UP)
[1 2 3]
[4 6  ]
[7 5 8]

pindah 6 (LEFT)= f(n)= 2. (dipilih)
pindah 3 (UP) = f(n) = 4
[1 2 3]
[4   6]
[7 5 8]

lakukan terus menerus langkah diatas sehingga nanti akan didapat perpindahan 5, dan terakhir perpindahan 8
[1 2 3]
[4 5 6]
[7 8  ] GOAL STATE ^^

selanjutnya
2. TOTAL JARAK.
contoh:

dengan patokan ubin yang kosong, kita dapatkan 3 kemungkinan yang dapat di lakukan. UP,RIGHT,LEFT.

maksud dari penambahan di bawah puzzle tersebut adalah total jarak yang harus di tempuh agar ubin tersusun.
misalnya pada kotak pertama. 1+2+1+1+1 karena
1 (jarak ubin 2 ke posisi aslinya) +
2 (jarak ubin 4 ke posisinya) +
1 (jarak ubin 1 ke posisinya) +
1 (jarak ubin 7 ke posisinya) +
1 (jarak ubin 6 ke posisinya) sehingga total nilai huristiknya = 6

karena UP memiliki nilai heuristik terkecil, kita pilih proses ini.
[243]
[1  5]
[678]
lanjutkan lagi dengan melihat kemungkinan yang dapat terjadi.
di dapat 3 kemungkinan
RIGHT
[243]
[15  ]
[678] 1+2+1+1= 5

LEFT
[243]
[  15]
[678] 1+1+1+2=5

UP
[2  3]
[145]
[678] 1+1+1 = 3 (dipilih)

selanjutnya akan terpilih LEFT
[  23]
[145]
[678] 1+1= 2

lalu DOWN
[123]
[  45]
[678]

dan terakhir RIGHT
[123]
[4  5]
[678] MENCAPAI GOAL STATE

1. BLIND SEARCHING

merupakan pencarian buta, pencarian ini tidak memiliki informasi awal.

ciri2 Blind Search
- Membangkitkan simpul berdasarkan urutan
- Kalau ada solusi, solusi akan ditemukan
- hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui)

Blid search di bagi menjadi 3
1. BFS (Breadth-first Search)atau sering disebut juga pencarian melebar
contoh

pada BFS teknik pencarian pesoalannya adalah dengan membuka node (titik) per levelnya.. sehingga pada persoalan diatas penyelesaian pada BFS adalah.

jadi urutan node yang di lalui pada pencarian BFS adalah. a,b,c,d,e,f,g,h

2. DFS (Depth-first Search)atau sering disebut juga pencarian mendalam
sesuai namanya pencarian mendalam, DFS tidak mencari solusi per level, namun mencari pada kedalaman sebelah kiri terlebih dahulu. masih menggunakan permasalahan di awal, pada DFS akan di dapatkan solusi seperti ini.

jadi solusi node yang di lalui pada DFS adalah a,b,e,h
dfs memiliki beberapa keuntungan,yaitu memori yang di gunakan tidak terlalu banyak karena tidak membuka semua node.

3. UCS (Uniform cost search) perpaduan antara BFS dan DFS
pada UCS, pencarian nya mempehatikan cost/jarak antara 1 node ke node lain.
contoh nya.

pada permasalahan diatas telah ditentukan jarak antara node. maka pada ucs akan membuka node yang memiliki nilai/cost antar node yang terendah.
pada gambar diatas jika kita buka
c = 10
b = 20
a = 10

karena nilai c dan a sama maka teserah mau buka yang mana lebih dahulu.
seandainya kita mebuka c maka kita teruskan pencariannya, jika kita buka
d = 10+5 =15
e = 10+40 = 50 (mencapai goal, namun nilai cost nya dirasa masih terlalu besar)

maka kita buka node d, lalu akan didapat
e = 10+5+30 = 45 (nilai pada pencarian ini pun terasa masih terlau besar) maka dari itu kita buka node yang kecil di awal tadi yaitu node a

setelah kita buka node a akan di dapat
e = 10 + 20 = 30 (di dapatkan goal dengan solusi terbaik)

dari kasus diatas dapat kita lihat, ada banyak cara unuk mendapatkan solusi. namun dari berbagai macam penyelesaian kasus, kita dapat mencari solusi yang paling optimal dan ini lah ke unggulan dari UCS


2. HEURISTIC SEARCHING
heuristic search merupakan metode pencarian yang memperhatikan nilai heuristik(nilai perkiraan).

heuristic memperkirakan jarak ke Goal (yang disebut dengan fungis heuristik)

salah satu contoh huristi search adalah Best First Search yang di bagi 2
1. Greddy Best
2. A* (baca A star)

kedua teknik ini memiliki persamaan dan perbedaan, persamaannya adalah sama-sama menggunakan nilai heuristic (perkiraan) perbedaannya akan dijelaskan di bawah ini

dalam heuristic search sangat di perhatikan nilai f(n) Fungsi Evaluasi yang menyataka seberapa bagus sebuah node.

heuristic function h(n) : fungsi yang menyataakan estimasi cost dari n ke goal state.

pada greddy best f(n) = h(n) dimana (* h(n) fungsi heuristik itu sendiri)
pada A* f(n) = h(n) + g(n) dimana (*g(n) merupakan aktual cost atau total jarak menuju ke n node)

contoh kasus pada teknik A*
Peta Rumania Problem

contoh kasus pada teknik Greddy Best
8 puzzle problem

Ruang masalah untuk masalah di atas dapat digambarkan sebagai himpunan pasangan bilangan bulat (x,y) yang terurut, sedemikian hingga x = 0, 1, 2, 3, atau 4 dan y = 0, 1, 2, atau 3;
x menyatakan jumlah air dalam bak ukuran 4 Liter, dan
y menyatakan jumlah air dalam bak ukuran 3 liter.
Keadaan mula-mula adalah (0,0). State tujuan adalah (2,n) untuk setiap nilai n.

Operator-opeartor (aturan produksi) yang digunakan untuk memecahkan masalah terlihat pada gambar dibawah ini.


agar lebih jelasnya coba lihat tree dari permasalahannya berikut ini
ingat bahwa x= bak 4L y= bak 3L,
Goal state bak 4L terisi 2L berarti goal statenya (2,n)

jika melihat perkembangan teknologi komputer dan pemograman secara tentatif bisa dibilang bahwa komputer itu telah dapat berpikir, seperti program catur misalnya. Tapi dapatkah ia mensimulasikan sebuah kesadaran bahwa ia adalah sebagai subjek atau individu seperti manusia? Inilah problem yang tampaknya masih belum terselesaikan dalam diskursus AI.

Lalu Problem AI dan kaitannya dengan kesadaran dibahas oleh John R. Searle dalam bukunya The Mystery of Consciousness (1997) dan artikelnya yang berjudul Minds, Brains, and Programs (1980). John Searle melihat bahwa mesin memang dalam arti tertentu mempunyai kecerdasan. Tapi ia melihat bahwa mesin hanya memilikinya secara partikular dan fungsional (Weak AI). Mesin menurutnya tidak dapat mempunyai kesadaran sebagai subjek seperti manusia (Strong AI). Ia menjelaskan hal ini lewat argumen yang dikenal dengan Chinese Room Argument.

Chinese Room Argument merupakan sebuah argumen yang menjelaskan tentang fenomena ketika kita tidak lagi mengetahui secara programatis perbedaan antara mesin dan manusia.

Anggaplah anda hanya bisa berbicara bahasa indonesia. Kemudian, anda berada di satu ruangan terisolasi dan harus menerjemahkan bahasa Cina ke dalam huruf cina yang lain. Dengan kaidah dan prosedur penerjemahan yang sudah diberikan kepada anda, anda mulai mengerjakan penerjemahan dan hasilny dikirimkan ke luar.
Inputnya mungkin berupa pertanyaan dan ouputnya merupakan jawaban. Apakah dengan keberhasilan menerjemahkan, anda sudah bisa dikatakan seorang inteligensia, seorang yang pintar?
Sebaliknya, jika tidak berhasil karena tidak bisa mengikuti kaidah dan prosedur yang sudah ditentukan, apakah anda dikatakan tidak atau kurang pintar, kurang inteligen? Tentu hasil ini masih bisa dipertanyakan.

Selanjutnya, walaupun sudah bisa memberikan jawaban yang benar, apakah anda sudah bisa dikatakan benar-benar mengerti bahasa cina? Tidak, sekalipun anda sudah berhasil mengerjakan sesuatu yang sangat berguna. Demikian pula, komputer yang bekerja dengan aplikasi AI menerjemahkan simbol-simbol pada output yang tepat menurut kaidah dan prosedur yang sudah dirancang.

Bila manusia dikonstitusikan dengan komputer dalam kaitannya dengan fenomena Chinese Room Argument, akan kita temukan kesamaan antara mesin dan manusia, yaitu ia sama-sama sebuah program atau bagian dari program itu sendiri. Namun bila kita telaah lagi akan kita temukan secara tentatif sebuah perbedaan.

Dengan merujuk argumen di atas kita pahami bahwa manusia dan mesin sebagai sebuah program memahami sebatas bentuk, bukan makna. Menurut John Searle dalam bukunya The Mystery of Consciousness, lewat Chinese Room Argument dapat diproposisikan bahwa

“semantik tidak intrinsik berada pada syntax, sehingga syntax tidak bersifat intrinsik terhadap bentuk fisik”. (John Searle, 1997: 17).

Dari sini kita pahami bahwa makna sebuah kata dalam beberapa hal adalah misteri. Karena sebuah komputer atau program dapat memahami bentuk (sintaksis) dan menjawab dengan bentuk, seolah-olah ia memahami maknanya (semantik). Sama seperti seseorang yang berada dalam kamar yang tidak mengerti tulisan China, namun lewat sebuah program ia seakan-akan dapat mengerti

Argumen John Searle memang telah memberikan penjelasan tentang fenomena robot atau super komputer yang dapat berpikir. Ia kemudian melanjutkan argumennya tentang bagaimana proses mengerti pada mesin dan manusia dapat dipahami. Apakah mesin dapat mengerti sebagaimana manusia mengerti?
Karena kita sebagai manusia dapat mengerti dalam arti verstehen seperti dalam filsafat Kant.

Pertanyaan kemudian dapat diajukan di sini: apakah pintu otomatis yang terbuka karena sinyal fotoelektrik dapat dikategorikan mengerti ketika kita akan memasukinya? John Searle melihat bahwa mesin seperti pintu otomatis tidak bisa dibilang mengerti seperti manusia mengerti. Ia membuat analogi tentang manusia yang mengerti sebuah bahasa, semisal cerita dalam bahasa Indonesia. Manusia yang mengerti cerita berbahasa Indonesia tidak sama dengan mesin yang mengerti dalam konteks gerak dan bentuk. Tentu ini akhirnya menjadi misteri, karena proses mengerti seperti halnya makna sebuah teks tak dapat dibuktikan. Karena itulah John Searle menolak Strong AI.

Fenomena super-komputer menurutnya adalah hanyalah bagian dari kecerdasan yang bersifat fungsional atau populer dengan istilah Weak AI. (John Searle, 1997:17).

Permasalahan Strong AI memang akhirnya terletak pada masalah yang dalam filsafat dikenal sebagai hermeneutika.

Hermeneutika adalah ilmu yang mengkaji tentang bagaimana manusia memahami sebuah teks. Pemikiran John Searle tentang apakah mesin mengerti seperti halnya manusia mengerti adalah contoh problem hermeneutis. Roger Schank, ahli komputer dan ilmu kognitif, melihat bahwa mesin bisa mengerti seperti halnya manusia. Karena menurutnya tujuan sebuah program dibuat adalah mensimulasi kemampuan manusia untuk mengerti sebuah cerita. Secara literal dapat dikatakan bahwa mesin secara programatis dapat meniru manusia, namun seperti kita ketahui pendapat Schank disangkal oleh John Searle.

Ketidak mungkinan terciptanya Strong AI lewat Chinese Room Argument menjelaskan bahwa robot atau mesin pintar yang mempunyai pikiran dan kesadaran seperti manusia hanya berada dalam sebuah fiksi. Bahkan sekarang pikiran dalam beberapa hal tidak lagi menjadi unsur konstitutif dari kecerdasan, filsafat misalnya tidak lagi mempunyai kecederungan untuk melihat pikiran (cogito) sebagai kajian utamanya. Berakhirnya epistemologi dan kemudian tergantikan dengan hermeneutika diproposisikan oleh Richard Rorty, keutamaan tubuh dibandingkan dengan pikiran dalam memahami dunia dirumuskan dalam filsafat teknologi Don Ihde.

Misalnya sebuah komputer yang mampu menjalankan program dengan masukan berukuran n dalam waktu 10-4 x 2^n detik.
Dengan algoritma dan komputer tersebut, maka dapat dihitung bahwa untuk

n=10, dibutuhkan waktu eksekusi kira-kira 1/10 detik
n=20, dibutuhkan waktu eksekusi kira-kira 2 menit
n=30, dibutuhkan waktu eksekusi lebih dari satu hari

misalkan kita dapat menjalankan komputer tanpa gangguan selama satu tahun, maka waktu satu tahun itu hanya dapat menyelesaikan persoalan dengan masukan sebanyak 38.

Karena kita perlu menyelesaikan masalah dengan jumlah yang lebih besar, mukin kita harus membeli mesin baru yang 100 kali lebih cepat dari pada komputer semula (menjadi 10^-6). Dengan algorima yang sama, kita sekarang dapat menyelesaikan masalah denga masukan sebanyak n dalam waktu 10^-6 x 2^n detik. Bila kita menjalan kan mesin baru itu selama satu tahun penuh, kita hanya dapat menyelesaikan persoalan untuk masukan sebanyak n selama selang waktu tertentu, komputer baru itu akan dapat menyelesaikan persoalan dengan masukan paling banyak n + 7 dalam waktu yang sama.

Sebagai gantinya kita memutuskan untuk menaruh perhatian padan algoritmanya. Misalkan kita menemukan sebuah algrotima baru yang dapat menyelesaikan masalah semula dalam waktu orde kubik (n^3). Bayangkan lah dengan menggunakan komputer pertama, algoritma baru ini dapat menyelesaikan masalah dengan masukan sebanyak n dalam dalam waktu 10^-4 x n^3 detik. Dalam waktu satu hari kita dapat menyelesaikan masalah dengan jumlah masukan lebih besar dari 900; dan dalam waktu satu tahun komputasi ukuran masukan yang dapat diselesaikan hampir mencapai 6800 lebih bahkan dengan komputer yang kedua jumlah masukan yang dapat diproses selama satu tahun komputasi mejadi lebih banyak lagi banyak lagi, yaitu 31.500 lebih.

Hal ini diperlihatkan pada gambar dibawah ini. Jelaslah bahwa algoritma kedua lebih mangkus yang berarti lebih bagus dibandingkan degan algitma pertamanya.


Kita dapat mengukur waktu yang diperlukan oleh sebuah algoritma dengan menghitung banyaknya operasi/instruksi yang dieksekusi.

Jika kita mengetahui besaran waktu (dalam satuan detik) untuk melaksanakan sebuah operasi tertentu, maka kita dapat menghitung berapa waktu sesungguhnya untuk melaksanakan algoritma tersebut.

Contoh 1. Menghitung rata- rata

a1 a2 a3 … an

Larik bilangan bulat

Kita lihat procedure berikut ini

procedure HitungRerata(input a1, a2, ..., an : integer, output r : real)
{ Menghitung nilai rata-rata dari sekumpulan elemen larik integer a1, a2, ..., an.
Nilai rata-rata akan disimpan di dalam peubah r.
Masukan: a1, a2, ..., an
Keluaran: r (nilai rata-rata)
}
Deklarasi
k : integer
jumlah : real

Algoritma
jumlah←0
k←1
while k ← n do
jumlah←jumlah + ak
k←k+1
endwhile
{ k > n }
r ← jumlah/n { nilai rata-rata }

banyaknya operasi/instruksi
(i) Operasi pengisian nilai (jumlah←0, k←1, jumlah←jumlah+ak, k←k+1, dan r ← jumlah/n)
Jumlah seluruh operasi pengisian nilai adalah
t1 = 1 + 1 + n + n + 1 = 3 + 2n

(ii) Operasi penjumlahan (jumlah+ak, dan k+1)
Jumlah seluruh operasi penjumlahan adalah
t2 = n + n = 2n

(iii) Operasi pembagian (jumlah/n)
Jumlah seluruh operasi pembagian adalah
t3 = 1
Total kebutuhan waktu algoritma HitungRerata:

t = t1 + t2 + t3 = (3 + 2n)a + 2nb + c detik

Model perhitungan kebutuhan waktu seperti di atas kurang dapat diterima:
1. Dalam praktek kita tidak mempunyai informasi berapa waktu sesungguhnya untuk melaksanakan suatu operasi tertentu

2. Komputer dengan arsitektur yang berbeda akan berbeda pula lama waktu untuk setiap jenis operasinya.

Selain bergantung pada komputer, kebutuhan waktu sebuah program juga ditentukan oleh compiler bahasa yang digunakan.

Model abstrak pengukuran waktu/ruang harus independen dari pertimbangan mesin dan compiler apapun. Besaran yang dipakai untuk menerangkan model abstrak pengukuran waktu/ruang ini adalah kompleksitas algoritma.