algorithm - neighbors - ¿Cuál es el significado de "de distintas cadenas de vértices" en este algoritmo vecino más cercano?

nn k

Question

El siguiente pseudocódigo es del primer capítulo de una versión preliminar en línea de The Algorithm Design Manual (página 7 de este PDF ).

El ejemplo es de un algoritmo defectuoso, pero todavía quiero entenderlo:

[...] Una idea diferente podría ser conectar repetidamente el par más cercano de puntos finales cuya conexión no creará un problema, como la terminación prematura del ciclo. Cada vértice comienza como su propia cadena de vértice único. Después de fusionar todo junto, terminaremos con una sola cadena que contiene todos los puntos en ella. Conectar los dos puntos finales finales nos da un ciclo. En cualquier paso durante la ejecución de esta heurística de par más cercano, tendremos un conjunto de vértices únicos y cadenas desunidas de vértice disponibles para combinar. En pseudocódigo:

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

Tenga en cuenta que sm y tm deben ser s m y t m .

En primer lugar, no entiendo lo que significaría "de distintas cadenas de vértices". En segundo lugar, i se usa como contador en el bucle externo, ¡pero i nunca se usa en ningún lugar! ¿Podría alguien más inteligente que yo, por favor explicar qué está pasando aquí realmente?

Answer 1

1) La descripción indica que cada vértice siempre pertenece a una "cadena de un solo vértice" (es decir, está solo) o pertenece a otra cadena; Un vértice solo puede pertenecer a una cadena. El algoritmo dice que en cada paso seleccionas cada par posible de dos vértices que son cada uno un punto final de la cadena respectiva a la que pertenecen, y que no pertenecen a la misma cadena. A veces serán singletons; a veces uno o ambos ya pertenecerán a una cadena no trivial, por lo que te unirás a dos cadenas.

2) Repite el bucle n veces, de modo que eventualmente selecciona cada vértice; pero sí, el recuento de iteración real no se utiliza para nada. Todo lo que importa es que ejecutas el bucle suficientes veces.

Answer 2

Así es como lo veo, después de la explicación de Ernest Friedman-Hill (respuesta aceptada):

Así que el ejemplo del mismo libro (Figura 1.4). He añadido nombres a los vértices para que quede claro.

Entonces, en el primer paso, todos los vértices son cadenas de un solo vértice, así que conectamos los pares AD, BE y CF, la distancia b / c entre ellos es la más pequeña.

En el segundo paso tenemos 3 cadenas y la distancia entre AD y BE es la misma que entre BE y CF, así que conectamos AD con BE y salimos con dos cadenas: ADEB y CF

En el tercer paso, la única forma de conectarlos es a través de B y C, b / c BC es más corto que BF, AF y AC (recuerde que solo consideramos los puntos finales de las cadenas). Así que ahora tenemos una cadena ADEBCF.

En el último paso conectamos dos puntos finales (A y F) para obtener un ciclo.

Answer 3

Aunque la pregunta ya está respondida, aquí hay una implementación de python para la par heurística más cercana. Comienza con cada punto como una cadena, luego extiende cadenas sucesivamente para construir una cadena larga que contenga todos los puntos. Este algoritmo construye un camino, pero no se desconoce una secuencia de movimientos del brazo del robot para ese punto de inicio del brazo.

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()