什么是＆QUOT的意义;从不同的顶点链＆QUOT;在这个近邻算法？ [英] What is the meaning of "from distinct vertex chains" in this nearest neighbor algorithm?

问题描述

下面的伪code是的的的算法设计手册的（第7页从的这个PDF ）。

这个例子是一个有缺陷的算法，但我还是真的想了解它：

  

[...] A二FF erent想法可能是反复连接最接近的一对   终端的连接不会产生问题，如   premature终止循环。每个顶点开始作为其自身   单个顶点链。合并一切融合在一起之后，我们最终会   用含有所有点在它的单链。连接   网络最终两个端点给了我们一个周期。在执行过程中的任何步骤   这个最接近，对启发，我们将有一组单顶点   和可用的顶点相交链合并。在伪code：

  ClosestPair（P）
    设n是点的数目在设置P.
    对于i = 1到n  -  1做
        D =∞
        对于每对端点（S，T）从不同顶点链
            如果测距（S，T）≤ð然后SM = S，TM =吨，以及d = DIST（S，T）
        连接（SM，TM）由边缘
    由边缘连接的两个端点
 

请注意， SM 和 TM 应取值 <分> M 和 T <分> M 。

首先，我不，从不同的顶点链明白意味着什么。其次，我用作外循环的计数器，但我本身实际上从未在任何地方使用！可能有人比我聪明，请解释一下到底发生了什么在这里？

解决方案

1）的说明指出，每个顶点总是属于任何一个单顶点链（即，它是单独的），或者它属于另外一个链条;一个顶点只能属于一个链。该算法表示在每一步选择每个可能的对的两个顶点这是它们所属的相应链的每个端点，并且不已经属于同一连锁。有时，他们会单身人士;有时一个或两个都已经属于非平凡链，所以你会加入两个链。

2）你重复循环的 N 的时间，让你最终选择每一个顶点;但是，实际的迭代次数不用于任何东西。所有的事情是，你运行循环足够的时间。

The following pseudo-code is from the first chapter of an online preview version of The Algorithm Design Manual (page 7 from this PDF).

The example is of a flawed algorithm, but I still really want to understand it:

[...] A different idea might be to repeatedly connect the closest pair of endpoints whose connection will not create a problem, such as premature termination of the cycle. Each vertex begins as its own single vertex chain. After merging everything together, we will end up with a single chain containing all the points in it. Connecting the final two endpoints gives us a cycle. At any step during the execution of this closest-pair heuristic, we will have a set of single vertices and vertex-disjoint chains available to merge. In pseudocode:

ClosestPair(P)
    Let n be the number of points in set P.
    For i = 1  to n − 1 do
        d = ∞
        For each pair of endpoints (s, t) from distinct vertex chains
            if dist(s, t) ≤ d then sm = s, tm = t, and d = dist(s, t)
        Connect (sm, tm) by an edge
    Connect the two endpoints by an edge

Please note that sm and tm should be sm and tm.

First of all, I don't understand what "from distinct vertex chains" would mean. Second, i is used as a counter in the outer loop, but i itself is never actually used anywhere! Could someone smarter than me please explain what's really going on here?

解决方案

1) The description states that every vertex always belongs either to a "single-vertex chain" (i.e., it's alone) or it belongs to one other chain; a vertex can only belong to one chain. The algorithm says at each step you select every possible pair of two vertices which are each an endpoint of the respective chain they belong to, and don't already belong to the same chain. Sometimes they'll be singletons; sometimes one or both will already belong to a non-trivial chain, so you'll join two chains.

2) You repeat the loop n times, so that you eventually select every vertex; but yes, the actual iteration count isn't used for anything. All that matters is that you run the loop enough times.

这篇关于什么是＆QUOT的意义;从不同的顶点链＆QUOT;在这个近邻算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！