Подтвердить что ты не робот

В чем смысл "из разных вершинных цепей" в этом алгоритме ближайшего соседа?

Следующий псевдокод из первой главы онлайновой версии предварительного просмотра Руководства по разработке алгоритмов (стр. 7 из этого PDF).

Пример неправильного алгоритма, но я все еще очень хочу его понять:

[...] Двумя идеями может быть многократное соединение ближайшей пары конечные точки, соединение которых не создает проблемы, например преждевременное прекращение цикла. Каждая вершина начинается как собственная единственная цепочка вершин. После слияния всего вместе мы закончим с одной цепью, содержащей все точки в ней. Подключение конечные конечные точки дают нам цикл. На любом этапе выполнения этой эвристики ближайшей пары мы будем иметь набор одиночных вершин и вершинно-дизъюнктивные цепочки, доступные для слияния. В псевдокоде:

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

Обратите внимание, что sm и tm должны быть s m и t m.

Прежде всего, я не понимаю, что означало бы "из разных вершинных цепей". Во-вторых, i используется как счетчик во внешнем цикле, но i сам по себе никогда не используется нигде! Может ли кто-нибудь умнее меня объяснить, что здесь происходит?

4b9b3361

ОТВЕТЫ

Ответ 1

1) В описании указывается, что каждая вершина всегда принадлежит либо "одновершинной цепочке" (т.е. одному), либо принадлежит одной другой цепочке; вершина может принадлежать только одной цепочке. Алгоритм говорит, что на каждом шаге вы выбираете каждую возможную пару из двух вершин, каждая из которых является конечной точкой соответствующей цепи, к которой они принадлежат, и уже не принадлежат к одной и той же цепочке. Иногда они будут одиночными; иногда один или оба будут принадлежать к нетривиальной цепочке, поэтому вы присоедините две цепи.

2) Повторяйте цикл n раз, чтобы в конечном итоге выбрать каждую вершину; но да, фактическое количество итераций ни для чего не используется. Все, что имеет значение, заключается в том, что вы запускаете цикл достаточно времени.

Ответ 2

Вот как я вижу это после объяснения Эрнеста Фридмана-Хилла (принятый ответ):

Итак, пример из той же книги (рис. 1.4). Я добавил имена в вершины, чтобы они поняли Figure 1.4

Таким образом, на первом шаге все вершины являются одиночными вершинами, поэтому мы соединяем пары A-D, B-E и C-F, расстояние b/c между ними является наименьшим.

На втором шаге мы имеем 3 цепи, а расстояние между A-D и B-E такое же, как между B-E и C-F, поэтому мы соединяем, скажем, A-D с B-E, и мы оставили две цепи: A-D-E-B и C-F

На третьем шаге есть единственный способ связать их через B и C, b/c B-C короче, чем B-F, A-F и A-C (помните, что мы рассматриваем только конечные точки цепей). Итак, у нас есть одна цепочка теперь A-D-E-B-C-F.

На последнем шаге мы соединяем две конечные точки (A и F), чтобы получить цикл.

Ответ 3

Хотя на вопрос уже дан ответ, здесь реализована реализация python для ближайшей парной эвристики. Он начинается с каждой точки как цепочки, а затем последовательно расширяя цепи, чтобы построить одну длинную цепочку, содержащую все точки. Этот алгоритм действительно строит путь, но пока неизвестна последовательность движений рук робота для этой начальной точки руки.

import matplotlib.pyplot as plot
import math
import random


def draw_arrow(axis, p1, p2, rad):
    """draw an arrow connecting point 1 to point 2"""
    axis.annotate("",
              xy=p2,
              xytext=p1,
              arrowprops=dict(arrowstyle="-", linewidth=0.8, connectionstyle="arc3,rad=" + str(rad)),)


def closest_pair(points):
    distance = lambda c1p, c2p:  math.hypot(c1p[0] - c2p[0], c1p[1] - c2p[1])
    chains = [[points[i]] for i in range(len(points))]
    edges = []
    for i in range(len(points)-1):
        dmin = float("inf")  # infinitely big distance
        # test each chain against each other chain
        for chain1 in chains:
            for chain2 in [item for item in chains if item is not chain1]:
                # test each chain1 endpoint against each of chain2 endpoints
                for c1ind in [0, len(chain1) - 1]:
                    for c2ind in [0, len(chain2) - 1]:
                        dist = distance(chain1[c1ind], chain2[c2ind])
                        if dist < dmin:
                            dmin = dist
                            # remember endpoints as closest pair
                            chain2link1, chain2link2 = chain1, chain2
                            point1, point2 = chain1[c1ind], chain2[c2ind]
        # connect two closest points
        edges.append((point1, point2))
        chains.remove(chain2link1)
        chains.remove(chain2link2)
        if len(chain2link1) > 1:
            chain2link1.remove(point1)
        if len(chain2link2) > 1:
            chain2link2.remove(point2)
        linkedchain = chain2link1
        linkedchain.extend(chain2link2)
        chains.append(linkedchain)
    # connect first endpoint to the last one
    edges.append((chains[0][0], chains[0][len(chains[0])-1]))
    return edges


data = [(0.3, 0.2), (0.3, 0.4), (0.501, 0.4), (0.501, 0.2), (0.702, 0.4), (0.702, 0.2)]
# random.seed()
# data = [(random.uniform(0.01, 0.99), 0.2) for i in range(60)]
edges = closest_pair(data)
# draw path
figure = plot.figure()
axis = figure.add_subplot(111)
plot.scatter([i[0] for i in data], [i[1] for i in data])
nedges = len(edges)
for i in range(nedges - 1):
    draw_arrow(axis, edges[i][0], edges[i][1], 0)
# draw last - curved - edge
draw_arrow(axis, edges[nedges-1][0], edges[nedges-1][1], 0.3)
plot.show()