METODE PENCARIAN IDS(Iterative Deepening Search)

Iterative Deepening Search 

 Menggunakanbatasanlevel(kedalaman)padasetiapiterasipencariannya.IdetersebutdigunakanpadaIDSdenganbatasanyangberupaflimit(nilaigabunganantaranilaisebenarnyadengannilaiperkiraan).Pada IDSinisetiapiterasiakanmengembalikannilaiflimitbaruyangakandigunakansebagaibatasanpencarianuntukiterasiberikutnya.
Dalamalgoritma IDS mungkinakanmembangkitkansimpul-simpul yang samasecaraberulang-ulang. Hal ini membutuhkanwaktu yang lama, sehingga time-complexitynyatinggi.Bagaimanapun, keuntunganutama IDS adalahjumlahmemori yang dibutuhkanmenjadijauhlebihsedikit. Secara detail, algoritma IDS bias dijelaskansepertiberikut :
Function IDS(masalah) returns solusi
Inputs :masalah, sebuahmasalah
Local variables: f-limit, batasan f-Cost saatini, root, sebuahsimpul
Root <-- MAKE-SIMPUL(INITIAL-STATE[masalah])
      f-limit<--f-Cost(root)
                   l oop do
           solusi, f-limit <--DFS-CONTOUR(root,f-limit)
            if f-limit sama dengan INFINITE then return gagal
end

functionDFS-CONTOUR(simpul, f-limit) returns solusi, batasan f-Cost yang baru
             inputs :simpul, sebuah simpul
                  f-limit, batasan f-Cost saat ini
                      local variables : next-f, batasan f-Cost untuk batasan berikutnya, pada awalnya variable ini     diberinilai takhingga (INFINITE)
         if f-Cost [simpul] > f-limit then return null, f-Cost [simpul]
           if GOAL-TEST [problem] (STATE[simpul]) then return simpul, f-limit
             forsetiapsimpul s yang menjadi SUCCESSOR (simpul) do
             solusi, new-f <--DFS-CONTOUR(s,f-limit)
               ifsolusibukan null then return solusi,f-limit
               next-f<--MIN(next-f,new-f)
               end
return null, next-f