Итеративный углубленный поиск: рекурсивен ли он?

Я искал в интернете алгоритм IDS, и я продолжаю находить некоторые примеры, но все они с рекурсией, и, как я понял, итеративный не рекурсивен. Так что вы можете дать мне несколько примеров для алгоритма IDS?(Реализация была бы отличной и без рекурсии)

Заранее спасибо! ты будешь спасателем жизни!

Источник

1 ответ

Итеративная часть не является рекурсивной: сверху она более или менее:

int limit = 0;
Solution sol;
do {
    limit++;
    sol = search(problem,limit);
} while(sol == null);
//do something with the solution.

При этом в большинстве случаев поиск решения действительно осуществляется рекурсивно:

Solution search(Problem problem, int limit) {
    return search(problem,0,limit);
}
Solution search (Problem problem, int price, int limit) {
    if(problem.solved) {
        return problem.getSolution();
    }
    for(int value = 0; value < valuerange; value++) {
        problem.assignVariable(value);
        int newprice = price + problem.price();
        if(price < limit) {
            Solution solution = search(problem,newprice,limit);
            if(s != null) {
                return solution;
            }
        }
        problem.backtrackVariable();
    }
    return null;
}

Но существует автоматическая процедура для превращения любой рекурсивной программы в нерекурсивную.

Источник

Если вы думаете в терминах алгоритма (а не только реализации), это будет означать применение итерации во всех узлах дерева поиска, а не только в корневом узле.

В случае с шахматными программами в этом есть некоторые преимущества. Это улучшает порядок ходов, даже в том случае, если позже будет добавлена ​​ветка, которая ранее была обрезана альфа-бета-версией. Стоимость дополнительного поиска остается низкой за счет использования таблицы транспонирования.

https://www.chessprogramming.org/Internal_Iterative_Deepening

Источник
Другие вопросы по тегам