Friday, December 23, 2011

Computational economics Lecture 13


Application: Shortest Paths and Dynamic Programming

Here's a little application concerning how to find the shortest paths on a graph
  • This is a well-known problem
  • Applications in
    • Finding directions between locations
    • Operations research, robotics, etc.
  • A simple example of dynamic programming, which is one of our key topics

Outline of the Problem

Consider the following graph



We are interested in getting from node (vertex) A to node G at minimum cost
Arrows (edges) indicate the movements we can take
Numbers next to edges indicate the cost of traveling that edge
Possible interpretations
  • Minimum cost for supplier to reach a destination
  • Routing of packets on the internet (minimize time)
A quick scan of the edges shows that the optimal paths are
  • A, C, F, G at cost 8
  • A, D, F, G at cost 8

Finding Least-Cost Paths

For large graphs we need a systematic solution
Let J(v) denote the minimum cost-to-go from node v
  • Total cost from v if we take the best route
Suppose that we know J(v) for each node v



Note that J(G) = 0
Intuitively, the best path can now be found as follows
  • Start at A
  • From node v, move to any node that solves


where
  • Fv is the set of nodes which can be reached from v in one step
  • c(v, w) is the cost of traveling from v to w
Hence, if we know J, then finding the best path is trivial
But how to find J?
A little thought will convince you that, for every node v, the function J satisfies


This is known as Bellman's equation
  • That is, J is the solution to Bellman's equation
  • There are algorithms for finding this solution

Solving for J

The standard algorithm for finding J is to start with


where M is a big number
Now we use the following algorithm
  1. Set n = 0
  2. Set


  1. If Jn+1 and Jn are not equal then increment n, go to 2
In general, this sequence converges to J---the proof is omitted

Exercises

Use this algorithm to find the optimal path (and its cost) for this graph
Here the line
node0, node1 0.04, node8 11.11, node14 72.21
means that from node0 we can go to
  • node1 at cost 0.04
  • node8 at cost 11.11
  • node14 at cost 72.21
And so on, and so on
According to my calucations, the path and is cost are like this 

Solution

## Filename: shortpath.py
## John Stachurski, July 2009

def read_graph():
    """ Read in the graph from the data file.  The graph is stored
    as a dictionary, where the keys are the nodes, and the values
    are a list of pairs (d, c), where d is a node and c is a number.
    If (d, c) is in the list for node n, then d can be reached from
    n at cost c.
    """
    graph = {}
    infile = open('graph.txt')
    for line in infile:
        elements = line.split(',')
        node = elements.pop(0).strip()
        graph[node] = []
        if node != 'node99':
            for element in elements:
                destination, cost = element.split()
                graph[node].append((destination.strip(), float(cost)))
    infile.close()
    return graph

def update_J(J, graph):
    "The Bellman operator."
    next_J = {}
    for node in graph:
        if node == 'node99':
            next_J[node] = 0
        else:
            next_J[node] = min(cost + J[dest] for dest, cost in graph[node])
    return next_J

def print_best_path(J, graph):
    """ Given a cost-to-go function, computes the best path.  At each node n, 
    the function prints the current location, looks at all nodes that can be 
    reached from n, and moves to the node m which minimizes c + J[m], where c 
    is the cost of moving to m.
    """
    sum_costs = 0
    current_location = 'node0'
    while current_location != 'node99':
        print current_location
        running_min = 1e100  # Any big number
        for destination, cost in graph[current_location]:
            cost_of_path = cost + J[destination]
            if cost_of_path < running_min:
                running_min = cost_of_path
                minimizer_cost = cost
                minimizer_dest = destination
        current_location = minimizer_dest
        sum_costs += minimizer_cost

    print 'node99'
    print
    print 'Cost: ', sum_costs


## Main loop

graph = read_graph()
M = 1e10
J = {}
for node in graph:
    J[node] = M
J['node99'] = 0

while 1:
    next_J = update_J(J, graph)
    if next_J == J:
        break
    else:
        J = next_J
print_best_path(J, graph)

0 comments: