Antecedentes
Esta imagen ilustra el problema:
Puedo controlar el círculo rojo. Los objetivos son los triángulos azules. Las flechas negras indican la dirección en la que se moverán los objetivos.
Quiero recopilar todos los objetivos en el número mínimo de pasos.
Cada turno debo moverme 1 paso hacia la izquierda / derecha / arriba o abajo.
Cada turno, los objetivos también se moverán 1 paso de acuerdo con las instrucciones que se muestran en el tablero.
Manifestación
He puesto una demostración reproducible del problema aquí en Google appengine .
Me interesaría mucho si alguien puede superar la puntuación objetivo, ya que esto mostraría que mi algoritmo actual no es óptimo. (¡Debería imprimirse un mensaje de felicitación si logra esto!)
Problema
Mi algoritmo actual escala realmente mal con el número de objetivos. El tiempo aumenta exponencialmente y para 16 peces ya son varios segundos.
Me gustaría calcular la respuesta para tamaños de placa de 32 * 32 y con 100 objetivos móviles.
Pregunta
¿Cuál es un algoritmo eficiente (idealmente en Javascript) para calcular el número mínimo de pasos para recopilar todos los objetivos?
Lo que he probado
Mi enfoque actual se basa en la memorización, pero es muy lento y no sé si siempre generará la mejor solución.
Resuelvo el subproblema de "¿cuál es el número mínimo de pasos para recopilar un conjunto dado de objetivos y terminar en un objetivo en particular?".
El subproblema se resuelve de forma recursiva examinando cada opción para el objetivo anterior que ha visitado. Supongo que siempre es óptimo recopilar el subconjunto anterior de objetivos lo más rápido posible y luego pasar de la posición en la que terminó al objetivo actual lo más rápido posible (aunque no sé si esta es una suposición válida).
Esto da como resultado que se computen n * 2 ^ n estados que crecen muy rápidamente.
El código actual se muestra a continuación:
var DX=[1,0,-1,0];
var DY=[0,1,0,-1];
// Return the location of the given fish at time t
function getPt(fish,t) {
var i;
var x=pts[fish][0];
var y=pts[fish][1];
for(i=0;i<t;i++) {
var b=board[x][y];
x+=DX[b];
y+=DY[b];
}
return [x,y];
}
// Return the number of steps to track down the given fish
// Work by iterating and selecting first time when Manhattan distance matches time
function fastest_route(peng,dest) {
var myx=peng[0];
var myy=peng[1];
var x=dest[0];
var y=dest[1];
var t=0;
while ((Math.abs(x-myx)+Math.abs(y-myy))!=t) {
var b=board[x][y];
x+=DX[b];
y+=DY[b];
t+=1;
}
return t;
}
// Try to compute the shortest path to reach each fish and a certain subset of the others
// key is current fish followed by N bits of bitmask
// value is shortest time
function computeTarget(start_x,start_y) {
cache={};
// Compute the shortest steps to have visited all fish in bitmask
// and with the last visit being to the fish with index equal to last
function go(bitmask,last) {
var i;
var best=100000000;
var key=(last<<num_fish)+bitmask;
if (key in cache) {
return cache[key];
}
// Consider all previous positions
bitmask -= 1<<last;
if (bitmask==0) {
best = fastest_route([start_x,start_y],pts[last]);
} else {
for(i=0;i<pts.length;i++) {
var bit = 1<<i;
if (bitmask&bit) {
var s = go(bitmask,i); // least cost if our previous fish was i
s+=fastest_route(getPt(i,s),getPt(last,s));
if (s<best) best=s;
}
}
}
cache[key]=best;
return best;
}
var t = 100000000;
for(var i=0;i<pts.length;i++) {
t = Math.min(t,go((1<<pts.length)-1,i));
}
return t;
}Lo que he considerado
Algunas opciones sobre las que me he preguntado son:
Almacenamiento en caché de resultados intermedios. El cálculo de la distancia repite mucha simulación y los resultados intermedios pueden almacenarse en caché.
Sin embargo, no creo que esto impida que tenga una complejidad exponencial.Un algoritmo de búsqueda A *, aunque no me queda claro cuál sería una heurística admisible apropiada y qué tan efectivo sería en la práctica.
Investigar buenos algoritmos para el problema del viajante y ver si se aplican a este problema.
Tratar de demostrar que el problema es NP-difícil y, por lo tanto, no es razonable buscar una respuesta óptima.
fuente
Respuestas:
¿Ha buscado la literatura? Encontré estos papeles que parecen analizar su problema:
"Seguimiento de objetivos en movimiento y el problema del viajante no estacionario": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.85.9940
"El problema del viajante de destino móvil": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.6403
ACTUALIZACIÓN 1:
Los dos artículos anteriores parecen concentrarse en el movimiento lineal de la métrica euclidiana.
fuente
Método codicioso
Un enfoque sugerido en los comentarios es ir primero al objetivo más cercano.
He puesto una versión de la demostración que incluye el costo calculado a través de este método codicioso aquí .
El codigo es:
Para 10 objetivos, es aproximadamente el doble de la distancia óptima, pero a veces es mucho más (por ejemplo, * 4) y, en ocasiones, incluso alcanza el óptimo.
Este enfoque es muy eficiente, por lo que puedo permitirme algunos ciclos para mejorar la respuesta.
A continuación, estoy considerando usar métodos de colonias de hormigas para ver si pueden explorar el espacio de la solución de manera efectiva.
Método de colonia de hormigas
Un método de colonia de hormigas parece funcionar notablemente bien para este problema. El enlace en esta respuesta ahora compara los resultados cuando se usa el método de colonia de hormigas y codiciosos.
La idea es que las hormigas elijan su ruta de manera probabilística en función del nivel actual de feromonas. Después de cada 10 pruebas, depositamos feromona adicional a lo largo del camino más corto que encontraron.
Resultados
Este método de colonias de hormigas que utiliza 100 repeticiones de 10 hormigas sigue siendo muy rápido (37 ms para 16 objetivos en comparación con 3700 ms para la búsqueda exhaustiva) y parece muy preciso.
La siguiente tabla muestra los resultados de 10 ensayos con 16 objetivos:
El método de las hormigas parece significativamente mejor que el codicioso y, a menudo, muy cerca del óptimo.
fuente
El problema puede representarse en términos del problema del vendedor ambulante generalizado y luego convertirse en un problema del vendedor ambulante convencional. Este es un problema bien estudiado. Es posible que las soluciones más eficientes al problema del OP no sean más eficientes que las soluciones al TSP, pero de ninguna manera seguro (probablemente no estoy aprovechando algunos aspectos de la estructura del problema del OP que permitirían una solución más rápida , como su naturaleza cíclica). De cualquier manera, es un buen punto de partida.
De C. Noon & J. Bean, Una transformación eficiente del problema generalizado del viajante de comercio :
Para el problema del OP:
Nes la ubicación de un pez en particular en un momento determinado. Represente esto como(x, y, t), donde(x, y)es una coordenada de la cuadrícula ytes el momento en que el pez estará en esta coordenada. Para el pez más a la izquierda en el ejemplo del OP, los primeros (basados en 1) son:(3, 9, 1), (4, 9, 2), (5, 9, 3)cuando el pez se mueve hacia la derecha.fish(n_i)devuelva el ID del pez representado por el nodo. Para dos miembros cualesquiera de N podemos calcularmanhattan(n_i, n_j)la distancia de Manhattan entre los dos nodos, ytime(n_i, n_j) el desplazamiento de tiempo entre los nodos.S_iconstará solo de los nodos para los quefish(n) == i.iyjfish(n_i) != fish(n_j)luego hay un arco entreiyj.time(n_i, n_j), o indefinido sitime(n_i, n_j) < distance(n_i, n_j)(es decir, no se puede llegar a la ubicación antes de que llegue el pez, quizás porque está al revés en el tiempo). Los arcos de este último tipo pueden eliminarse.La solución de este problema resultaría en una única visita a cada subconjunto de nodos (es decir, cada pez se obtiene una vez) para una ruta con un costo mínimo (es decir, un tiempo mínimo para obtener todos los peces).
El artículo continúa describiendo cómo la formulación anterior puede transformarse en un problema tradicional de vendedor ambulante y posteriormente resolverse o aproximarse con técnicas existentes. No he leído los detalles, pero otro documento que hace esto de una manera que proclama ser eficiente es este .
Hay problemas obvios con la complejidad. En particular, ¡el espacio nodal es infinito! Esto se puede aliviar generando solo nodos hasta un cierto horizonte de tiempo. Si
tes el número de pasos de tiempo para generar nodos yfes el número de peces, entonces el tamaño del espacio del nodo serát * f. Un nodo en un momentojtendrá como máximo(f - 1) * (t - j)arcos salientes (ya que no puede retroceder en el tiempo ni a su propio subconjunto). El número total de arcos será del orden det^2 * f^2arcos. Es probable que la estructura del arco se pueda arreglar, para aprovechar el hecho de que las rutas de los peces son eventualmente cíclicas. Los peces repetirán su configuración una vez cada mínimo común denominador de la duración de sus ciclos, por lo que tal vez se pueda utilizar este hecho.No sé lo suficiente sobre el TSP para decir si esto es factible o no, y no creo que signifique que el problema publicado sea necesariamente NP-hard ... pero es un enfoque para encontrar una solución óptima o limitada .
fuente
Creo que otro enfoque sería:
Cita wikipedia:
En matemáticas, un diagrama de Voronoi es una forma de dividir el espacio en varias regiones. Un conjunto de puntos (llamados semillas, sitios o generadores) se especifica de antemano y para cada semilla habrá una región correspondiente que consta de todos los puntos más cercanos a esa semilla que a cualquier otra.
Entonces, elige un objetivo, sigue su camino para algunos pasos y establece un punto de semilla allí. Haga esto también con todos los demás objetivos y obtendrá un diagrama de voroni. Dependiendo de la zona en la que te encuentres, te mueves al punto de partida de la misma. Viola, tienes el primer pescado. Ahora repita este paso hasta que los compre todos.
fuente