algoritmos exhaustivos Algoritmos
Páginas: 3 (636 palabras)
Publicado: 19 de agosto de 2015
ALGORITMOS EXHAUSTIVOS
CRISTIAN CAMILO OTÁLORA CÁCERES
MANUEL FERNANDO TRIANA
CONTENIDO
•
DEFINICION
•
FORMA GENERAL
•
PROBLEMAS CLASICOS
–
–
–
–
–
•
EL SALTO DEL CABALLO
LAS OCHO REINAS
LAPERMUTACION SIGUIENTE
CAMINOS MINIMOS EN UN GRAFO
EL PROBLEMA DE LA MOCHILA
CONCLUSIONES
DEFINICION
Los algoritmos exhaustivos son aquellos que
analizan todo el espacio de búsqueda paraencontrar una o todas las soluciones y
garantizan que pueden encontrar una
solución óptima.
Se llaman algoritmos de vuelta atrás, porque
en el caso de no encontrar una solución a
una subtarea se retrocede ala subtarea
anterior y se prueba otro camino diferente a
los probados anteriormente.
Estos algoritmos se asemejan al recorrido en
profundidad dentro de un grafo, siendo cada
subtarea un nodo delgrafo.
Los problemas que manejan los
algoritmos exhaustivos, se caracterizan
por:
• Problemas de optimización.
• Existe función factible que permite
averiguar la solución en curso, viola o
no lasrestricciones.
• Existe función para determinar si una
decisión factible es solución al
problema planteado.
Forma
General
El esquema general de solución
presenta los siguientes pasos:
.
• Vuelta atráshace un recorrido en profundidad del
espacio de búsqueda partiendo de la raíz.
• El recorrido en profundidad regresa sobre sus
pasos, retrocede, cada vez que encuentra un
camino que se ha acabado o porel que no puede
continuar.
• En un recorrido en profundidad o en anchura
sobre un espacio de búsqueda se conoce de
antemano el orden en que se van a generar o
recorrer, sus nodos.
ESQUEMA PROBLEMAS CLÁSICOS
El salto del caballo
Se pretende recorrer un tablero de ajedrez mediante un
caballo, de tal manera que iniciando en una posición
determinada, recorra todas las posiciones del tablero conlos
movimientos o saltos del caballo en el juego de ajedrez
Las ocho reinas
Sobre un tablero de ajedrez hay que colocar 8 reinas de forma que
ninguna de ellas se amenace. Se debe tener en cuenta...
CRISTIAN CAMILO OTÁLORA CÁCERES
MANUEL FERNANDO TRIANA
CONTENIDO
•
DEFINICION
•
FORMA GENERAL
•
PROBLEMAS CLASICOS
–
–
–
–
–
•
EL SALTO DEL CABALLO
LAS OCHO REINAS
LAPERMUTACION SIGUIENTE
CAMINOS MINIMOS EN UN GRAFO
EL PROBLEMA DE LA MOCHILA
CONCLUSIONES
DEFINICION
Los algoritmos exhaustivos son aquellos que
analizan todo el espacio de búsqueda paraencontrar una o todas las soluciones y
garantizan que pueden encontrar una
solución óptima.
Se llaman algoritmos de vuelta atrás, porque
en el caso de no encontrar una solución a
una subtarea se retrocede ala subtarea
anterior y se prueba otro camino diferente a
los probados anteriormente.
Estos algoritmos se asemejan al recorrido en
profundidad dentro de un grafo, siendo cada
subtarea un nodo delgrafo.
Los problemas que manejan los
algoritmos exhaustivos, se caracterizan
por:
• Problemas de optimización.
• Existe función factible que permite
averiguar la solución en curso, viola o
no lasrestricciones.
• Existe función para determinar si una
decisión factible es solución al
problema planteado.
Forma
General
El esquema general de solución
presenta los siguientes pasos:
.
• Vuelta atráshace un recorrido en profundidad del
espacio de búsqueda partiendo de la raíz.
• El recorrido en profundidad regresa sobre sus
pasos, retrocede, cada vez que encuentra un
camino que se ha acabado o porel que no puede
continuar.
• En un recorrido en profundidad o en anchura
sobre un espacio de búsqueda se conoce de
antemano el orden en que se van a generar o
recorrer, sus nodos.
ESQUEMA PROBLEMAS CLÁSICOS
El salto del caballo
Se pretende recorrer un tablero de ajedrez mediante un
caballo, de tal manera que iniciando en una posición
determinada, recorra todas las posiciones del tablero conlos
movimientos o saltos del caballo en el juego de ajedrez
Las ocho reinas
Sobre un tablero de ajedrez hay que colocar 8 reinas de forma que
ninguna de ellas se amenace. Se debe tener en cuenta...
Leer documento completo
Regístrate para leer el documento completo.