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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Algoritmo 6.4. Procedimiento nextvalue (Horowitz y Sahni, 1978)

Este procedimiento primero inicializa la matriz adyacente GRAPH (1: n, 1:n), a continuación estable-
ce X(2:n) 0, X(1) 1 y ejecuta la llamada a HAMILTONIAN(2). El problema del agente viajero es
un ciclo hamiltoniano con la diferencia de que cada arista tiene un costo diferente. El algoritmo 6.5,
programado en C, es una combinación del programa del agente viajero por medio de programación
dinámica y el código de las n reinas que resuelve el ciclo hamiltoniano:

Algoritmo 6.5. Ciclo hamiltoniano

141