The purpose of this example is to give a basic idea of a problem in optimization and to illustrate the concepts of solution space, and brute force and heuristic approaches to solving optimization problems.
The graph below consists of 9 nodes labeled A, B, C, D, E, F, G, H and I and 15 edges. Each of the edges has some weight associated with it. For example, the edge between node A and node E has weight of 5. The edge between node G and node I has a weight of 1. We might consider each weight as some kind of cost such as the number of miles a car must drive.
The goal of this problem is to identify a path starting from node A and finishing at node I without crossing the same edge twice. As the path is traversed, we sum up the weights along the way. The optimal solution to this problem will be the path with the least total cost.
Notice that for this problem, there are many possible solutions:
A -> E -> F -> I Cost: 5 + 4 + 3 = 12
A -> E -> G -> I Cost: 5 + 4 + 1 = 10
A -> B -> G -> I Cost: 3 + 7 + 1 = 11
A -> B -> C -> D -> G -> I Cost: 3 + 1 + 4 + 4 + 1 = 13
A -> B -> C -> D -> H -> I Cost: 3 + 1 + 4 + 2 + 3 = 13
A -> E -> F -> G -> B -> C -> D -> H -> I Cost: 5 + 4 + 2 + 7 + 1 + 4 + 2 + 3 = 28 and so on…
A -> E -> G -> I Cost: 5 + 4 + 1 = 10
A -> B -> G -> I Cost: 3 + 7 + 1 = 11
A -> B -> C -> D -> G -> I Cost: 3 + 1 + 4 + 4 + 1 = 13
A -> B -> C -> D -> H -> I Cost: 3 + 1 + 4 + 2 + 3 = 13
A -> E -> F -> G -> B -> C -> D -> H -> I Cost: 5 + 4 + 2 + 7 + 1 + 4 + 2 + 3 = 28 and so on…
Even with just nine nodes as in this example, a large number of solutions are possible. The number of potential solutions grows very rapidly as the number of nodes increases. We call this set of possible solutions the solution space. The goal is to choose the least cost solution from this solution space.
There are two main approaches to finding the least cost path. We might consider a brute force method where every path is enumerated and the cost is compared with others to see if it is the least cost. Such a method is guaranteed to identify the absolute lowest cost path. However, if the solution space is large, it could take us an extremely long time to identify this lowest cost path.
Another approach to solving the problem is to use a heuristic or a set of general rules that can guide us to a solution. For example, one heuristic would be at any given node, choose the path with the least cost. in the example graph above, such a heuristic results in a solution:
A -> B -> C -> D -> H -> I with a total Cost:
3 + 1 + 4 + 2 + 3 = 13
A -> B -> C -> D -> H -> I with a total Cost:
3 + 1 + 4 + 2 + 3 = 13
While this solution is not the optimal solution, it can be reached in a very short time as compared with the brute force approach. It is possible that a heuristic approach can each a solution that is much worse than the optimal solution. However, faced with the alternative of spending significant time locating the optimal solution, we may be willing to accept a sub-optimal solution if it can be reached in a short time.