Mierda
Páginas: 4 (873 palabras)
Publicado: 30 de diciembre de 2012
Vuelta Atrás
Miguel Gómez Jiménez Francisco Navas Sánchez
LA VUELTA ATRÁS
Del inglés “Backtracking” , la metodología de Vuelta Atrás tiene como objetivo la consecución de la solución a unproblema realizando el producto cartesiano de posibles soluciones al fin de hallar todas las posibilidades combinatorias y, de éstas, discernir cuál de ellas satisface los requisitos para ser verdaderasolución.
EL PROCEDIMIENTO DE VUELTA ATRÁS
El procedimiento que siguen estos algoritmos es tremendamente sencillo: En primer lugar define una codificación ilustrativa de la solución que garanticeincluir todas las combinaciones de posibles soluciones. Tras esto, rastrea una a una esas posibilidades chequeando si es o no solución final del problema.
COSTE COMPUTACIONAL
Debido a que el únicocomponente realmente utilizado en un algoritmo de vuelta atrás es el codificador de soluciones que es actualizado constantemente, el coste computacional genérico de estos algoritmos será exponencialcon base igual a las posibilidades de solución por elemento de la tupla solución elevado a un exponente igual al número de elementos de la tupla solución. Por ejemplo, en una tupla de cuatro elementoscodificada en binario natural tendremos 24 posibilidades ya que existen dos posibilidades por elementos de la tupla (0 y 1) y existen cuatro elementos en la tupla solución.
APLICACIÓN Y ALCANCEDebido a su fácil implementación y su exhaustividad, que a la vez incrementa su coste al orden exponencial, son aplicables a casi todos sino todos los problemas posibles. Sin embargo, pierde utilidaddebido a que otras metodologías, dependiendo del problema, puede implementar una solución de menor coste computacional.
Ejemplo
El problema de la búsqueda de pareja estable
ENUNCIADOSupongamos que tenemos n hombres y n mujeres y dos matrices M y H que contienen las preferencias de los unos por los otros. Más concretamente, la fila M[i,·] es una ordenación (de mayor a menor) de las...
Miguel Gómez Jiménez Francisco Navas Sánchez
LA VUELTA ATRÁS
Del inglés “Backtracking” , la metodología de Vuelta Atrás tiene como objetivo la consecución de la solución a unproblema realizando el producto cartesiano de posibles soluciones al fin de hallar todas las posibilidades combinatorias y, de éstas, discernir cuál de ellas satisface los requisitos para ser verdaderasolución.
EL PROCEDIMIENTO DE VUELTA ATRÁS
El procedimiento que siguen estos algoritmos es tremendamente sencillo: En primer lugar define una codificación ilustrativa de la solución que garanticeincluir todas las combinaciones de posibles soluciones. Tras esto, rastrea una a una esas posibilidades chequeando si es o no solución final del problema.
COSTE COMPUTACIONAL
Debido a que el únicocomponente realmente utilizado en un algoritmo de vuelta atrás es el codificador de soluciones que es actualizado constantemente, el coste computacional genérico de estos algoritmos será exponencialcon base igual a las posibilidades de solución por elemento de la tupla solución elevado a un exponente igual al número de elementos de la tupla solución. Por ejemplo, en una tupla de cuatro elementoscodificada en binario natural tendremos 24 posibilidades ya que existen dos posibilidades por elementos de la tupla (0 y 1) y existen cuatro elementos en la tupla solución.
APLICACIÓN Y ALCANCEDebido a su fácil implementación y su exhaustividad, que a la vez incrementa su coste al orden exponencial, son aplicables a casi todos sino todos los problemas posibles. Sin embargo, pierde utilidaddebido a que otras metodologías, dependiendo del problema, puede implementar una solución de menor coste computacional.
Ejemplo
El problema de la búsqueda de pareja estable
ENUNCIADOSupongamos que tenemos n hombres y n mujeres y dos matrices M y H que contienen las preferencias de los unos por los otros. Más concretamente, la fila M[i,·] es una ordenación (de mayor a menor) de las...
Leer documento completo
Regístrate para leer el documento completo.