search

KyoGren / Intro_AI_

0 stars 0 forks source link

Tìm hiểu lí thuyết IDS in Sokoban #8

Open KyoGren opened 1 year ago

KyoGren commented 1 year ago

Một số link lí thuyết:

https://www.educative.io/answers/what-is-iterative-deepening-search https://www.geeksforgeeks.org/iterative-deepening-searchids-iterative-deepening-depth-first-searchiddfs/

Code (hiện tại mới thấy ví dụ của IDDFS và DFID): (IDDFS) https://www.codingninjas.com/codestudio/library/iterative-deepening-searchids-vs-iterative-deepening-depth-first-searchiddfs (DFID) https://www.askpython.com/python/examples/depth-first-iterative-deepening-dfid

nguyentiendathus commented 1 year ago

Mã giả (DFS_ID):

stack <- starting position of Sokoban
depth <- 1 WHILE stack is not empty DO
IF Are crates on target THEN
    break
ELSE
    IF Is deadlock or is time >= maxtimeout THEN
        increase the depth
        pick next solution
    ELSE
        get valid moves for **Sokoban**
        FOREACH move DO
            find next state
            put it in stack
return moves