Artificial Intelligence Question posted in
ChatGBT is becoming a world-wide phenomena, try it out here.

Differences about the two recursive functions of DFS – Artificial Intelligence

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.

Tags:

2

Answers


  1. 0

    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?

    Login or Signup to reply.
  2. 0

    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
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search