CODEWITHSUNDEEP
searchiterative-deepening
Galactic Void
Galactic Void

Reputation: 41

Iterative deepening search : Is it recursive?

I've searched the internet about the IDS algorithm and I keep finding some example but they are all with recursion, and as I understood iterative is not recursive.. So can you please give me some examples for IDS algorithm ?(implementation would be great and without recursion)

Thanks in advance! you will be a life saver!

Upvotes: 2

Views: 1274

Answers (2)

Peer Sommerlund
Peer Sommerlund

Reputation: 512

If you are thinking in algorithm terms (not just implementation), this would mean applying iteration at all nodes of the search tree, instead of just at the root node.

In the case of chess programs, this does have some bennefits. It improves move ordering, even in the case where a branch that was previously pruned by alpha-beta is later included. The cost of the extra search is kept low by using a transposition table.

https://www.chessprogramming.org/Internal_Iterative_Deepening

Upvotes: -1

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477684

The iterative part is not recursive: at the top it is more or less:

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

This said, in most cases searching for a solution is indeed implemented recursively:

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;
}

But there exists an automatic procedure to turn any recursive program into a non-recursive one.

Upvotes: 2

Related Questions