Differences about the two recursive functions of DFS

Question

I'm working on a python program from an artificial intelligence project. It's about Depth-First Search. I have one python code which works out fine:

def depthFirst(problem,start,path,result,vis):
    next=problem.getSuccessors(start)
    if problem.isGoalState(start):
        result.append(path)
        print path
    for I in next:
        if I[0] not in vis:
            vis.append(I[0])
            depthFirst(problem,I[0],path+[I[1]],result,vis)
            vis.pop()

    def depthFirstSearch(problem):
        start=problem.getStartState()
        result=[]
        depthFirst(problem,start,[],result,[])
        return result[-1]

I know that for numbers python cannot return its reference but for lists it passes its reference rather than its value.

I have written a similar program; here I use variable path instead of result:

def depthFirst(problem,start,path,vis):
    if problem.isGoalState(start[0]):
        print 'Start1',start[1]

        print 'Path',path
        l=start[1]
        path.append(l)
        path=path[0]
        print 'FindPath',path

        return

    #vis.add(start[0])
    fringe=problem.getSuccessors(start[0])
    for child in fringe:
        '''if problem.isGoalState(child):
            path.apend(child[1])

            break
            return'''
        print child
        if child[0] not in vis:
            tmppath=start[1][:]
            tmppath.append(child[1])

            vis.add(child[0])
            print 'vis=',vis
            print path
            depthFirst(problem,(child[0],tmppath),path,vis)
        print 'path=',path

def depthFirstSearch(problem):
    start=problem.getStartState()
    path=[]
    vis=set([])

    depthFirst(problem,[start,[]],path,vis)
    print path[0]
    return path[0]

But it works out a path very different from the first one. I consider the two program are the same but as I was just trying to change result to path. how come the difference.

It looks like you're not modifying `path` anywhere in your second version, just reassigning the reference to another object. — Joel Cornett, Oct 22 '12 at 06:09
I've done my best fixing your code formatting; please review the indentation of the codeblock. — Martijn Pieters, Oct 22 '12 at 06:29
"I know that for numbers python cannot return its reference..." what does this mean? There are *only* references in python. The fact is that integers are immutable and so every operation creates a new object. — Bakuriu, Oct 22 '12 at 07:41

score 0 · Answer 1 · answered Oct 22 '12 at 07:27

I've done my best adding comments to some of the problems in your code, and hopefully it will fix your problem:

def depthFirst(problem,start,path,vis):
    if problem.isGoalState(start[0]):
        l=start[1]      # just use path.append(start[1]) here
        path.append(l)  # AND why do you even need path here at all???
        path=path[0]    # if you assign path=path[0], then don't call path[0]
                        # in depthFirstSearch
        return

    # vis.add(start[0]) # Why comment this out? Move this to the top!
    fringe=problem.getSuccessors(start[0])
    for child in fringe:
        if child[0] not in vis:
            tmppath=start[1][:]
            tmppath.append(child[1])
            vis.add(child[0])  # you AREN'T discovering it yet, don't add it here!
            depthFirst(problem,(child[0],tmppath),path,vis)

def depthFirstSearch(problem):
    start=problem.getStartState()
    path=[]
    vis=set([])
    depthFirst(problem,[start,[]],path,vis)
    return path[0]  # should be path instead here since you assigned path=path[0]

Here is a fixed version that I think should work:

def depthFirst(problem,start,path,vis):
    vis.add(start[0])

    if problem.isGoalState(start[0]):
        path.append(start[1])  # still convoluted..
        path = path[0]
        return True

    fringe=problem.getSuccessors(start[0])
    for child in fringe:
        if child[0] not in vis:
            tmppath = start[1][:]
            tmppath.append(child[1])
            depthFirst(problem, (child[0], tmppath), path, vis)

def depthFirstSearch(problem):
    start=problem.getStartState()
    path=[]
    vis=set([])
    if depthFirst(problem, [start, []], path, vis):
        return path

Thanks, but I have tried your algorithm and it returns the same as my 2nd algorithm. I don't know why. The trace of 1st and 2nd algorithm is different — user1656238, Oct 22 '12 at 13:15
Thank you Kay, I know what my problem is. `fringe.reverse()` should be put before `for child in fringe` loop. This is due to the problem, as the original use stack as the data structure. Last question, I tried to substitute `tmp=start[1][:]` into `tmp=start[1]`. It should be same as they return a list and the list could append child[1] after it. But the path is actually wrong after I modified it. Could you tell me what the problem is. Thank you. — user1656238, Oct 23 '12 at 00:33
@user1656238 `tmp=start[1][:]` makes a *copy* of list `start[1]`, so that when you later modifies `tmp`, `start[1]` will not be modified. However if you do it with `tmp=start[1]`, any changes made to `tmp` *will* change `start[1]`. This is because list in Python is *mutable*. You can read more on it here: http://stsdas.stsci.edu/pyraf/python_quick_tour.html#PyMutability and here http://effbot.org/zone/python-list.htm — K Z, Oct 23 '12 at 01:20

score -2 · Answer 2 · edited May 23 '17 at 11:50

-2

I'm not very familiar with python but if you need to pass a var by reference, maybe this will help you: How do I pass a variable by reference?

edited May 23 '17 at 11:50

Community

1
1

answered Oct 22 '12 at 05:47

Daniel Alexander Karr

325
1
4
16

Differences about the two recursive functions of DFS

2 Answers2