I must implement , in Lisp , a depth-search algorithm in an implict graph (namely a graph where I have the starting node, the goal node, and the successor function ,f, that give a node create his successors). There is a depth limit d. The algorithm must return a path (obviously cannot be minimal).
My problem is how manage the loop .
My first question is: If I use this following stupid method work it?
I have 2 list. The first is a LIFO ((I call it list1) when I insert in the head the succesor nodes. Evry time I expand the node in the head.
In the second list (I call it list2) I keep a list where put all nodes already met and every time that I expand a node I check if successor nodes obtained are in the list above (list2). For the nodes that are in it (in list2) I don't insert in list1.
This method sucks because in the worst case i must keep in list2 all nodes of the graph and I must search at every expansion if some successor nodes are in the list2. (for example, this method certainly works with breadth-first search) But at least it works? Or I would risk to cut relevant paths ?
Second question is: How can I implement it efficiently (pseudocode, or simply idea)?
Thanks in advance