Content deleted Content added
m v2.04b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation) |
m Add link to the Online Algorithm page within the Graph Exploration section to improve clarity of definition. |
||
Line 78:
==Graph exploration==
The problem of graph exploration can be seen as a variant of graph traversal. It is an [[Online algorithm|online problem]], meaning that the information about the graph is only revealed during the runtime of the algorithm. A common model is as follows: given a connected graph {{nowrap|1=''G'' = (''V'', ''E'')}} with non-negative edge weights. The algorithm starts at some vertex, and knows all incident outgoing edges and the vertices at the end of these edges—but not more. When a new vertex is visited, then again all incident outgoing edges and the vertices at the end are known. The goal is to visit all ''n'' vertices and return to the starting vertex, but the sum of the weights of the tour should be as small as possible. The problem can also be understood as a specific version of the [[travelling salesman problem]], where the salesman has to discover the graph on the go.
For general graphs, the best known algorithms for both undirected and directed graphs is a simple [[greedy algorithm]]:
| |||