heuristic fonksiyonu? ha?

[Mithr]

simdi arkadaslar, search algoritmalarini kullanarak 8 puzzle cozduruyorum. Uninformed search algoritmalarinda bir sorun yasamadim, fakat informed algoritmalari tam olarak anlamadim, ornek gormedim de hic.

greedy search algoritmasini kullaniyorum ve bu algoritma, frontierden bir tane node donduruyor, bu node, goal state'e en yakin node. dolayisiyla bi fonksiyon yazdirmam gerekecek o node'u secen, acaba nasil yaparim.

manhattan distance diye bir sey buldum fakat nasil implement ederim bi fikrim yok, fazla zamanim da yok hizlica arastirma yapmaya calisiyorum fakat, hazirda bilen biri varsa yardimina muhtacim hehe :D

[asinanyavuz]

sabancıda değilsin di mi sen?

[Mithr]

yok calstate suan

[Mithr]

bi yontem buldum ismini hatirlamiorm ama sanirim manhattan distance ile ayni sonucu veriyor.

goal state{0 1 2 3 4 5 6 7 8} ise, current state i goal state ile karsilastiriyorum ve esit olmayan her pozisyon icin hval degiskenini bir arttiriyorum, 0 dan baslatarak. en buyuk hval'e sahip olan node, best node oluyor. deneyecegim simdi bakalim

[Mithr]

ilerde ihtiyaci olan olur diye yaziyim, cozdum,

her node icin yerinde olmayan block sayisi kadar, olabilecek maximum g(h)'dan (benim sorumda 9 oluyor cunku 9 farkli blok var)
1 dusuyorum, ve node'da sakliyorum bunu. onun disinda node'da zaten path cost tutuyordum, node icin path cost, parent'in path costunun 1 arttirilmisi.

greedy search icin f(n) = h(n) = yerinde olmayan blok sayisi
a star icin f(n) = h(n) + g(n), g(n) path cost oluyor.

yaratilan node lar arasinda en dusuk f(n) i seciyorsunuz, taraa.

[reyou]

manhattan 2nd avenuda ali baba var,
kime sorsan gosterir.

[Penthesilea]

manhattan distance'in ne oldugunu bilmedigine sasirdim yahu cs'te ilk ogretilen seylerden bitanesi.

genel bilgi olsun diye soyleyeyim, ismi manhattan'dan geliyor (deme yav), manhattan haritasina bakarsan izgara gibi direk.

40 ve 3'un kesisimindesin mesela. 45 ve 5'e gitmek istiyorsun. gidebilecegin bircok path var, ama hangisini secersen sec her seferinde ya x ya y ekseninde bir birim ilerleyecegin icin, 7 birimden daha kisa bi path yok ortada.

en populer ve basit heuristic olmasinin sebebi de, heuristic'inin admissible olmasi icin estimated cost'un actual cost'tan kucuk esit olmasi lazim. yukarida yazdigim sebeple, manhattan distance tek dogrultuda ilerleyebildigin durumlarda her zaman admissible bi heuristic.