Page 146 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

El vector solución por backtraking (x , x , x ,..., x ) se define de tal forma que x representa el i-ésimo
1 2 3 n i
vértice visitado del ciclo propuesto. Ahora, todo lo que se tiene que hacer es determinar cómo calcu-
lar el conjunto posible de vértices para x si x ,..., x han sido ya escogidos. Si k = 1, entonces X (1)
k 1 k-1
puede ser cualquiera de los n vértices. Para evitar la impresión del mismo ciclo n veces se requiere
que X (1) = 1. Si 1 < k < n, entonces X(k) puede ser cualquier vértice v, el cual es distinto de X (1), X
(2),..., X(k-1) y v es conectado por una arista a X(k-1). X(n) puede ser solo un vértice restante y debe
ser conectado a ambos X(n-1) y X (1). El pseudocódigo se muestra en el algoritmo 6.3:

Algoritmo 6.3. Pseudocódigo (Horowitz y Sahni, 1978)

Usando el procedimiento nextvalue, se puede particularizar el esquema recursivo de backtracking
para encontrar todos los ciclos hamiltonianos (algoritmo 6.4).

140