Quelle est la signification de "à partir de chaînes de sommets distincts" dans cet algorithme du plus proche voisin ?

Question

Le pseudo-code suivant est tiré du premier chapitre d'une version préliminaire en ligne de l'ouvrage Le manuel de conception d'algorithmes (page 7 de ce PDF ).

L'exemple est celui d'un algorithme défectueux, mais j'ai quand même envie de le comprendre :

[...] Une autre idée pourrait consister à connecter de manière répétée la paire d' points d'extrémité dont la connexion ne créera pas de problème, tel qu'une une fin prématurée du cycle. Chaque sommet commence comme sa propre chaîne à sommet unique. Après avoir fusionné le tout, nous nous retrouverons avec une seule chaîne contenant tous les points qui la composent. En reliant les deux derniers points terminaux nous donne un cycle. A n'importe quelle étape de l'exécution de cette heuristique de paire la plus proche, nous aurons un ensemble de sommets simples et de chaînes de sommets disjoints disponibles pour fusionner. En pseudo-code :

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

Veuillez noter que sm y tm devrait être s_{<code>m</code>} y t_{<code>m</code>} .

Tout d'abord, je ne comprends pas ce que signifie "à partir de chaînes de sommets distinctes". Ensuite, i est utilisé comme un compteur dans la boucle externe, mais i n'est jamais utilisé nulle part ! Quelqu'un de plus intelligent que moi pourrait-il m'expliquer ce qui se passe réellement ici ?

Answer 1

Voici comment je vois les choses, après l'explication d'Ernest Friedman-Hill (réponse acceptée) :

Ainsi l'exemple du même livre (figure 1.4). J'ai ajouté des noms aux sommets pour que ce soit plus clair.

Ainsi, à la première étape, tous les sommets sont des chaînes à sommet unique, nous connectons donc les paires A-D, B-E et C-F, car la distance entre elles est la plus petite.

A la deuxième étape, nous avons 3 chaînes et la distance entre A-D et B-E est la même qu'entre B-E et C-F, donc nous connectons disons A-D avec B-E et il nous reste deux chaînes - A-D-E-B et C-F.

À la troisième étape, la seule façon de les relier est de passer par B et C, car B-C est plus court que B-F, A-F et A-C (rappelez-vous que nous ne considérons que les extrémités des chaînes). Nous avons donc maintenant une chaîne A-D-E-B-C-F.

À la dernière étape, nous connectons deux points d'extrémité (A et F) pour obtenir un cycle.

Answer 2

1) La description indique que chaque sommet appartient toujours soit à une "chaîne à sommet unique" (c'est-à-dire qu'il est seul), soit à une autre chaîne ; un sommet ne peut appartenir qu'à une seule chaîne. L'algorithme dit qu'à chaque étape, il faut sélectionner toutes les paires possibles de deux sommets qui sont chacun un point d'extrémité de la chaîne respective à laquelle ils appartiennent, et qui n'appartiennent pas déjà à la même chaîne. Parfois, il s'agira de singletons ; parfois, l'un d'entre eux ou les deux appartiendront déjà à une chaîne non triviale, de sorte que vous joindrez deux chaînes.

2) Vous répétez la boucle n fois, de sorte que vous finissez par sélectionner chaque sommet ; mais oui, le nombre réel d'itérations n'est pas utilisé pour quoi que ce soit. Tout ce qui compte, c'est que vous exécutez la boucle suffisamment de fois.

Answer 3

Bien que la question ait déjà reçu une réponse, voici une implémentation python de l'heuristique de la paire la plus proche. Il commence avec chaque point comme une chaîne, puis étend successivement les chaînes pour construire une longue chaîne contenant tous les points. Cet algorithme construit un chemin mais ce n'est pas une séquence de mouvements du bras du robot dont le point de départ est inconnu.

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