加载中…
个人资料
whutgy
whutgy
  • 博客等级:
  • 博客积分:0
  • 博客访问:3,024
  • 关注人气:0
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

Chapter 14-1: Weighted Graphs

(2009-09-10 19:42:33)
标签:

杂谈

分类: DataStructures&Algorith笔记

(1)
In the last chapter we saw that a graph's edges can have direction. In this chapter we'll explore another edge feature: weight.

当把权值当作边的特性时,一些有趣和复杂的问题也就出现了。什么是带权图的最小生成树?什么是两个顶点间的最短(或造价最低)距离?这些问题在现实世界中有重要的意义。

 

(2)
带权图的最小生成树(Minimum Spanning Tree with Weighted Graphs)
要引入带权图,首先回到最小生成树的问题。在有向图中创建这样一棵树比在无向图中要复杂一点。
(实际上是一个NP完全问题,要找到真正的全局最优,可能需要穷举。往往用一些优化算法,或者用局部最优代替。)

Chapter <wbr>14-1: <wbr>Weighted <wbr>Graphs

An Example: Cable TV in the Jungle
  Suppose we want to install a cable television line that connects six towns in the mythical country of Magnaguena. Five links will connect the six cities, but which five links should they be? The cost of connecting each pair of cities varies, so we must pick the route carefully to minimize the overall cost.

 

  How can we pick a route that minimizes the cost of installing the cable system? The answer is to calculate a minimum spanning tree. It will have five links (one fewer than the number of towns), it will connect all six towns, and it will minimize the total cost of building these links.


  You start by setting up an office in Ajo. (You could start in any town, but Ajo has the best restaurants.) Only two towns are reachable from Ajo: Bordo and Danza (refer to Figure 14.1). You hire two tough, jungle-savvy surveyors and send them out along the dangerous wilderness trails, one to Bordo and one to Danza. Their job is to determine the cost of installing cable along these routes.


  To get a feel for this situation, try to imagine some other route linking Ajo to Danza that would be cheaper than the direct link. If it doesn't go directly to Danza, this other route must go through Bordo and circle back to Danza, possibly via one or more other towns. But you already know the link to Bordo is more expensive, at 6 million dollars,than the link to Danza, at 4. So even if the remaining links in this hypothetical circle route are cheap, as shown in Figure 14.4, it will still be more expensive to get to Danza by going through Bordo. Also, it will be more expensive to get to towns on the circle route, like X, by going through Bordo than by going through Danza.
(这一段论证从某点出发能够直接到其它点的距离中最小的一条一定属于最小生成树的一部分。)

 

  We conclude that the Ajo–Danza route will be part of the minimum spanning tree. This isn't a formal proof (which is beyond the scope of this book), but it does suggest your best bet is to pick the cheapest link. So you build the Ajo–Danza link and install an office in Danza.

Once you've completed the Ajo–Danza link and built your office in Danza, you can send out surveyors from Danza to all the towns reachable from there. These are Bordo, Colina, and Erizo. The surveyors reach their destinations and report back costs of 7, 8, and 12 million dollars, respectively. (Of course you don't send a surveyor to Ajo because you've already surveyed the Ajo–Danza route and installed its cable.)

 

Now you know the costs of four links from towns with offices to towns with no offices:
? Ajo–Bordo, $6 million
? Danza–Bordo, $7 million
? Danza–Colina, $8 million
? Danza–Erizo, $12 million

 

  Why isn't the Ajo–Danza link still on the list? Because you've already installed the cable there; there's no point giving any further consideration to this link. The route on which a cable has just been installed is always removed from the list.

 

  At this point it may not be obvious what to do next. There are many potential links to choose from. What do you imagine is the best strategy now? Here's the rule:
Rule: From the list, always pick the cheapest edge.
(规则:在表单中,总是选择造价最低的边。)

 

  Actually, you already followed this rule when you chose which route to follow from Ajo; the Ajo–Danza edge was the cheapest. Here the cheapest edge is Ajo–Bordo, so you install a cable link from Ajo to Bordo for a cost of 6 million dollars, and build an office in Bordo.

Let's pause for a moment and make a general observation. At a given time in the cable system construction, there are three kinds of towns:
1. Towns that have offices and are linked by cable. (In graph terms they're in the minimum spanning tree.)
2. Towns that aren't linked yet and have no office, but for which you know the cost to link them to at least one town with an office. We can call these "fringe" towns.
3. Towns you don't know anything about.

 

  At this point, Ajo, Danza, and Bordo are connected to the cable system and have offices. You already know the costs from Ajo and Danza to towns in category 2, but you don't know these costs from Bordo. So from Bordo you send out surveyors to Colina and Erizo. They report back costs of 10 to Colina and 7 to Erizo. Here's the new list:
? Bordo–Erizo, $7 million
? Danza–Colina, $8 million
? Bordo–Colina, $10 million
? Danza–Erizo, $12 million

 

  The Danza–Bordo link was on the previous list but is not on this one because, as we noted, there's no point in considering links to towns that are already connected, even by an indirect route.
(注意,Danza-Bordo的连接原来在表单中,现在却没有了,因为没有必要考虑已连接的城市之间的连接问题,即使它们不是直接相连的。)

  From this list we can see that the cheapest route is Bordo–Erizo, at 7 million dollars. You send out the crew to install this cable link, and you build an office in Erizo (refer to Figure 14.3).

 

  From Erizo the surveyors report back costs of 5 to Colina and 7 to Flor. The Danza–Erizo link from the previous list must be removed because Erizo is now a connected town. Your new list is
? Erizo–Colina, $5 million
? Erizo–Flor, $7 million
? Danza–Colina, $8 million
? Bordo–Colina, $10 million


  The cheapest of these links is Erizo–Colina, so you built this link and install an office in Colina.

 

And, Finally, the Colina–Flor Link
  The choices are narrowing. After removing already linked towns, your list now shows only
? Colina–Flor, $6 million
? Erizo–Flor, $7 million
  You install the last link of cable from Colina to Flor, build an office in Flor, and you're done. You know you're done because there's now an office in every town. You've constructed the cable route Ajo–Danza, Ajo–Bordo, Bordo–Erizo, Erizo–Colina, and Colina–Flor, as shown earlier in Figure 14.3. This is the cheapest possible route linking the six towns of Magnaguena.


(3)
优先级队列
  The key activity in carrying out the algorithm, as described in the cable TV example, was maintaining a list of the costs of links between pairs of cities. We decided where to build the next link by selecting the minimum of these costs.
  正如前面例子描述的那样,执行算法的关键行为是保存两城市间建立连接的造价表。通过选择造价最低的项,就可以决定下一条连接建在何处。

 

  A list in which we repeatedly select the minimum value suggests a priority queue as an appropriate data structure, and in fact this turns out to be an efficient way to handle the minimum spanning tree problem. Instead of a list or array, we use a priority queue. In a serious program this priority queue might be based on a heap, as described in Chapter 12, "Heaps." This would speed up operations on large priority queues. However, in our demonstration program we'll use a priority queue based on a simple array.
  建议用优先级队列来实现这个用于反复选择最小造价的表,而不用链表或数组。这是解决最小生成树的有效方式。在正式的程序中,优先级队列可能基于堆来实现,正如第12章“堆”所描述的。这会加快在较大的优先级队列中的操作。然而,在实际程序中,将用数组实现优先级队列。

 

(4)
算法要点
下面用图的术语重申一下算法:

  Start with a vertex, put it in the tree. Then repeatedly do the following:
1. Find all the edges from the newest vertex to other vertices that aren't in the tree. Put these edges in the priority queue.
2. Pick the edge with the lowest weight, and add this edge and its destination vertex to the tree.
  Do these steps until all the vertices are in the tree. At that point, you're done.
  In step 1, "newest" means most recently installed in the tree. The edges for this step can be found in the adjacency matrix. After step 1, the list will contain all the edges from vertices in the tree to vertices on the fringe.


从一个顶点开始,把它放到树的集合中。然后重复做下面的事情:
1.找到从最新的顶点到其他顶点的所有边,这些顶点不能在树的集合中。把这些边加入优先级队列。
2.找出权值最小的边,把它和它所到达的顶点放入树的集合中。
重复这些步骤,直到所有顶点都在树的集合中。这时,工作完成。

  在步骤1,“最新的”意味着最近放入树中的。此步骤的边可以在邻接矩阵中找到。步骤1完成后,表中包含了所有的边,这些边都是从树中顶点到它们的不在树脂的邻接点(边缘点)的连接。


(5)
无用边(Extraneous Edges)

  In maintaining the list of links, we went to some trouble to remove links that led to a town that had recently become connected. If we didn't do this, we would have ended up installing unnecessary cable links.
在表剩余条目中,想要把某些连接删除比较困难,它们都是从当前城市到已经拥有办事处的城市的连接。但是如果不做这样的工作,就可能会导致安装不必要的有线电缆。

 

  In a programming algorithm we must likewise make sure that we don't have any edges in the priority queue that lead to vertices that are already in the tree. We could go through the queue looking for and removing any such edges each time we added a new vertex to the tree. As it turns out, it is easier to keep only one edge from the tree to a given fringe vertex in the priority queue at any given time. That is, the queue should contain only one edge to each category 2 vertex.
在程序的算法中,也要确保优先级队列中不能有连接已在树中的顶点的边。每次向树中添加顶点后,都要遍历优先级队列查找并删除这样的边。这样做了以后,要使优先级队列中在任意时刻只保持一条从树中顶点到某边缘点的边就变得容易了。也就是说,优先级队列中应该只包含一条到达某个第二类顶点的边。

 

  You'll see that this is what happens in the GraphW Workshop applet. There are fewer edges in the priority queue than you might expect; just one entry for each category 2 vertex. Step through the minimum spanning tree for Figure 14.1 and verify that this is what happens. Table 14.1 shows how edges with duplicate destinations have been removed from the priority queue.

Chapter <wbr>14-1: <wbr>Weighted <wbr>Graphs

  The third column is what you see in the priority queue when you run the GraphW applet. Any edge with the same destination vertex as another edge, and which has a greater weight, has been removed.

 

  The fourth column shows the edges that have been removed, and, in parentheses, the edge with the smaller weight that superseded it and remains in the queue. Remember that as you go from step to step the last entry on the list is always removed because this edge is added to the tree.


(6)
在优先级队列中寻找目的地重复的边
(Looking for Duplicates in the Priority Queue)

  How do we make sure there is only one edge per category 2 vertex? Each time we add an edge to the queue, we make sure there's no other edge going to the same destination. If there is, we keep only the one with the smallest weight.
如何保证以每个第二类顶点为目的地的边只有一条?每次向树中增加边的时候,一定要确保没有其他边也到达同样的顶点。如果有,只保留最小权值的边。

 

  This necessitates looking through the priority queue item by item, to see if there's such a duplicate edge. Priority queues are not designed for random access, so this is not an efficient activity. However, violating the spirit of the priority queue is necessary in this situation.
  这使得在优先级队列中逐项查找成为必要的一步操作。查找的目的是看是否有这样的重复边,优先级队列设计初衷本不为随机访问的,所以这不是一个有效的方法。然而,在这种情况下,必须违反一下优先级队列的设计思想。


(7)
java代码

public void mstw()
  算法在while循环中执行,循环结束条件是所有顶点都已在树中。循环中完成下面的操作:
1.当前顶点放在树中。
2.连接这个顶点的边放到优先级队列中(如果合适)。
3.从优先级队列中删除权值最小的边。这条边的目的顶点变成当前顶点。

再看看这些步骤的细节。在步骤1中,通过标记currentVert所指顶点的isInTree字段来表示该顶点放入树中。


  在步骤2中,连接这个顶点的边插入优先级队列。通过在邻接矩阵中扫描行号是currentVert的行寻找需要的边。只要下面任意一个条件为真,这条边就不能放入队列中:
1.源点和终点相同。
2.终点在树中。
3.源点和终点之间没有边(邻接矩阵中对应的值等于无限大)。

  如果没有一个条件为真,调用putInPQ()方法把这条边放入队列中。实际上,正如下面要看到的,这个例程并不总把边放到队列中。
(Actually, this routine doesn't always put the edge in the queue either, as we'll see in a moment.)

在步骤3中,将最小权值的边从优先级队列中删除。把这条边和该边的终点加入树,并显示源点(currentVent)和终点。


  At the end of mstw(), the vertices are removed from the tree by resetting their isInTree variables. That isn't strictly necessary in this program, because only one tree is created from the data. However, it's good housekeeping to restore the data to its original form when you finish with it.
  (在mstw()方法最后,所有顶点的isInTree变量被重置,即从树中删除。在该程序中这样做,是因为根据这些数据只能创建一棵树。然而,在完成一项工作后,最好把数据恢复到原始的形态。)

 

(8)
  As we noted, the priority queue should contain only one edge with a given destination vertex. The putInPQ() method makes sure this is true. It calls the find() method of the PriorityQ class, which has been doctored to find the edge with a specified destination vertex. If there is no such vertex, and find() therefore returns –1, then putInPQ() simply inserts the edge into the priority queue. However, if such an edge does exist, putInPQ() checks to see whether the existing edge or the new proposed edge has the lower weight. If it's the old edge, no change is necessary. If the new one has a lower weight, the old edge is removed from the queue and the new one is installed.

  正如前面所强调的,在优先级队列中应该只含有一条到达某个特定目标顶点的边。putInPQ()方法保证了这一点。它调用PriorityQ类的find()方法,这个方法经过修正,可以寻找到达指定点的边。如果不存在到达指定点的边,find()方法返回-1;这时putInPQ()方法只要把新边插入优先级队列中即可。然而,如果有到达指定点的老边存在,putinPQ()方法就要检查老边是否比新边有更小的权值。如果老边的权值小,就不需要作什么变化。如果新边有更小的权值,就要把老边从队列中删除,把新边放进去。

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有