3.md

Workshop 3

• problems_3.pdf
• solutions_3.pdf

3. Pseudo Code for

• BrFS

  closed = set()
  opened = util.Queue()
  curState = problem.getStartState()
  path = []
  bestG = {}
  opened.push((curState, path))
  while not opened.isEmpty():
      curState, path = opened.pop()
      g = problem.getCostOfActions(path)
      if problem.isGoalState(curState):
          return path
      if curState not in closed:
          closed.add(curState)
          bestG[curState] = g
          successors = problem.getSuccessors(curState)
          for sucPos, action, cost in successors:
              if sucPos not in closed:
                  sucPath = path + [action]
                  gValue = problem.getCostOfActions(sucPath)
                  hValue = 0
                  w = 0
                  fValue = gValue + w*hValue
                  opened.push((sucPos, sucPath))
  

• DFS

  closed = set()
  opened = util.Stack()
  curState = problem.getStartState()
  path = []
  bestG = {}
  opened.push((curState, path))
  while not opened.isEmpty():
      curState, path = opened.pop()
      g = problem.getCostOfActions(path)
      if problem.isGoalState(curState):
          return path
      if curState not in closed:
          closed.add(curState)
          bestG[curState] = g
          successors = problem.getSuccessors(curState)
          for sucPos, action, cost in successors:
              if sucPos not in closed:
                  sucPath = path + [action]
                  gValue = problem.getCostOfActions(sucPath)
                  hValue = 0
                  w = 0
                  fValue = gValue + w*hValue
                  opened.push((sucPos, sucPath))
  

• A*

  closed = set()
  opened = util.PriorityQueue()
  curState = problem.getStartState()
  path = []
  bestG = {}
  opened.push((curState, path), heuristic(curState, problem))
  while not opened.isEmpty():
      curState, path = opened.pop()
      g = problem.getCostOfActions(path)
      if problem.isGoalState(curState):
          return path
      if (curState not in closed) or (g < bestG[curState]):
          closed.add(curState)
          bestG[curState] = g
          successors = problem.getSuccessors(curState)
          for sucPos, action, cost in successors:
              if sucPos not in closed:
                  sucPath = path + [action]
                  gValue = problem.getCostOfActions(sucPath)
                  hValue = heuristic(sucPos, problem)
                  w = 1
                  fValue = gValue + w*hValue
                  opened.push((sucPos, sucPath), fValue)
  

• Uniform Cost

  closed = set()
  opened = util.PriorityQueue()
  curState = problem.getStartState()
  path = []
  bestG = {}
  opened.push((curState, path), 0)
  while not opened.isEmpty():
      curState, path = opened.pop()
      g = problem.getCostOfActions(path)
      if problem.isGoalState(curState):
          return path
      if curState not in closed:
          closed.add(curState)
          bestG[curState] = g
          successors = problem.getSuccessors(curState)
          for sucPos, action, cost in successors:
              if sucPos not in closed:
                  sucPath = path + [action]
                  gValue = problem.getCostOfActions(sucPath)
                  hValue = 0
                  w = 0
                  fValue = gValue + w*hValue
                  opened.push((sucPos, sucPath), gValue)