algoritmos euristicos

Algoritmos heurísticos
Concepto de heurística.
Se denomina heurística al arte de inventar. En programación se dice que un algoritmo es
heurístico cuando la solución no se determina en formadirecta, sino mediante ensayos,
pruebas y reensayos.
El método consiste en generar candidatos de soluciones posibles de acuerdo a un patrón
dado; luego los candidatos son sometidos a pruebas de acuerdo aun criterio que
caracteriza a la solución. Si un candidato no es aceptado, se genera otro; y los pasos dados
con el candidato anterior no se consideran. Es decir, existe inherentemente una vueltaatrás, para comenzar a generar un nuevo candidato; por esta razón, este tipo de algoritmo
también se denomina "con vuelta atrás" (backtracking en inglés).
Estudiemos el siguiente problema,propuesto por Wirth y desarrollado por Dijkstra:

Aplicación. Generación de secuencias.
Se desea generar secuencias en orden 'alfabético' de tres caracteres '0','1' y '2', hasta

obtener una secuenciade largo 100. Las secuencias generadas no deben contener
subsecuencias adyacentes iguales.
Una lista de las primeras secuencias que cumplen es:
0

01

010

0102
01020

010201

01020100102012
........

La lista indica lo que se entiende por ordenamiento alfabético, en este caso.

Observando las soluciones, cada una de ellas es una extensión (a lo menos en un dígito) de laanterior.

Denominaremos buena una secuencia que cumple la condición de no contener
subsecuencias adyacentes iguales.
Si una secuencia de ensayo es buena, se la debe imprimir y 'extender' con un '0'para
generar la candidata siguiente. Si ésta no se buena, se 'incrementa' para obtener la
próxima.

Se entiende por incrementar la operación de remover los dígitos finales iguales a '2' eincrementar en uno el último dígito resultante. Las operaciones de extender e
incrementar aseguran la generación alfabética. Además observamos que una nueva

secuencia se obtiene de la anterior, según se...