Question 1172185: The Greedy Algorithm is an algorithm that would help us to find a Hamiltonian circuit in a weighted graph, but only for complete graphs - a graphs in which every possible edge is drawn between vertices (without any multiple edges). Though this algorithm does not guaranteed the optimal solution but a good solution anyway than having a trial and error.
"The Greedy Algorithm"
1. Choose a vertex to start at, then travel along the connected edge that has the smallest weight. (if two or more edges have the same weight, pick any one.)
2. After arriving at the next vertex, travel along the edge of smallest weight that connects to a vertex not yet visited. Continue this process until you have visited all vertices.
3. Return to the starting vertex.
The greedy algorithm is so called because it choose the “cheapest” option at every chance we get.
Assignment: please show the solution it really help me, thanks:
A tourist is staying in Toronto, Canada, and would like to visit four other Canadian cities by train. The visitor wants to go from one city to the next and return to Toronto while minimizing the total travel distance. The distances between cities, in kilometers, are given in the following table. Represent the distances between the cities using a weighted graph. Use the greedy algorithm to plan a route for the tourist.
Toronto Kingston Niagara Falls Ottawa Windsor
Toronto -- 259 142 423 381
Kingston 259 -- 397 174 623
Niagara Falls 142 397 -- 562 402
Ottawa 423 174 562 -- 787
Windsor 381 623 402 787 --
Answer by ikleyn(52887)   (Show Source):
You can put this solution on YOUR website! .
Having so clearly described algorithm, WHY don't you follow it to solve the problem on your own ?
It requires only to read the instructions attentively and then BLINDLY follow them, making ELEMENTARY steps, ONLY.
Why you so indispensably want to reload YOUR JOB to the tutors' shoulders ?
You will learn NOTHING without making your own steps.
So, been inspired by my post, BOLDLY go forward.
|
|
|
