Programlama | Programlama Dilleri | C Programlama Dili |C++

Hata
  • XML Parsing Error at 1:82. Error 9: Invalid character
Anasayfa Programlama Haskell Labirentte Yolun Bulunmas?


Labirentte Yolun Bulunmas?

LAB?RENTTE YOLUN BULUNMASI

            Labirent içerisinde bir hedef hücre vard?r. Amaç labirent içerisinde verilen hücreden bu hedef hücreye ula??p, verilen hücre ile hedef hücre aras?ndaki yolu bulmakt?r. Çözüm yöntemi Lee algoritmas?na benzer bir yolla labirenti çözmeye çal???r.

            Ba?lang?ç olarak 4 farkl? yönde arama i?lemi yap?l?r. Hedef durumuna ula?mak için bu 4 yöne bak?l?r.

Labirentte dörtlü hareket yönü

            Bir yönde hareket yap?l?rken özyinelmeli olarak arama fonksiyonu ça?r?l?r. Ba?lang?çta B noktas? için 4 yönde de fonksiyon ça?r?l?r. Diyelim ki ilk olarak fonksiyon a?a?? yön içi ça?r?ld?. Fonksiyonun bu kademesinde bu hücreye gelinen yön gidilecek yönler aras?ndan ç?kar?l?r. Örne?in fonksiyonun a?a?? yönde ça?r?ld???nda gidece?i yönler a?a??daki ?ekilde gösterilmi?tir.

Labirentte dörtlü hareket yönü

            E?er bir hücre fonksiyonun bir kademesinde i?lenmi?se bu hücre “Gidildi” olarak i?aretlenir. Böylelikle fonksiyonun di?er kademelerinde tekrar bu dü?üme bak?lmaz. Hücre e?er duvarsa daha önce gidilmi? hücre ile ayn? muameleyi görür.

            Bu ?ekilde gelinen hücrelerden herhangi birisi hedef durumu ise algoritma geriye do?ru i?leyerek gidilecek yönleri olu?turur.

 

VER? YAPILARI

Hucre ( data Hucre = Bos | Gidildi | Duvar | Hedef )

Labirent içerisindeki hücreleri temsil etmek için kullan?lan veri tipidir. Dört farkl? de?er alabilir. E?er de?eri “Hedef” ise gidilmesi istenen hedef hücre oldu?u anlam?na gelir. De?eri “Duvar” ise bu hücrenin bir duvar oldu?unu ve bu hücre üzerinden gidilemeyece?ini belirtir. De?eri “Bos” ise arama yap?l?rken bu hücreden geçilebilece?i anlam?na gelir. De?eri “Gidildi” ise arama yap?l?rken bu hücreden daha önce geçildi?i anlam?na gelir. Böylelikle arama esnas?nda tekrar bu hücreye bak?lmaz.

Yon ( data Yon = Yukari | Asagi | Sola | Saga )

            Yönleri belirlemek için kullan?lan veri tipidir. Labirentte arama yap?l?rken yönlere bak?larak arama yap?l?r. Bir pozisyonun kom?ular?na bak?l?rken ve hedefe giden yol olu?turulurken yönler kullan?l?r.

Pozisyon ( type Pozisyon = (Int, Int) )

            Labirentin bulundu?u ?zgara üzerindeki koordinatlar? belirlemek için kullan?lan tip tan?mlamas?d?r. ?lk de?er x eksenine, ikinci de?er de y eksenine kar??l?k gelir.


 

Labirent ( data Labirent = Labirent Int Int [[Hucre]] )

            Labirenti temsil eden veri tipidir. ?lk tamsay? de?eri labirentin geni?li?ini, ikincisi ise yüksekli?ini temsil eder. En son eleman? da hücrelerin tutuldu?u iki bir dizi gibi dü?ünebiliriz. Sonuçta bu eleman listelerin listesidir. Labirent verileri bu eleman içindedir. Yap?lmas? gereken herhangi bir de?i?iklik bu listenin içindeki elemanlar?n de?i?tirilmesiyle sa?lan?r.

Yol ( data Yol = Dur | Git Yon Yol )

            Verilen hücreden istenilen hücreye gidilecek yolun tutuldu?u özyinelemeli veri tipidir. Hedefe ula??ld???n? “Dur” verisi belirtir.

 

FONKS?YONLAR

Sil (sil :: Eq a => a -> [a] -> [a] )

            Verilen listedeki bir eleman? siler.

karsiYon ( karsiYon::Yon->Yon )

            Verilen yönlerin z?t yönünü döndüren fonksiyondur.

git (git :: Pozisyon -> Yon -> Pozisyon )

            Verilen bir koordinattan belirli bir yönde ilerleyince hangi koordinata ula??laca??n? gösteren fonksiyondur.

hucreDurumu ( hucreDurumu :: Labirent -> Pozisyon -> Hucre )

            Labirent içerisindeki verilen bir koordinattaki hücreyi geri veren fonksiyondur. E?er istenilen pozisyon labirent s?n?rlar? d???nda ise “Duvar” döndürür. Di?er durumlarda labirentin veri tipinin içinde hücrelerin bulundu?u iki boyutlu Hucre listesinde gerekli de?eri döndürür.

gelinmismi ( gelinmismi::Labirent->Pozisyon->Bool )

            Labirent içerisinde verilen pozisyondaki hücrenin hücre durumuna bakar. E?er buradaki hücre “Gidildi” ise do?ru, di?er durumlarda yanl?? döndürür.

duvarmi (duvarmi::Labirent->Pozisyon->Bool )

            gelinmismi fonksiyonuna benzerdir. Fark olarak hücre durumu “Duvar” ise do?ru, di?er durumlarda yanl?? döndürür.

hucreBlokemi (hucreBlokemi :: Labirent -> Pozisyon -> Bool )

            E?er labirentte verilen pozisyondaki hücre duvarsa veya daha önce ziyaret edilmi?se do?ru, aksi hallerde yanl?? döndüren fonksiyondur.

hareketSayisi (hareketSayisi::Yol->Int )

            Bir “Yol” içerisinde hedefe ula?mak için kaç hareket yap?lmas? gerekti?ini bulan fonksiyondur.

hucreyeGit (hucreyeGit :: Labirent -> Pozisyon -> Labirent )

            Labirentteki verilen koordinattaki hücreyi “Gidildi” olarak de?i?tiren fonksiyondur.

ara (ara :: Labirent -> Pozisyon -> [Yon] -> Maybe Yol )

            Labirentteki arama i?lemini gerçekle?tiren özyinelemeli fonksiyondur. Argüman olarak “Labirent”, “Pozisyon” ve “Yon” listesi al?r ve geriye “Maybe Yol” eleman?n? döndürür. E?er verilen pozisyondaki hücre “Hedef” hücresi ise “Just Dur” verisini döndürür. E?er gelen “Yon” listesi bo? bir liste ise “Nothing” verisini döndürür. Bu ikisi de de?ilse arama i?lemi özyinelemeli olarak devam edecektir.

            ?lk olarak yeni pozisyon ve bu pozisyondan gidilecek yönler hesaplan?r. Yeni pozisyon verilen pozisyondan verilen yönde gidilerek bulunur. Gidilecek yönler bütün yönlerden gelinen yönün tersi ç?kar?larak bulunur. Böylelikle arama i?lemi yap?l?rken gelinen yöne tekrar bak?lmaz ve program sonsuz döngüden kurtulur. Yeni pozisyonundaki hücrenin bloke olup olmad???na bak?larak özyinelemeli olarak gidilecek yönler arama fonksiyonuna iletilir. E?er yeni pozisyondaki hücre bloke de?ilse bu hücre “Gidildi” olarak i?aretlenir ve di?er yönler arama fonksiyonuna yeni pozisyon ile iletilir.

            Çözüm bulunmas? durumunda “Hedef” durumundan geriye do?ru özyineleme içerisinde yollar olu?turulur.

labirentiCoz ( labirentiCoz :: Labirent -> Pozisyon -> Maybe Yol )

Arama i?lemi ba?lang?c?nda ça?r?lan fonksiyondur. Dalga algoritmas?na göre ba?lang?ç pozisyonundan bütün yönler için ara fonksiyonunu ça??r?r.

labirentiKodla ( labirentiKodla :: [String] -> Labirent )

            labirentiCoz fonksiyonu argüman olarak “Labirent” tipinde bir veri al?r.Kullan?c?n?n elle bu veritipini olu?turmas? karma??k bir i?lemdir.Bu fonksiyon string listelerinden Labirent veritipine dönü?üm yapar.A?a??da bu string listelerinden bir tanesi verilmi?tir.

  1.  
  2.  
  3. module Labirent
  4. where
  5.  
  6.  
  7. main = putStrLn (gorsel a)
  8.          where
  9.         a = baslat 1 8
  10.                      
  11. baslat a b =cevrim (yolciz1 (labirentiKodla labirent3) (labirentiCoz (labirentiKodla labirent3) (a,b)) (a,b))
  12.  
  13. gorsel [] = ""
  14. gorsel (x:xs) =  ((show (x)) ++ "\n" ++ gorsel xs)   
  15.  
  16.  
  17. --hucrenin karaktere göre ve i?lenmesine göre durumunun tutuldu?u veri tipi
  18. data Hucre = Bos
  19.           | Gidildi
  20.           | Duvar
  21.           | Hedef
  22.           deriving (Eq, Show)
  23.  
  24. --hucrelerin, geni?lik ve enin tutuldu?u veri tipi
  25. data Labirent = Labirent Int           
  26.                          Int          
  27.                          [[Hucre]]     
  28.                 deriving Show
  29.  
  30. --koordinat düzlemi
  31. type Pozisyon = (Int, Int) 
  32.  
  33. --gidilebilecek yönleri tutan veri tipi
  34. data Yon = Yukari
  35.            | Asagi
  36.            | Sola
  37.            | Saga
  38.            deriving (Show, Enum, Eq)
  39.  
  40. --izlenen i?lemlerin tutuldugu veri tipi
  41. data Yol = Dur
  42.           | Git Yon Yol
  43.           deriving Show
  44.  
  45.  
  46. labirentiCoz :: Labirent -> Pozisyon -> Maybe Yol
  47. labirentiCoz maze here = ara maze here [Yukari .. Saga]
  48.  
  49.  
  50. --hedef durumuna veya t?kanma durumuna gelene kadar arama yapan fonksiyon
  51. ara :: Labirent -> Pozisyon -> [Yon] -> Maybe Yol
  52. ara maze here _          | hucreDurumu maze here == Hedef = Just Dur
  53. ara maze here []                                          = Nothing
  54. ara maze here (dir:dirs)                                  =
  55.   let
  56.     newPos  = git here dir
  57.     newDirs = sil (karsiYon dir) [Yukari .. Saga]
  58.   in
  59.   case hucreBlokemi maze newPos of
  60.     True      -> ara maze here dirs
  61.     otherwise -> case ara (hucreyeGit maze here) newPos newDirs of
  62.                Nothing   -> ara maze here dirs
  63.                Just path -> Just (Git dir path)
  64.  
  65. --Yone göre yeni pozisyonu belirleyen fonksiyon
  66. git :: Pozisyon -> Yon -> Pozisyon
  67. git (x, y) Yukari = (x, y - 1)
  68. git (x, y) Asagi = (x, y + 1)
  69. git (x, y) Sola  = (x - 1, y)
  70. git (x, y) Saga  = (x + 1, y)
  71.  
  72. --labirentte pozisyonu verilen hucren?n durumu
  73. hucreDurumu :: Labirent -> Pozisyon -> Hucre
  74. hucreDurumu (Labirent width height tiles) (x, y)
  75.   | x >= 0 && x < width && y >= 0 && y < height = (tiles!!y)!!x
  76.   | otherwise                                   = Duvar
  77.  
  78. --duvara veya sonuc durumuna gelindimi kontrolu
  79. hucreBlokemi :: Labirent -> Pozisyon -> Bool
  80. hucreBlokemi maze pos = (duvarmi maze pos) || (gelinmismi maze pos)
  81.  
  82.  
  83. hucreyeGit :: Labirent -> Pozisyon -> Labirent
  84. hucreyeGit (Labirent width height tiles) pos =(Labirent width height (hucreGidildi tiles pos))
  85.  
  86. --satirlar aras? hücrelerde dolan?yor
  87. hucreGidildi :: [[Hucre]] -> Pozisyon -> [[Hucre]]
  88. hucreGidildi (tl:tls) (x,y)
  89.   | y == 0  = (makeVisitedTileAtRow tl x):tls
  90.   | otherwise = tl:(hucreGidildi tls (x, y - 1))
  91.  
  92. --satir içinde hücrelerde dolan?yor
  93. makeVisitedTileAtRow :: [Hucre] -> Int -> [Hucre]
  94. makeVisitedTileAtRow (cl:cls) column
  95.   | column == 0 = Gidildi:cls
  96.   | otherwise   = cl:(makeVisitedTileAtRow cls (column - 1))
  97.  
  98. --verilen yonun tersini al?yor
  99. karsiYon dir
  100.   | dir == Saga  = Sola
  101.   | dir == Sola  = Saga
  102.   | dir == Asagi = Yukari
  103.   | dir == Yukari = Asagi
  104.  
  105. --duvar kontrolu yap?l?yor
  106. duvarmi maze (x,y)
  107.   | hucreDurumu maze (x,y) == Duvar  = True
  108.   | otherwise = False
  109.  
  110. --sonuc durumu kontrolu yap?l?yor
  111. gelinmismi maze (x,y)
  112.   | hucreDurumu maze (x,y) == Gidildi = True
  113.   | otherwise                       = False
  114.  
  115. --metni labirente ceviriyor
  116. labirentiKodla :: [String] -> Labirent
  117. labirentiKodla []   = error "Bos Labirent"
  118. labirentiKodla rows =
  119.   let
  120.     height = length rows
  121.     width  = length (head rows)
  122.   in
  123.   Labirent width height (map (map charToTile) rows)
  124.   where
  125.     charToTile '.' = Bos
  126.     charToTile '#' = Duvar
  127.     charToTile '@' = Hedef
  128.     charToTile _   = error "Bilinmeyen Hucre Tespiti"
  129.  
  130. --verilen diziden istenilen de?eri siliyorr
  131. sil :: Eq a => a -> [a] -> [a]
  132. sil _ [] = []
  133. sil y (x:xs)
  134.   | (x==y)    = sil y xs
  135.   | otherwise = x:(sil y xs)
  136.  
  137. ---------------------------------------------------------------------------------------
  138.  
  139. hareketSayisi Dur = 0
  140. hareketSayisi (Git dir path) = 1 + (hareketSayisi path)
  141.  
  142. yoluGoster Dur = "\n"
  143. yoluGoster (Git dir path) = show dir ++ "\n" ++ yoluGoster path
  144.  
  145. yoluYaz path = putStr("\nHareket sayisi>>" ++ (show (hareketSayisi path)) ++
  146.                          "\n\n" ++ yoluGoster path)
  147.  
  148. hareket Nothing = 0
  149. hareket (Just path) = hareketSayisi path
  150.  
  151. yaz Nothing = putStrLn "Çözüm yok"
  152. yaz (Just path) = yoluYaz path
  153.  
  154. -----------------------------------------------------------------------------------------
  155.  
  156. labirent1 :: [String]
  157. labirent1 =  ["########",
  158.               "#.@..#.#",
  159.               "#.#.##.#",
  160.               "###..#.#",
  161.               "#.##...#",
  162.               "#..##.##",
  163.               "#.#...##",
  164.               "#.###..#",
  165.               "#.....##",
  166.               "########"]
  167.  
  168.  
  169.  
  170. labirent2 = ["#####",
  171.              "##..#",
  172.              "##..#",
  173.              "#####"]
  174.  
  175.  
  176. labirent3 =  ["########",
  177.               "#.@....#",
  178.               "#.#.##.#",
  179.               "###..#.#",
  180.               "#.####.#",
  181.               "#....#.#",
  182.               "#.#..#.#",
  183.               "#.#.##.#",
  184.               "#......#",
  185.               "########"]
  186.  
  187.  
  188. yolCiz :: Labirent -> Yol -> Pozisyon -> Labirent
  189. yolCiz a  Dur _ = a
  190. yolCiz (Labirent genis uzun hucre) (Git a b) (x , y)=
  191.                              case a of
  192.                              Yukari -> yolCiz (hucreyeGit (Labirent genis uzun hucre) (x , y)) b (x,y-1)
  193.                              Asagi -> yolCiz (hucreyeGit (Labirent genis uzun hucre)(x , y)) b (x,y+1)
  194.                              Saga -> yolCiz (hucreyeGit (Labirent genis uzun hucre)(x , y)) b (x+1,y)
  195.                              Sola -> yolCiz (hucreyeGit (Labirent genis uzun hucre)(x , y)) b (x-1,y)
  196.                             
  197. yolciz1 a (Just Dur)= yolCiz a Dur c
  198. yolciz1 a (Just b) c = yolCiz a b c
  199.  
  200. cevrim :: Labirent -> [String]
  201. cevrim (Labirent genis uzun hucre) = map (map tileToChar) hucre
  202.                                    where
  203.                                    tileToChar Bos = '.'
  204.                                    tileToChar Duvar = '#'
  205.                                    tileToChar Hedef = '@'
  206.                                    tileToChar Gidildi = 'o'
  207.  
  208.  

Program?n Tamam?n? A?a??daki Linkten ?ndirebilirsiniz

Linki Görebilmeniz ?çin Üye Olman?z Gerekmektedir...

Üye Kay?t

 

 

Dictionary
x
+
?
Null.
Dictionary
x
+
?
Null.
Dictionary
x
+
?
Null.
Yorumlar (0)
Sadece kayıtlı kullanıcılar yorum yazabilir!
Son Güncelleme ( Salı, 27 Eylül 2011 03:46 )  
amınıza koyayım amınıza koyayım amınıza koyayım amınıza koyayım amınıza koyayım amınıza koyayım