Warning: Undefined variable $PHP_SELF in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 2
Warning: Undefined array key "word" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 5
Warning: Undefined array key "svar" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 6
Warning: Undefined array key "valg" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 7
Spanners
Greedy algorithms are based on the assumption, that from a starting point an optimal final solution can be reached by constantly taking short-seighted (or greedy) choices. Local optimum => Global optimum. This puts restricts to the types of problems which can be solved by a greedy algorithm. It must have the greedy-choice property: A globally optimal solution can be found by a series of local improvements.
But what is an optimal solution in t-spanner construction?
For the time being, let us assume that an optimal solution is a graph which is in fact a t-spanner.
The scheme
Imagine a set of vertices in need of a t-spanner.
Adding an edge between two vertices lying very close to each other might be a good idea. The path between them could not be shorter, thus keeping the t-spanner property. And any other vertex connected to one of them, would also be connected to the other by only a short extra distance.
The greedy algorithm uses this scheme to construct t-spanners. Starting with the two verticess lying closest to each other, it considers all pairs of vertices in the set. If no satisfactory short path exists between the two vertices, then an edge between them is added to the graph.
When all pairs of vertices have been considered every vertex is connected by the graph and all paths are short enough. Thus the greedy algorithm constructs a valid t-spanner.
Pseudocode
The pseudocode below illustrates this greedy algorithm.
At this site you will find several interactive applets illustrating how it works.
Figure 6: Pseudocode of the greedy algorithm
Starting point:
A graph G(V, E) consisting of a set, V, of vertices and an empty list, E, of edges.
L01:
Sort all pairs of vertices in non-decreasing order
by their euclidian distance.
L02:
For each pair:
L03:
Find a shortest path between the two vertices.
L04:
If a path exists:
L05:
If the path is short enough:
L06:
Do nothing.
L07:
If the path is too long:
L08:
Add the edge between the two vertices to E.
L09:
If no path exists:
L10:
Add the edge between the two vertices to E.
When all pairs of vertices have been handled, the graph G is a t-spanner.
The greedy algorithm vs Kruskal
Kruskals algorithm is a greedy algorithm for constructing minimum spanning trees.
In this algorithm, pairs of vertices are sorted in the same way as in L01 above. Edges are then added only if the vertices are in different parts of the graph. If no shortest path can be found, then this confirms that the vertices are indeed in different parts of the graph.
In kruskals algorithm edges should be added only if there is no path. If the greedy algorithm above is run with an infinitely large t, it gives the same result.
This means that with a sufficiently large t the greedy algorithm constructs minimum spanning trees.