《算法分析与设计AlgoD&ALectureNotesW2章节》由会员分享，可在线阅读，更多相关《算法分析与设计AlgoD&ALectureNotesW2章节（68页珍藏版）》请在金锄头文库上搜索。
1、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
2、: 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: Computi
3、ng 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 ; System
4、s 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 m
5、atrix,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 co
6、mmunication 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 Mode
7、l 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
8、 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 suppose
9、d 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
10、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
11、 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 weig
12、ht) 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
13、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,
14、 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-w
15、eight 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
16、 (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
