The Wirehouse Lumber Company will soon begin logging eight groves of trees in the same general area. Therefore, it must develop a system of dirt roads that makes each grove accessible from every other grove. The distance(in miles) between every pair of groves is as follows:
Grove | Distance between Pairs of Groves | |||||||
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
1 | - | 1.3 | 2.1 | 0.9 | 0.7 | 1.8 | 2.0 | 1.5 |
2 | 1.3 | - | 0.9 | 1.8 | 1.2 | 2.6 | 2.3 | 1.1 |
3 | 2.1 | 0.9 | - | 2.6 | 1.7 | 2.5 | 1.9 | 1.0 |
4 | 0.9 | 1.8 | 2.6 | - | 0.7 | 1.6 | 1.5 | 0.9 |
5 | 0.7 | 1.2 | 1.7 | 0.7 | - | 0.9 | 1.1 | 0.8 |
6 | 1.8 | 2.6 | 2.5 | 1.6 | 0.9 | - | 0.6 | 1.0 |
7 | 2.0 | 2.3 | 1.9 | 1.5 | 1.1 | 0.6 | - | 0.5 |
8 | 1.5 | 1.1 | 1.0 | 0.9 | 0.8 | 1.0 | 0.5 | - |
Management now wants to determine between which pairs of groves the roads should be constructed to connect all groves with a minimum total length of road.
a. Describe how this problem fits the network description of a minimum spanning tree problem.
b. Use the suitable algorithm to solve this problem.
answer:
- Choose of the first link: Select the cheapest potential link.
- Choose of the next link: Select the cheapest potential link between a node that already is touched by a link and a node that does not yet have such a link.
- Repeat step 2 over and over until every node is touched by a link (perhaps more than one). At that point, an optimal solution (a minimum spanning tree) has been obtained.
b. Use the suitable algorithm to solve this problem.
answer :
n = 8
n -1 = 7
total distance = 0.5 + 0.6 + 0.8 + 0.7+ 0.7 + 0.9 + 1.0
= 5.2 miles
References:
Titanium Athletics: The history and beginnings of the
ReplyDeleteThe era has long seen titanium oakley titanium sunglasses athletics at our titanium hair clipper as being the first to do so during the 20th century. titanium grades The microtouch titanium trim as seen on tv T-shirt at the T-shirt at T-shirt. titanium white fennec