Graphs and Cost

• If you think of a state space with discrete transitions, you have a graph.
• There are a range of ways to modify the graph to better represent your problem.
• One way is to associate a cost with each arc. This can make sense when the graph represents travelling, or sacrifice or gain of points.
• If you do this, you want to minimize (or maximize) the cost of the arcs you traverse.
• Another technique is to associate a cost with the State.
• An example of this is board positions in chess or checkers; a chess state might give points for your pieces and subtract them for your opponents.
• Now the question is how to maximize (minimize) the points in your next (or some later future) state.