El algoritmo vecino más cercano fue uno de los primeros algoritmos utilizados para resolver el problema del vendedor ambulante . En él, el vendedor comienza en una ciudad aleatoria y visita repetidamente la ciudad más cercana hasta que todos hayan sido visitados. Rápidamente produce un recorrido corto, pero generalmente no es el óptimo.
Algoritmo [ editar ]
Estos son los pasos del algoritmo:
- Inicialice todos los vértices como no visitados.
- Seleccione un vértice arbitrario, configúrelo como el vértice actual u . Marca u como visitado.
- Descubra el borde más corto que conecta el vértice actual u y un vértice no visitado v .
- Establezca v como el vértice actual u . Marque v como visitado.
- Si se visitan todos los vértices del dominio, entonces finalice. De lo contrario, vaya al paso 3.
La secuencia de los vértices visitados es la salida del algoritmo.
El algoritmo vecino más cercano es fácil de implementar y se ejecuta rápidamente, pero a veces puede perder rutas más cortas que se notan fácilmente con la comprensión humana, debido a su naturaleza "codiciosa". Como guía general, si las últimas etapas del recorrido son comparables en longitud a las primeras etapas, entonces el recorrido es razonable; si son mucho mayores, entonces es probable que existan tours mucho mejores. Otra comprobación es utilizar un algoritmo como el algoritmo de límite inferior para estimar si este recorrido es lo suficientemente bueno.
En el peor de los casos, el algoritmo da como resultado un recorrido que es mucho más largo que el recorrido óptimo. Para ser precisos, por cada constante r hay una instancia del problema del vendedor ambulante de tal manera que la duración del recorrido calculada por el algoritmo vecino más cercano es mayor que r veces la duración del recorrido óptimo. Además, para cada número de ciudades hay una asignación de distancias entre las ciudades para las cuales la heurística vecina más cercana produce el peor recorrido único posible. (Si el algoritmo se aplica en cada vértice como el vértice inicial, la mejor ruta encontrada será mejor que al menos N / 2-1 otros recorridos, donde N es el número de vértices) [1]
El algoritmo vecino más cercano puede no encontrar un recorrido factible en absoluto, incluso cuando exista.
(Redirigido desde la regla de Warnsdorff )
El recorrido de un caballero es una secuencia de movimientos de un caballero en un tablero de ajedrez de modo que el caballero visita cada casilla solo una vez. Si el caballero termina en una casilla que es el movimiento de un caballero desde la casilla inicial (de modo que pueda recorrer el tablero nuevamente de inmediato, siguiendo el mismo camino), el recorrido está cerrado , de lo contrario está abierto . [1] [2]
El problema del recorrido del caballero es el problema matemático de encontrar el recorrido del caballero. Crear un programa para encontrar el recorrido de un caballero es un problema común dado a los estudiantes de informática . [3] Las variaciones del problema del recorrido del caballero incluyen tableros de ajedrez de diferentes tamaños que los 8 × 8 habituales , así como tableros irregulares (no rectangulares).
Teoría [ editar ]
El problema del recorrido del caballero es una instancia del problema más general del camino hamiltoniano en la teoría de grafos . El problema de encontrar el recorrido de un caballero cerrado es igualmente una instancia del problema del ciclo hamiltoniano . A diferencia del problema general del camino hamiltoniano, el problema del recorrido del caballero se puede resolver en tiempo lineal . [4]
Historia [ editar ]
La primera referencia conocida al problema de la gira del caballero se remonta al siglo IX d. C. En Rudrata 's Kavyalankara [5] (5.15), una obra en sánscrito en la Poética, el patrón de recorrido del caballo en un régimen de media pensión se ha presentado como una figura poética elaborada ( citra-Alankara ) llama la turagapadabandha o' acuerdo en el pasos de un caballo ". El mismo verso en cuatro líneas de ocho sílabas se puede leer de izquierda a derecha o siguiendo el camino del caballero en la gira. Dado que los sistemas de escritura índica utilizados para sánscrito son silábicos, se puede pensar que cada sílaba representa un cuadrado en un tablero de ajedrez. El ejemplo de Rudrata es el siguiente:
| से | ना | ली | ली | ली | ना | ना | ली |
| ली | ना | ना | ना | ना | ली | ली | ली |
| न | ली | ना | ली | ले | ना | ली | ना |
| ली | ली | ली | ना | ना | ना | ना | ली |
transcrito:
| se | n / A | lī | lī | lī | n / A | n / A | lī |
| lī | n / A | n / A | n / A | n / A | lī | lī | lī |
| n / A | lī | n / A | lī | le | n / A | lī | n / A |
| lī | lī | lī | n / A | n / A | n / A | n / A | lī |
Por ejemplo, la primera línea se puede leer de izquierda a derecha o moviéndose desde el primer cuadrado a la segunda línea, la tercera sílaba (2.3) y luego a 1.5 a 2.7 a 4.8 a 3.6 a 4.4 a 3.2.
Una gira informada en el quinto libro de Bhagavantabaskaraby por Bhat Nilakantha, un trabajo ciclopédico en sánscrito sobre rituales, leyes y política, escrito alrededor de 1600 o alrededor de 1700 describe las giras de 3 caballeros. Los recorridos no solo son reentrantes sino también simétricos y los versos se basan en el mismo recorrido a partir de diferentes cuadrados [6] . El trabajo de Bhat Nilakantha es un logro extraordinario al ser un recorrido cerrado totalmente simétrico, anterior al trabajo de Euler (1759) por al menos 60 años.
Uno de los primeros matemáticos en investigar la gira del caballero fue Leonhard Euler . El primer procedimiento para completar la gira del caballero fue la regla de Warnsdorf, descrita por primera vez en 1823 por HC von Warnsdorf.
En el siglo XX, el grupo de escritores Oulipo lo utilizó entre muchos otros. El ejemplo más notable es el recorrido del caballero 10 × 10 que establece el orden de los capítulos en el novedoso Manual del usuario Life a de Georges Perec .
El sexto juego del Campeonato Mundial de Ajedrez 2010 entre Viswanathan Anand y Veselin Topalov vio a Anand hacer 13 movimientos consecutivos de caballeros (aunque con ambos caballeros); Los comentaristas en línea bromearon que Anand estaba tratando de resolver el problema de la gira del caballero durante el juego.
Existencia [ editar ]
Schwenk [7] demostró que para cualquier tablero m × n con m ≤ n , un recorrido de caballero cerrado siempre es posible a menos que se cumplan una o más de estas tres condiciones:
- m y n son ambos impares
- m = 1, 2 o 4
- m = 3 yn = 4, 6 u 8.
Cull y col. y Conrad et al. demostró que en cualquier tablero rectangular cuya dimensión más pequeña es al menos 5, hay un recorrido de caballero (posiblemente abierto). [4] [8]
Número de recorridos [ editar ]
En un tablero de 8 × 8 , hay exactamente 26,534,728,821,064 recorridos cerrados dirigidos (es decir, dos recorridos a lo largo del mismo camino que viajan en direcciones opuestas se cuentan por separado, al igual que las rotaciones y los reflejos ). [9] [10] [11] El número de recorridos cerrados no dirigidos es la mitad de este número, ya que cada recorrido se puede rastrear en reversa. Hay 9.862 recorridos cerrados no dirigidos en una tabla de 6 × 6 . [12]
El número de todos los recorridos dirigidos (abiertos y cerrados) en una tabla n × n para n = 1, 2, ... son:
- 1; 0; 0; 0; 1.728; 6.637.920; 165.575.218.320; 19,591,828,170,979,904. (secuencia A165134 en el OEIS ).
Encontrar tours con computadoras [ editar ]
Hay varias formas de encontrar el recorrido de un caballero en una tabla determinada con una computadora. Algunos de estos métodos son algoritmos, mientras que otros son heurísticos .
Algoritmos de fuerza bruta [ editar ]
Una búsqueda de fuerza bruta para la gira de un caballero no es práctica en todos los tableros, excepto en los más pequeños. [13] Por ejemplo, hay aproximadamente 4 × 10 51 posibles secuencias de movimiento en un tablero de 8 × 8 , [14] y está muy por encima de la capacidad de las computadoras modernas (o redes de computadoras) para realizar operaciones en un conjunto tan grande . Sin embargo, el tamaño de este número no es indicativo de la dificultad del problema, que puede resolverse "utilizando la perspicacia humana y el ingenio ... sin mucha dificultad". [13]
Divide y conquista algoritmos [ editar ]
Al dividir el tablero en piezas más pequeñas, construir recorridos en cada pieza y juntar las piezas, se pueden construir recorridos en la mayoría de los tableros rectangulares en tiempo lineal , es decir, en un tiempo proporcional al número de cuadrados en el tablero. [8] [15]
La regla de Warnsdorff [ editar ]
La regla de Warnsdorff es heurística para encontrar el recorrido de un solo caballero. El caballero se mueve para que siempre proceda al cuadrado desde el cual el caballero tendrá la menor cantidad de movimientos hacia adelante. Al calcular el número de movimientos hacia adelante para cada cuadro candidato, no contamos los movimientos que vuelven a visitar cualquier cuadro ya visitado. Es posible tener dos o más opciones para las cuales el número de movimientos hacia adelante es igual; Existen varios métodos para romper tales lazos, incluido uno ideado por Pohl [16] y otro por Squirrel y Cull. [17]
Esta regla también puede aplicarse más generalmente a cualquier gráfico. En términos de teoría de grafos, cada movimiento se realiza al vértice adyacente con el menor grado [18] . Aunque el problema del camino hamiltoniano es NP-duro en general, en muchos gráficos que ocurren en la práctica, esta heurística es capaz de localizar con éxito una solución en tiempo lineal . [16] La gira del caballero es un caso tan especial. [19]
La heurística fue descrita por primera vez en "Des Rösselsprungs einfachste und allgemeinste Lösung" por HC von Warnsdorff en 1823. [19] Gordon Horsington escribió un programa informático que encuentra un recorrido de caballero para cualquier posición inicial utilizando la regla de Warnsdorff y publicado en 1984. libro Century / Acorn User Book of Computer Puzzles . [20]
Soluciones de redes neuronales [ editar ]
El problema del recorrido del caballero también se presta para ser resuelto por una implementación de red neuronal . [21] La red está configurada de tal manera que el movimiento de cada caballero legal está representado por una neurona , y cada neurona se inicializa aleatoriamente para ser "activa" o "inactiva" (salida de 1 o 0), con 1 lo que implica que la neurona Es parte de la solución. Cada neurona también tiene una función de estado (descrita a continuación) que se inicializa a 0.
Cuando se permite que la red funcione, cada neurona puede cambiar su estado y salida en función de los estados y salidas de sus vecinos (los que se alejan exactamente de un caballero) de acuerdo con las siguientes reglas de transición:
dónde representa intervalos de tiempo discretos, es el estado del cuadrado de conexión de la neurona cuadrar , es la salida de la neurona de a y Es el conjunto de vecinos de la neurona.
Aunque son posibles casos divergentes, la red eventualmente debería converger, lo que ocurre cuando ninguna neurona cambia su estado con el tiempo a . Cuando la red converge, la red codifica un recorrido de caballero o una serie de dos o más circuitos independientes dentro de la misma placa.
No hay comentarios:
Publicar un comentario