Math Editor

Search Algorithms

graph = {'s':['d','e','p'],'d':['b','c','e'],'e':['h','r'],'p':['q'],
         'h':['p','q'],'b':['a'],'c':['a'],'r':['f'],'f':['c','g']}

def dfs(graph, start, goal):
  stack = [(start, [start])]
  while stack:
    node, path = stack.pop()
    if node == goal: return path
    stack += sorted([(n, path + [n]) for n in graph.get(node, [])], reverse=True)
  return None

def bfs(graph, start, goal):
  queue = [(start, [start])]
  while queue:
    node, path = queue.pop(0)
    if node == goal: return path
    queue += [(n, path + [n]) for n in graph.get(node, [])]
  return None

def dfsv (graph, start, goal):
  stack = [(start, [start])]
  while stack:
    node, path = stack.pop()
    if node == goal: return path
    stack += sorted([(n, path + [n]) for n in graph.get(node, []) if n not in path], reverse=True)
  return None

def bfsv (graph, start, goal):
  queue = [(start, [start])]
  while queue:
    node, path = queue.pop(0)
    if node == goal: return path
    queue += [(n, path + [n]) for n in graph.get(node, []) if n not in path]
  return None

def dls (graph, start, goal, limit):
  stack = [(start, [start])]
  while stack:
    node, path = stack.pop()
    if node == goal: return path
    if len(path) < limit:
      stack += sorted([(n, path + [n]) for n in graph.get(node, [])], reverse=True)
  return None

def ids (graph, start, goal, limit):
  for i in range(limit):
    path = dls(graph, start, goal, i+1)
    if path: return path
  return None

graph = {'s':[('d',3),('e',9),('p',1)], 'd':[('b',1),('c',8),('e',2)], 'b':[('a',2)],'c':[('a',2)], 'e':[('h',8),('r',2)],'h':[('q',4)], 'p':[('q',15)],'r':[('f',2)], 'f':[('c',3),('g',2)]}

def ucs (graph, start, goal):
  queue = [(0, start, [start])]
  while queue:
    cost, node, path = queue.pop(0)
    if node == goal: return path
    queue = sorted(queue + [(cost + c, n, path + [n]) for n, c in graph.get(node, [])])
  return None

graph = {'s':[('a',1),('b',4)],'a':[('b',2),('c',5),('g',12)],'b':[('c',2)],'c':[('g',3)]}
heuristic = {'s':7, 'a':6, 'b':2, 'c':1, 'g':0}

def greedy (graph, start, goal):
  queue = [(heuristic[start], start, [start])]
  while queue:
    h, node, path = queue.pop(0)
    if node == goal: return path
    queue = sorted(queue + [(heuristic[n], n, path + [n]) for n, c in graph.get(node, [])])
  return None

def astar (graph, start, goal):
  queue = [(heuristic[start], 0, start, [start])]
  while queue:
    h, g, node, path = queue.pop(0)
    if node == goal: return path
    queue = sorted(queue + [(heuristic[n] + g + c, g + c, n, path + [n]) for n, c in graph.get(node, [])])
  return None

print("dfs:", dfs(graph, 's', 'g'))
print("bfs:", bfs(graph, 's', 'g'))
print("dfsv:", dfsv(graph, 's', 'g'))
print("bfsv:", bfsv(graph, 's', 'g'))
print("dls:", dls(graph, 's', 'g', 6))
print("ids:", ids(graph, 's', 'g', 6))
print("ucs:", ucs(graph, 's', 'g'))
print("greedy:", greedy(graph, 's', 'g'))
print("astar:", astar(graph, 's', 'g'))