FTP,ftp:/219.224.171.203 Download Lecture Notes: User name: download Password: student Upload Home Works: User name: upload Password: student,Complete Development of An Algorithm,A Complete Example,Example,The task: Decision of whether to establish a computer network at some different sites; Factors: Computing resources available at each site; Anticipate cite usage levels; Peak demands on the system; Possible system degradation of the major facility; The cost of the proposed network.,Example,The task: Decision of whether to establish a computer network at some different sites; Factors: Computing resources available at each site; Anticipate cite usage levels; Peak demands on the system; Possible system degradation of the major facility; The cost of the proposed network.,The Cost of the Proposed Network,This cost includes: Equipment purchases ; Establishment of communication links ; Systems maintenance; The costs of running a job of a given type at a given site.,Analyze the Problem,Leased line costs: Geographical distance between the sites; The desired transmission rate; The desired transmission capacity on a line. After discussion, have Cij between sites i and j. -a symmetric cost matrix,Complete Development of an Algo.,1 Statement of the problem 2 Development of a Model 3 Design of the algorithm 4 Correctness of the algorithm 5 Implementation 6 Analysis and complexity of the algorithm 7 Program testing 8 Documentation,1. Statement of the problem,To establish a minimum cost communication network, in which any site can communicate with each other, while the cost of building a link between any two cites are given.,1. Statement of the problem,已知网络中任意两点间建立链路的花费， 需建立一个最小费用的通讯网络, 其中任意节点间可以相互通讯。,Complete Development of an Algo.,1 Statement of the problem 2 Development of a Model 3 Design of the algorithm 4 Correctness of the algorithm 5 Implementation 6 Analysis and complexity of the algorithm 7 Program testing 8 Documentation,Modeling,What constitutes a solution to the problem? Must decide which specific links should be established and which ones should not, that is: for every site pair i and j, whether or not establish a link at cost Cij . A solution will consist of a modified matrix Cof the original cost matrix C in which the (i, j) and (j, i) entries equal if we do not establish the link; the entries equal Cij if we do.,Modeling,Also, since every site is supposed to be able to communicate with every other site in the final network, each row and each column of Cwill have at lease one finite entry. Is this a correct model? Will any modified matrix satisfying this condition on the rows and columns be a solution?,Look at white board Pls.,More Constraints,What this illustrates is that a network corresponding to a solution to the problem will: Must be connected Must not contain a cycle of communication links. If a solution were to contain a cycle, then a cheaper solution could be found by removing the most costly link in the cycle. Therefore, a solution to the problem will consist of a cheapest sub-network which is connected, contains no cycles, and contains every vertex. The solution is a spanning tree!,Mathematically,Our original problem can now be stated mathematically as follows: Given a weighted, connected network G, find a minimum-cost (or weight) spanning tree of G. -MCST, MWST, MST,Model,Let G=(V,E) be a connected, undirected graph; w(u,v) is the cost for connecting u,vV; find an acyclic subset T E and connects all vertices in V, such that is minimized,Complete Development of an Algo.,1 Statement of the problem 2 Development of a Model 3 Design of the algorithm 4 Correctness of the algorithm 5 Implementation 6 Analysis and complexity of the algorithm 7 Program testing 8 Documentation,Designing an Algorithm,Perhaps the most natural thing to do is to try a greedy algorithm select the cheapest edge first, then the next cheapest edge, and so forth. But in selecting edges we must keep in mind our three requirements: (1) the final subnetwork must contain all vertices and must be connected; (2) the final network must not contain any cycles; (3) the final network must have the minimum possible weight.,Algorithm A To find a minimum-weight spanning tree T in a weighted, connected network G with N vertices and M edges. Step 0. Initialize Set T a network consisting of N vertices and no edges; set H G. Step 1. Iterate While T is not a connected network do through step 3 od; STOP. Step 2. Pick a lightest edge Let (U,V) be a lightest (cheapest) edge in H; if T + (U,V) has no cycles then add (U,V) to T set T T + (U,V) fi. Step 3. Delete (U, V) from H Set H H (U, V).,Does it work?,There are several questions we should ask about this algorithm; 1. Does it always STOP? 2. When it STOPs, is T always a spanning tree of G? 3. Is T guaranteed to be a minimum-weight spanning tree? 4. Is it self-contained (or does it contain hidden, or implicit, sub-algorithms)? 5. Is it efficient?,Qu