Что означает «из различных цепочек вершин» в этом алгоритме ближайшего соседа? - PullRequest
Новая
       38

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

30 голосов
/ 27 августа 2011

Следующий псевдокод взят из первой главы онлайн-версии предварительного просмотра Руководство по разработке алгоритма (стр. 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 должны быть sm и tm.

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

Ответы [ 3 ]

26 голосов
/ 16 декабря 2012

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

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

Итак, на первом шаге все вершины являются цепочками из одной вершины, поэтому мы соединяем пары AD, BE и CF, расстояние между ними b / c равнонаименьший.

На втором шаге у нас есть 3 цепи и расстояние между AD и BE такое же, как между BE и CF, поэтому мы соединяем, скажем, AD с BE, и мы оставляем две цепи - ADEB и CF

На третьем шаге есть единственный способ соединить их через B и C, b / c BC короче, чем BF, AF и AC (помните, что мы рассматриваем только конечные точки цепей).Итак, теперь у нас есть одна цепочка ADEBCF.

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

18 голосов
/ 27 августа 2011

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

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

3 голосов
/ 20 апреля 2015

Хотя на вопрос уже дан ответ, здесь приведена реализация 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()
...