Dada una lista de puntos, encuentre el camino más corto que visite todos los puntos y regrese al punto de partida.
El problema del vendedor ambulante es bien conocido en el campo de la informática, ya que hay muchas formas de calcularlo / aproximarlo. Se ha resuelto para grupos muy grandes de puntos, pero algunos de los más grandes requieren muchos años de CPU para terminar.
No te quemes con la papa.
Hot Potato es un juego en el que 2+ jugadores pasan una "papa" en círculo mientras suena la música. El objetivo es pasarlo al siguiente jugador rápidamente. Si estás sosteniendo la papa cuando la música se detiene, estás fuera.
El objeto del vendedor de patatas calientes es:
Dado un conjunto de 100 puntos únicos , devuelva esos puntos en un mejor orden ( distancia total más corta como se define más abajo ). Esto "pasará" el problema al siguiente jugador. Tienen que mejorarlo y pasarlo al siguiente, etc. Si un jugador no puede mejorarlo, están fuera y el juego continúa hasta que quede un jugador.
Para evitar que esto sea una competencia de "fuerza bruta-me-a-camino", existen estas estipulaciones:
No puede tomar más de un minuto para pasar la papa. Si no ha encontrado y pasado una solución más corta para el momento en que transcurre un minuto, está fuera.
No puede cambiar la posición de más de 25 puntos. Para ser exactos, los
>= 75
puntos deben estar en la misma posición en que los recibió. No importa lo que usted decida cual el cambio, sólo la cantidad cambia.
Cuando solo queda un jugador, él es el ganador de ese juego y recibe un punto. Un torneo consiste en 5*n
juegos, donde n
está el número de jugadores. Cada juego, el jugador inicial se rotará y el orden restante del jugador se barajará . El jugador con más puntos al final es el ganador del torneo. Si el torneo termina con un empate por el primer lugar, se jugará un nuevo torneo solo con los concursantes. Esto continuará hasta que no haya empate.
El jugador inicial de cada juego recibirá un conjunto de puntos seleccionados pseudoaleatoriamente sin ningún orden en particular.
Los puntos se definen como un par de x,y
coordenadas enteras en una cuadrícula cartesiana. La distancia se mide usando la distancia Manhattan , |x1-x2| + |y1-y2|
. Todas las coordenadas estarán en el [0..199]
rango.
Entrada
La entrada se proporciona con un argumento de cadena única. Constará de 201 enteros separados por comas que representan el número de jugadores actuales ( m
) y 100 puntos:
m,x0,y0,x1,y1,x2,y2,...,x99,y99
El orden de estos puntos es el camino actual. La distancia total se obtiene sumando la distancia desde cada punto al siguiente ( dist(0,1) + dist(1,2) + ... + dist(99,0)
). ¡No olvide volver al inicio al calcular la distancia total!
Tenga en cuenta que nom
es el número de jugadores que comenzaron el juego, es el número que todavía están en.
Salida
La salida se da de la misma manera que la entrada, menos m
; una sola cadena que contiene enteros separados por comas que representan los puntos en su nuevo orden.
x0,y0,x1,y1,x2,y2,...,x99,y99
El programa de control esperará la salida solo por un minuto. Cuando se recibe la salida, verificará que:
- la salida está bien formada
- la salida consta de solo y todos los 100 puntos presentes en la entrada
>=75
los puntos están en sus posiciones originales- la longitud de la ruta es menor que la ruta anterior
Si alguno de estos controles falla (o no hay salida), estás fuera y el juego pasará al siguiente jugador.
Programa de control
Puede encontrar el programa de control en este enlace . El programa de control en sí mismo es determinista y se publica con una semilla ficticia de 1
. La semilla utilizada durante la puntuación será diferente, así que no te molestes en analizar el orden de giro / listas de puntos que escupe.
La clase principal es Tourney
. Ejecutar esto hará un torneo completo con los concursantes dados como argumentos. Escupe al ganador de cada juego y una cuenta al final. Un torneo de muestra con dos SwapBots se ve así:
Starting tournament with seed 1
(0) SwapBot wins a game! Current score: 1
(1) SwapBot wins a game! Current score: 1
(1) SwapBot wins a game! Current score: 2
(1) SwapBot wins a game! Current score: 3
(0) SwapBot wins a game! Current score: 2
(1) SwapBot wins a game! Current score: 4
(1) SwapBot wins a game! Current score: 5
(1) SwapBot wins a game! Current score: 6
(1) SwapBot wins a game! Current score: 7
(1) SwapBot wins a game! Current score: 8
Final Results:
Wins Contestant
2 (0) SwapBot
8 (1) SwapBot
Si quieres probar solo un juego a la vez, puedes ejecutar la Game
clase en su lugar. Esto ejecutará un juego con jugadores en el orden dado como argumentos. Por defecto, también imprimirá una jugada por jugada que muestra el jugador actual y la longitud de la ruta.
También se incluyen algunos jugadores de prueba: SwapBot
, BlockPermuter
, y TwoSwapBot
. Los dos primeros no se incluirán en las carreras de puntuación, así que siéntete libre de usarlos y abusar de ellos durante las pruebas. TwoSwapBot
se incluirá en la evaluación, y él no es holgazán, así que traiga su juego A.
Miscelánea
No puede guardar información de estado, y cada turno es una ejecución separada de su programa. La única información que recibirá en cada turno es el conjunto de puntos.
No puedes usar recursos externos. Esto incluye llamadas de red y acceso a archivos.
No puede utilizar las funciones de biblioteca diseñadas para resolver / ayudar con el problema de TSP o sus variantes.
No puedes manipular o interferir con otros jugadores de ninguna manera.
No puede manipular o interferir con el programa de control o cualquier clase o archivo incluido de ninguna manera.
Se permite el subprocesamiento múltiple.
Un envío por usuario. Si envía más de una entrada, solo ingresaré la primera. Si desea cambiar su envío, edite / elimine el original.
El torneo se ejecutará en Ubuntu 13.04, en una computadora con una CPU i7-3770K y 16 GB de RAM. No se ejecutará en una VM. Cualquier cosa que perciba como maliciosa descalificará de inmediato la entrada actual y futura que envíe.
Todas las entradas deben ejecutarse desde la línea de comandos con software gratuito ( como en cerveza ). Si tengo problemas para compilar / ejecutar su entrada, solicitaré ayuda en los comentarios. Si no responde o finalmente no puedo hacerlo funcionar, será descalificado.
Resultados (22 de mayo de 2014)
Nuevos resultados están en! UntangleBot ha vencido a la competencia bastante bien. TwoSwapBot logró siete victorias, y SANNbot también logró una victoria. Aquí hay un marcador y un enlace a la salida sin formato :
Wins Contestant
22 (2) ./UntangleBot
7 (0) TwoSwapBot
1 (5) SANNbot.R
0 (1) BozoBot
0 (3) Threader
0 (4) DivideAndConquer
Tal como está ahora , UntangleBot ha ganado la marca de verificación. Sin embargo, no dejes que eso te desanime de entrar, ya que correré el torneo a medida que aparezcan más concursantes y cambie la respuesta aceptada en consecuencia.
fuente
Respuestas:
UntangleBot (anteriormente NiceBot)
Un bot C ++ 11 que usa dos estrategias.
Al principio intentará "desenredar" la ruta si es posible, detectando intersecciones entre rutas que estén más cerca de 25 puntos (ya que desenredar implica modificar todos los puntos intermedios).
Si la primera estrategia falla, intercambia puntos aleatoriamente para encontrar mejores distancias hasta que se encuentre un mejor camino.
Este bot constantemente vence a TwoSwapBot con una proporción aproximada de cinco victorias por una derrota en mis torneos de prueba.
fuente
SANNbot
(un bot de recocido simulado en R )
Debería ser llamado con
Rscript SANNbot.R
.La idea es relativamente simple: cada turno es un "paso de enfriamiento" de un recocido simulado con el número de jugadores que todavía están en el juego como "temperatura" (modificada por la distancia actual sobre 12000, es decir, aproximadamente la distancia inicial). La única diferencia con un recocido simulado adecuado es que verifiqué que no permuto más de 25 elementos y si utilicé 20 movimientos pero la secuencia resultante vale más que la inicial, entonces comienza de nuevo.
fuente
java Tourney "java Swapbot" "Rscript SANNbot.R"
y parecía funcionar.u
límites de verificación, esto no sucede (y funciona mucho mejor). Si bien su código parece bastante sencillo, no conozco las peculiaridades de R, por lo que no puedo decir si la lógica es incorrecta. (la última versión del controlador dará mensajes sobre por qué un bot se apaga cuando se ejecutaGame
, por lo que podría ayudar a detectar el problema)BozoBot
Utiliza la lógica compleja detrás de Bozosort para encontrar un mejor camino. Se parece a esto.
¡BozoBot ahora se ha mejorado con Multithreading ! Cuatro minions ahora hacen malabares sin rumbo con puntos hasta que tropiezan con una mejora. ¡El primero en encontrar una solución recibe una cookie!Aparentemente fallo en el multihilo.
fuente
new Thread(new Minion()).start()
TwoSwapBot
Una actualización a
SwapBot
, este chico comprueba cada par de intercambios. Primero, verifica si cualquier intercambio único acortará el camino. Si lo hace, vuelve inmediatamente. De lo contrario, verifica cada uno para ver si otro intercambio lo acortará. Si no, él simplemente muere.Si bien el camino aún es semi-aleatorio, normalmente regresa en unos 100 ms. Si tiene que verificar todos y cada 2 intercambios (aproximadamente 25M), le tomará unos 20 segundos.
En el momento de la presentación, esto venció a todos los demás competidores en las rondas de prueba.
fuente
Enhebrador
Este bot
410 piezas de2510 puntosLa idea es encontrar la mejor mejora en el camino, para que los otros bots fallen con su lógica.
fuente
println
aprint
para deshacerme de la nueva línea al final de su salida. De lo contrario, se estrella.println
aprint
e hizo la dinámica hilos. Ahora comienza con 10 hilos ...Divide and Conquer + Greedy Bot
NOTA: Miré su código,
Game
que incluye lo siguiente en Game.parsePath:Sin embargo, no hay
catch(NumberFormatException)
bloque, por lo que es probable que su programa se bloquee cuando un programa de jugador emite una cadena (como se demuestra al final delmain
método de mi programa ). Le aconsejo que solucione esto, porque los programas pueden generar excepciones, rastreos de pila o similares. De lo contrario, comente esa línea en mi programa antes de ejecutarla.Volver al tema
Esta implementación (en Java) divide la lista de puntos en trozos de 25, espaciados aleatoriamente en la lista. Luego, crea hilos para acortar el camino entre los puntos en cada fragmento (Por lo tanto, "Divide y vencerás"). El hilo principal monitorea a los demás y se asegura de presentar la solución más corta dentro del límite de tiempo. Si un hilo muere con o sin solución, comienza otro hilo nuevamente en un trozo diferente.
Cada hilo utiliza el algoritmo "codicioso", que comienza en un punto aleatorio, va al punto más cercano y se repite hasta que todos los puntos estén cubiertos (por lo tanto, "codicioso").
Notas
Simplemente compile y use
java DivideAndConquer.class
para ejecutar.fuente
<200
tokens antes de intentar el análisis. Aún mejor comprobarlo de todos modos.)
en la línea 19; cambiarsubstr
asubstring
en 38; Inicializaridx
a algo en elrun()
método.