Поиск

Алгоритм поиска

В игре восьмёрки мы должны выполнить последовательность действий, чтобы перейти в целевое состояния. Для того чтобы найти искомый путь, мы систематически перебираем разные пути, используя алгоритму поиска, приведённый ниже.

function search(initialState, goalTest, actions, successor, print = true)
{
    const agenda = new Agenda()
    const explored = new Explored()
    const initialNode = new Node(null, initialState, null)
    agenda.add(initialNode)
    while(agenda.notEmpty())
    {
        const parent = agenda.getNode()
        if(goalTest(parent.state))
        {
            if(print) console.log("Solution ",parent.strPath())
            return parent.path()
        }
        else
            if(print) console.log(parent.strPath())


        explored.add(parent.state)
        for(const action of actions(parent.state))
        {
            const newS = successor(parent.state, action)
            const newN = new Node(action, newS, parent)
            if(!explored.hasState(newS))
            {
                agenda.add(newN)
            }
        }
    }
    return null
}

Реализация Agenda в виде очереди

class Agenda extends Array
{
    add(node)
    {
        this.push(node)
    }

    getNode()
    {
        return this.shift()
    }

    notEmpty()
    {
        return this.length !== 0
    }
}

Класс Agenda - наследник класса Array. В очереди, первый пришедший, выходит первым. В этом случае сначала будут рассматриваться узлы ближайшие к родителю, такой алгоритм называют поиском сначала в ширину.

Реализация класса Explored

class Explored extends Object
{
    add(state)
    {
        this[state.toString()] = true
    }

    hasState(state)
    {
        return Boolean(this[state.toString()])
    }
}

Восьмёрки