Expert System Lab 4

es4.py

(a, b, c, d, e, f, g, h, i, j, k, z) = range(12)

names = {a : 'a', b : 'b', c : 'c', d : 'd', e : 'e', f : 'f', g : 'g',\
h : 'h', i : 'i', j : 'j', k : 'k', z : 'z'}

cities = {'a' : a, 'b' : b, 'c' : c, 'd' : d, 'e' : e, 'f' : f, 'g' : g,\
'h' : h, 'i' : i, 'j' : j, 'k' : k, 'z' : z}

#       a, b, c, d, e, f, g, h, i, j, k, z
ways = ((0, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0), # a
        (2, 0, 0, 2, 3, 0, 0, 0, 0, 0, 0, 0), # b
        (3, 0, 0, 0, 1, 0, 2, 0, 0, 0, 0, 0), # c
        (0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0), # d
        (0, 3, 1, 0, 0, 4, 2, 0, 0, 0, 0, 0), # e
        (0, 0, 0, 1, 4, 0, 0, 3, 2, 0, 0, 0), # f
        (0, 0, 2, 0, 2, 0, 0, 0, 0, 1, 0, 0), # g
        (0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3), # h
        (0, 0, 0, 0, 0, 2, 0, 0, 0, 5, 0, 2), # i
        (0, 0, 0, 0, 0, 0, 1, 0, 5, 0, 3, 0), # j
        (0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 3), # k
        (0, 0, 0, 0, 0, 0, 0, 3, 2, 0, 3, 0)) # z

def shortest_path(start, finish):
  def neighbors(dists):
    return filter(lambda x: dists[x] != 0, range(len(dists)))

  def cost(path):
    if len(path) == 1:
      return 0

    return ways[path[0]][path[1]] + cost(path[1:])

  def go_wide(paths):
    if len(paths) == 0:
      return None

    path = paths[0]
    city = path[-1]
    if city == finish:
      return path

    children = filter(lambda c: c not in path, neighbors(ways[city]))
    next = map(lambda c: path + [c], children)

    return go_wide(sorted(paths[1:] + next, lambda x, y: cost(x) - cost(y)))

  return go_wide([[start]])

start = cities[raw_input("from ")]
finish = cities[raw_input("to ")]
print map(lambda a: names[a], shortest_path(start, finish))
raw_input()