Indice de área foliar

2101 palabras 9 páginas
BACKTRACKING: EJEMPLOS

Bibliografía: - Fundamentals of Computers Algorithms, Horowitz - Sahni. - Estructuras de Datos y Algoritmos, Aho - Hopcroft - Ullman. - Algorithms in C, Sedgewick.

EJEMPLO 1:

Un problema clásico es el problema del viajante: dadas n ciudades conectadas todas con todas, “encontrar el camino que recorra todas las ciudades con mínimo costo”.
Se parte de una ciudad cualquiera, y se obtiene el siguiente espacio de soluciones:

(1)

(1,2) (1,3) ....... (1,n)

(1,2,3) (1,2,n) .......... (1,n,2) ...... ..................

(1,2,3,4,...,n) En este nivel se tienen
…ver más…

Los jugadores alternan sus movimientos, y el estado del juego puede ser representado por la posición del tablero. Se asume que hay un número finito de posiciones en el tablero y que el juego tiene alguna regla que asegure su terminación. Con cada juego asociamos un árbol llamado árbol del juego. Cada nodo en el árbol representa una posición en el tablero. A la raíz le asociamos la posición de comienzo. Si la posición x está asociada con el nodo n, luego los hijos de n corresponden al conjunto de movidas permitidas desde la posición x, y con cada hijo es asociada la posición del tablero resultante. Por ejemplo la siguiente figura muestra parte del árbol del ta-te-ti:

juega A

... . . . . . .

juega A

juega B

juega A

Las hojas de un árbol de juego corresponden a las posiciones del tablero donde no hay mas movimientos, porque uno de los jugadores ha ganado o todos los casilleros están llenos y a ocurrido un empate. Se asocia un valor a cada nodo del árbol. Primero se asignan valores a las hojas planteado desde el punto de vista de uno de los jugadores, tomemos A. Los valores serán -1, 0 o 1, si A pierde, gana o empata respectivamente. Los valores se propagan hacia arriba en el árbol de acuerdo a la siguiente regla:
Si un nodo corresponde a la posición del tablero donde le toca jugar a A, luego el valor con el que se rotura este nodo es el máximo de los valores

Documentos relacionados

  • Evaluación Del Área Foliar Del Rabanito
    1824 palabras | 8 páginas
  • La alta direccion y sus habilidades
    1649 palabras | 7 páginas
  • Fisiología de la planta de camote
    1525 palabras | 7 páginas
  • morfologia y fisiologia de los pastos
    6902 palabras | 28 páginas
  • Informe De Pasantía
    2282 palabras | 10 páginas
  • La Hoja - Botánica
    3885 palabras | 16 páginas
  • Enfermedades en el cultivo del sesamo
    3786 palabras | 16 páginas
  • Estudio de prefactibilidad para la creación y puesta en marcha de una empresa procesadora de néctar de granadilla y cholupa en la ciudad de neiva
    9333 palabras | 38 páginas
  • Control de sigatoka negra en banano orgánico utilizando trichoderma harzianum
    18583 palabras | 75 páginas
  • Morfologia De La Yuca
    6009 palabras | 25 páginas