I am taking an introductory class AI and we have to know how to code IDA* algorithm in scheme. I am a novice when it comes to scheme and I was wondering does anyone have any information on where I can get some info on how to even start programming the following algorithm using scheme. function ITERATIVE-DEEPENING-SEARCH returns a solution, or failure inputs: problem, a problem for depth <- 0 to infinity do result <- DEPTH-LIMITED-SEARCH(problem, depth) if(result != cutoff then return result

I can't help you... but I have to wonder... why scheme?

Basically he only knows how to write in scheme so he makes all of our stuff in scheme which no one actually knows!

Here is the book to learn scheme from http://www.htdp.org/2003-09-26/Book/

now then do you have any questions about IDA* or was it a i don't know scheme moment?

Quote: Original post by InnocuousFox
I can't help you... but I have to wonder... why scheme?

Scheme is kind of nice, I think, especially if you use it in a very functional style (i.e., the way it's designed).

I actually have MANY questions but the first and most important is I have no clue where to even begin on this algorthim. Is there any code snipets that can help me get started or can you tell me in words what the algorithm is doing in scheme? Either of those would a great help.

Quote: Basically he only knows how to write in scheme so he makes all of our stuff in scheme which no one actually knows!

I find that very unlikely. A likelier explanation is that he's one of the people who knows that scheme is a great teaching language.

Quote: can you tell me in words what the algorithm is doing in scheme?

It's doing the same thing in scheme that it'd do in any other language. You must first understand the algorithm to implement it.

Once you understand the algorithm, HOW to do it in scheme is the question.

Quote: Is there any code snipets that can help me get started

I haven't written scheme in a while, so I felt like writing breadth first search in scheme. It's a short hop from BFS to IDFS, so this should help. Here goes:

;; Return the first element in list l that satisfies predicate pred?, or the atom 'not-found(define (find pred? l)  (cond ((null? l)         'not-found)        (#t         (let ((elt (car l))               (elts (cdr l)))           (cond ((pred? elt)                  (list 'found elt))                  (#t                    (find pred? elts)))))));; Apply a function f that returns lists to each element in a list, and concatenate the results(define (concatmap f l)  (define (cm-helper res f l)    (cond ((null? l)           res)          (#t           (let ((elt (car l))                 (elts (cdr l)))             (cm-helper (merge-lists (f elt) res) f elts)))))  (cm-helper (list) f l));; Make a list containing all elements in l1 and l2 (define (merge-lists l1 l2)  (cond ((null? l1)         l2)        (#t         (let ((elt (car l1))               (elts (cdr l1)))           (merge-lists elts (cons elt l2))))));; Expand all nodes by one level(define (deepen expand-f nodes)  (concatmap expand-f nodes));; Search to a depth of max-depth, returning either a list of the atom 'found and an element satisfying pred? ;; or the atom 'not-found. This is parametrized in terms of:;; 1) A function expand-f that, for a given node, returns;; a list of its successors (possibly empty).;; 2) A function pred? that returns true if the node is the one we're looking for;; 3) A list nodes, containing the root node.(define (bfs max-depth expand-f pred? nodes)  (cond ((= max-depth 0)         'not-found)        (#t         (let ((search-res (find pred? nodes)))           (cond ((eq? search-res 'not-found)                  (bfs (- max-depth 1) expand-f pred? (deepen expand-f nodes)))                 (#t                  search-res))))))

That's extremely straightforward, standard, and decently efficient scheme code. I think it's bug free. Note that all function calls are tail calls, which means the compiler turns them into iterations: that's basically the first thing to worry about when writing efficient scheme code.

Here's an example search tree, parametrized in terms of the node-expand, pred?, and initial node list. I chose the implicit representation of a binary tree in an array; it's explained in wikipedia:

http://en.wikipedia.org/wiki/Binary_heap#Heap_implementation

;; An example node expansion function and a predicate that simply looks for the node called 26.;; In this example case, nodes have two successors and we have a binary tree.;; Consider integers as nodes and expand them like so. If integers are considered indices of an array, the nth;; expansion corresponds to the nth level of a binary tree stored in that array. That's a neat implicit data structure;; generally used to compactly represent heaps, for example. http://en.wikipedia.org/wiki/Binary_heap#Heap_implementation(define (example-expand-num n)  (list (+ (* 2 n) 1) (+ (* 2 n) 2)))(define (example-pred? n)   (= n 26));; If you run it in the interpreter, you should get this:> (bfs 30 example-expand-num example-pred? (list 0))(found 26)

Thanks for that, I am sure that will help I will probably have more questions very soon!

I have several new questions that I would like to ask. First of all in your example of BFS the elt stand for what exactly in your code? I follow your code pretty well just get a little bit confused as to what elt that stands for, 2nd the res variable is another one that I am unsure of what res is meant to be as well. Finally the project I am working on is also suppose to use A* Graph Search Algorithm and the IDFS search algorithm in order to solve NxM tile puzzle. I was just wondering how the code example you've shown could help solve the NxM puzzle and if you have any suggestions on how to start the A* process that would be great. Thanks a ton.

Quote: I have several new questions that I would like to ask. First of all in your example of BFS the elt stand for what exactly in your code?

Element. Elts stands for elements. That's what I'm looking at; if I have a list alist, elt is (car alist), elts is (cdr alist), this is the invariant:

(cons (car alistl) (cdr alist)) == alist
(cons elt elts) == alist

I'm destructuring the list.

Quote: 2nd the res variable is another one that I am unsure of what res is meant to be as well.

Res stands for result; I'm explicitly passing the state around in the extra argument res in a helper function to make the function tail recursive. For example, the concatmap function:

(define (concatmap f l)  (define (cm-helper res f l)    (cond ((null? l)           res)          (#t           (let ((elt (car l))                 (elts (cdr l)))             (cm-helper (merge-lists (f elt) res) f elts)))))  (cm-helper (list) f l))

could be written like this, but it would run in linear space instead of constant space because the last call is not a tail call:

(define (concatmap2 f l)  (cond ((null? l)         (list))        (#t         (let ((elt (car l))               (elts (cdr l)))           (merge-lists (f elt) (concatmap2 f elts))))))

Quote: I was just wondering how the code example you've shown could help solve the NxM puzzle

The algorithm is parametrized by providing the root node of the search problem, the node-expand function (takes a node and returns its children) and by the predicate that takes a node and decides whether it satifies your condition.

Find a way to represent a node in the NxM search problem, write a function that node-expands nodes in the NxM puzzle, and a function that decides whether a node is a solution to the puzzle, and call the bfs function with those parameters.

Quote: if you have any suggestions on how to start the A* process that would be great.

Start thinking about how to implement a priority queue in Scheme.