算法设计与分析W3-续W2+分治

VIP免费

2025-01-13 0 0 1.83MB 118 页 5.9玖币

侵权投诉

Last Section

An Example

•Task

•Problem analyzing

•Statement of the problem

•Development of a Model

•Design of the algorithm

•Correctness of the algorithm

•Implementation

•Analysis and complexity of the algorithm

Statement of the problem

已知网络中任意两点间建立链路的花费，

需建立一个最小费用的通讯网络,

其中任意节点间可以相互通讯。

Model

Let

G=(V,E) be a connected, undirected graph;

w(u,v) is the cost for connecting u,v

∈

find an acyclic subset T E and connects

all vertices in V, such that

is minimized









Tvu

vuwTw

),(

),()(

•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?

Question 4&5

•Step 1 requires a sub-algorithm to

determine if a network is connected, and

•step 2 requires a sub-algorithm to decide if

a network has a cycle.

•These two steps can make the algorithm

ineffective in that these sub-algorithms

might be time-consuming.

•Algorithm B To find a minimum-weight

spanning tree T in a weighted, connected network G

with N vertices and M edges.

Step 0. [Initialize] Label all vertices “unchosen”;

set T ← a network with N vertices and

no edges; choose an arbitrary vertex

and label it “chosen”.

Step 1. [Iterate] While there is an unchosen

vertex do step 2 od; STOP.

Step 2. [Pick a lightest edge]

Let (U, V) be a lightest edge between any

chosen vertex U and any unchosen vertex V;

label V as “chosen”; and set T ← T + (U, V).

Now

•Algorithm B is self-contained;

•It is assumed to be more efficient than

Algorithm A.

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?

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

LastSectionAnExample•Task•Problemanalyzing•Statementoftheproblem•DevelopmentofaModel•Designofthealgorithm•Correctnessofthealgorithm•Implementation•AnalysisandcomplexityofthealgorithmStatementoftheproblem已知网络中任意两点间建立链路的花费，需建立一个最小费用的通讯网络,其中任意节点间可以相互通讯。ModelLetG=(V,E)beaconnected,undirectedgraph;w(u,v)...

展开>> 收起<<

算法设计与分析W3-续W2+分治.pdf

共118页,预览24页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

算法设计与分析W3-续W2+分治

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: