Greedy algorithms work on the concept that a locally optimal choice will result

Question

Greedy algorithms work on the concept that a locally optimal choice will result in a globally optimal choice in solving a problem. The traveling salesman problem can be represented as a set V, of vertices and a set L, of links, (vi, vj) each with a weight/distance wi,j. The object is to find a set of links with minimum weight, such that each vertex (except the start vertex) is visited exactly once.

A). Sketch out a greedy algorithm to find a solution to the traveling salesman problem that visits each vertex. Do not worry about finding an optimal solution. Your algorithm should start at some vertex, k, in the set of vertices and return to that vertex. Assume the set of vertices are connected enough to produce a result. The output should be the list of links, (vi, vj), that provides the solution. The vertex and link information is contained in an nxn matrix of weights. A weight is infinity if there is no link from vi to vj.

B).Does your algorithm produce an optimal answer to the traveling salesman problem? (justify your answer)

C). ) Does your algorithm work with asymmetric weights (i.e., wi,j ? wj,i)?

Explanation / Answer

Greedy algorithms:
(A) Do the right thing. Locally.
(B) Make decisions incrementally in small steps no backtracking.
(C) Decision at each step based on improving local or current state in myopic fashion. ...
without considering the global situation.
(D) myopia: lack of understanding or foresight.
(E) Decisions often based on some fixed and simple priority rules

A)Traveling Salesman Problem. The traveling salesman problem (TSP) is one of the most
famous combinatorial optimization problems. Given a graph, the goal is to find a Hamiltonian
cycle (also called a tour ) of maximum or minimum weight (Max-TSP or Min-TSP).
An instance of Max-TSP is a complete graph G = (V, E) with edge weights w : E ? Q+.
The goal is to find a Hamiltonian cycle of maximum weight. The weight of a Hamiltonian
cycle (or, more general, of any set of edges) is the sum of the weights of its edges. If G is
undirected, we have Max-STSP (symmetric TSP). If G is directed, we obtain Max-ATSP
(asymmetric TSP). An instance of Min-TSP is also a complete graph G with edge weights
w that fulfil the triangle inequality: w(u, v) ? w(u, x) +w(x, v) for all u, v, x ? V . The goal
is to find a tour of minimum weight. We have Min-STSP if G is undirected and Min-ATSP
if G is directed. In this paper, we only consider the latter. If we restrict the instances to
fulfil the ?-triangle inequality (w(u, v) ? ?

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.