javascript - sencillos - ¿Cómo puedo encontrar el camino más corto entre 100 objetivos en movimiento?(Demostración en vivo incluida)

practicas de javascript

Question

Fondo

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 que se moverán los objetivos.

Quiero recoger todos los objetivos en la cantidad mínima de pasos.

Cada turno debo mover 1 paso hacia la izquierda / derecha / arriba o hacia 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 jugable del problema aquí en Google appengine .

Me interesaría mucho si alguien puede superar el puntaje objetivo, ya que esto mostraría que mi algoritmo actual no es óptimo. (¡Debería imprimirse un mensaje de felicitación si gestionas esto!)

Problema

Mi algoritmo actual escala muy mal con la cantidad de objetivos. El tiempo aumenta exponencialmente y para 16 peces ya es varios segundos.

Me gustaría calcular la respuesta para los tamaños de tablero de 32 * 32 y con 100 objetivos móviles.

Pregunta

¿Qué es un algoritmo eficiente (idealmente en Javascript) para calcular el número mínimo de pasos para recolectar todos los objetivos?

Lo que he intentado

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 recolectar un conjunto dado de objetivos y terminar en un objetivo particular?".

El subproblema se resuelve de manera recursiva examinando cada opción del objetivo anterior que se 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 crece 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 de las opciones que me he preguntado son:

1. Almacenamiento en caché de resultados intermedios. El cálculo de distancia repite una gran cantidad de simulación y los resultados intermedios se pueden almacenar en caché.
   Sin embargo, no creo que esto pueda evitar que tenga una complejidad exponencial.

2. Un algoritmo de búsqueda A * aunque no me queda claro qué heurística admisible sería adecuada y qué tan efectiva sería en la práctica.

3. Investigar buenos algoritmos para el problema del vendedor viajero y ver si se aplican a este problema.

4. Tratando de demostrar que el problema es NP-difícil y, por lo tanto, irracional buscar una respuesta óptima para ello.

Answer 1

Método codicioso

Un enfoque sugerido en los comentarios es ir primero al objetivo más cercano.

He presentado una versión de la demostración que incluye el costo calculado a través de este método codicioso here .

El código es:

function greedyMethod(start_x,start_y) {
  var still_to_visit = (1<<pts.length)-1;
  var pt=[start_x,start_y];
  var s=0;
  while (still_to_visit) {
    var besti=-1;
    var bestc=0;
    for(i=0;i<pts.length;i++) {
      var bit = 1<<i;
      if (still_to_visit&bit) {
        c = fastest_route(pt,getPt(i,s));
        if (besti<0 || c<bestc) {
          besti = i;
          bestc = c;
        }
      }
    }
    s+=c;
    still_to_visit -= 1<<besti;
    pt=getPt(besti,s);
  }
  return s;
}

Para 10 objetivos, es aproximadamente el doble de la distancia óptima, pero a veces mucho más (por ejemplo, * 4) y, ocasionalmente, llega al nivel óptimo.

Este enfoque es muy eficiente, así que puedo permitirme algunos ciclos para mejorar la respuesta.

Luego, 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 tanto el método codicioso como el de colonia de hormigas.

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 intentos, depositamos feromonas adicionales a lo largo del camino más corto que encontraron.

function antMethod(start_x,start_y) {
  // First establish a baseline based on greedy
  var L = greedyMethod(start_x,start_y);
  var n = pts.length;
  var m = 10; // number of ants
  var numrepeats = 100;
  var alpha = 0.1;
  var q = 0.9;
  var t0 = 1/(n*L);

  pheromone=new Array(n+1); // entry n used for starting position
  for(i=0;i<=n;i++) {
    pheromone[i] = new Array(n);
    for(j=0;j<n;j++)
      pheromone[i][j] = t0; 
  }

  h = new Array(n);
  overallBest=10000000;
  for(repeat=0;repeat<numrepeats;repeat++) {
    for(ant=0;ant<m;ant++) {
      route = new Array(n);
      var still_to_visit = (1<<n)-1;
      var pt=[start_x,start_y];
      var s=0;
      var last=n;
      var step=0;
      while (still_to_visit) {
        var besti=-1;
        var bestc=0;
        var totalh=0;
        for(i=0;i<pts.length;i++) {
          var bit = 1<<i;
          if (still_to_visit&bit) {
            c = pheromone[last][i]/(1+fastest_route(pt,getPt(i,s)));
            h[i] = c;
            totalh += h[i];
            if (besti<0 || c>bestc) {
              besti = i;
              bestc = c;
            }
          }
        }
        if (Math.random()>0.9) {
          thresh = totalh*Math.random();
          for(i=0;i<pts.length;i++) {
            var bit = 1<<i;
            if (still_to_visit&bit) {
              thresh -= h[i];
              if (thresh<0) {
                besti=i;
                break;
              }
            }
          }
        }
        s += fastest_route(pt,getPt(besti,s));
        still_to_visit -= 1<<besti;
        pt=getPt(besti,s);
        route[step]=besti;
        step++;
        pheromone[last][besti] = (1-alpha) * pheromone[last][besti] + alpha*t0;
        last = besti;
      }
      if (ant==0 || s<bestantscore) {
        bestroute=route;
        bestantscore = s;
      }
    }
    last = n;
    var d = 1/(1+bestantscore);
    for(i=0;i<n;i++) {
      var besti = bestroute[i];
      pheromone[last][besti] = (1-alpha) * pheromone[last][besti] + alpha*d;
      last = besti;
    }
    overallBest = Math.min(overallBest,bestantscore);
  }
  return overallBest;
}

Resultados

Este método de colonia de hormigas que usa 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:

   Greedy   Ant     Optimal
   46       29      29
   91       38      37
  103       30      30
   86       29      29
   75       26      22
  182       38      36
  120       31      28
  106       38      30
   93       30      30
  129       39      38

El método de la hormiga parece ser mucho mejor que codicioso y, a menudo, muy cercano al óptimo.

Answer 2

¿Has buscado en la literatura? Encontré estos documentos que parecen analizar su problema:

• "Seguimiento de objetivos en movimiento y el problema del vendedor ambulante no estacionario": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.85.9940

• "El problema del vendedor ambulante con objetivo 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 para la métrica euclidiana.

Answer 3

Creo que otro enfoque sería:

• calcular el camino de los objetivos - predictivo.
• que usar diagramas de Voronoi

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, eliges un objetivo, sigues su camino para algunos pasos y estableces un punto inicial allí. Haga esto con todos los demás objetivos y obtendrá un diagrama de voroni. Dependiendo de en qué área se encuentre, se mueve al punto de inicio de la misma. Viola, tienes el primer pez. Ahora repita este paso hasta que los haya comprado todos.

Answer 4

El problema puede ser representado en términos del Problema del Vendedor Viajero Generalizado, y luego convertido en un Problema de Vendedor Viajero convencional. Este es un problema bien estudiado. Es posible que las soluciones más eficientes para el problema del OP no sean más eficientes que las soluciones del TSP, pero de ninguna manera son ciertas (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 del vendedor ambulante generalizado :

El problema del vendedor ambulante generalizado (GTSP) es un modelo útil para problemas que involucran decisiones de selección y secuencia. La versión asimétrica del problema se define en un gráfico dirigido con nodos N, conectando arcos A y un vector de costos de arco correspondientes c. Los nodos están agrupados previamente en m conjuntos de nodos mutuamente exclusivos y exhaustivos. Los arcos de conexión se definen solo entre los nodos que pertenecen a diferentes conjuntos, es decir, no hay arcos dentro del conjunto. Cada arco definido tiene un costo no negativo correspondiente. El GTSP puede establecerse como el problema de encontrar un ciclo de m-arco de costo mínimo que incluye exactamente un nodo de cada conjunto de nodos .

Para el problema de OP:

• Cada miembro de N es 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, y t es el tiempo en el que el pez estará en esta coordenada. Para el pez más a la izquierda en el ejemplo del PO, los primeros de estos (basados ​​en 1) son: (3, 9, 1), (4, 9, 2), (5, 9, 3) medida que el pez se mueve hacia la derecha.
• Para cualquier miembro de N, let fish(n_i) devuelve la ID del pez representado por el nodo. Para dos miembros de N podemos calcular manhattan(n_i, n_j) para la distancia de Manhattan entre los dos nodos, y el time(n_i, n_j ) para la time(n_i, n_j de tiempo entre los nodos.
• El número de subconjuntos disjuntos m es igual al número de peces. El subconjunto disjunto S_i consistirá solo de los nodos para los que S_i fish(n) == i .
• Si para dos nodos, i y j fish(n_i) != fish(n_j) entonces hay un arco entre i y j .
• El costo entre el nodo iy el nodo j es el time(n_i, n_j) o indefinido si el time(n_i, n_j) < distance(n_i, n_j) (es decir, la ubicación no puede alcanzarse antes de que el pez llegue allí, tal vez porque está al revés en el tiempo). Los arcos de este último tipo se pueden eliminar.
• Se deberá agregar un nodo adicional que represente la ubicación del jugador con arcos y costos para todos los otros nodos.

La solución de este problema daría como resultado una visita única a cada subconjunto de nodos (es decir, cada pez se obtiene una vez) para una ruta con un costo mínimo (es decir, tiempo mínimo para todos los peces).

El documento continúa para describir cómo la formulación anterior puede transformarse en un problema tradicional de viajero ambulante y posteriormente resolverse o aproximarse con las 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 del nodo es infinito! Esto puede aliviarse generando nodos hasta cierto horizonte de tiempo. Si t es el número de pasos de tiempo para generar nodos para f es el número de peces, entonces el tamaño del espacio del nodo será t * f . Un nodo en el tiempo j tendrá como máximo (f - 1) * (t - j) arcos de salida (ya que no puede retroceder en el tiempo ni a su propio subconjunto). El número total de arcos será del orden de t^2 * f^2 arcos. La estructura del arco probablemente puede ser arreglada, para aprovechar el hecho de que las rutas de los peces son eventualmente cíclicas. El pez repetirá su configuración una vez que el mínimo común denominador de la duración de sus ciclos, por lo que tal vez este hecho pueda ser utilizado.

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 difícil para NP ... pero es un enfoque para encontrar una solución óptima o acotada .