Como posso encontrar o caminho mais curto entre 100 alvos móveis? (Demonstração ao vivo incluída).

fundo

Esta imagem ilustra o problema:

Eu posso controlar o círculo vermelho. Os alvos são os triângulos azuis. As setas pretas indicam a direção em que os alvos se moverão.

Quero coletar todos os alvos no número mínimo de etapas.

Cada curva devo mover 1 passo para a esquerda / direita / cima ou para baixo.

Cada vez, os alvos também se moverão 1 passo de acordo com as instruções mostradas no tabuleiro.

Demo

Eu coloquei uma demonstração jogável do problema aqui no Google appengine .

Eu estaria muito interessado se alguém pudesse bater a pontuação desejada, pois isso mostraria que meu algoritmo atual está abaixo do ideal. (Uma mensagem de parabéns deve ser impressa se você conseguir isso!)

Problema

Meu algoritmo atual escala muito mal com o número de alvos. O tempo aumenta exponencialmente e para 16 peixes já leva vários segundos.

Eu gostaria de calcular a resposta para tamanhos de placa de 32 * 32 e com 100 alvos móveis.

Questão

O que é um algoritmo eficiente (idealmente em Javascript) para calcular o número mínimo de etapas para coletar todos os alvos?

O que eu tentei

Minha abordagem atual é baseada no memoisation, mas é muito lenta e não sei se sempre gerará a melhor solução.

Eu resolvo o subproblema de "qual é o número mínimo de etapas para coletar um determinado conjunto de alvos e terminar em um determinado alvo?".

O subproblema é resolvido recursivamente examinando cada escolha do destino anterior que foi visitado. Presumo que seja sempre ideal coletar o subconjunto anterior de alvos o mais rápido possível e, em seguida, mover da posição em que você acabou para o alvo atual o mais rápido possível (embora eu não saiba se essa é uma suposição válida).

Isso resulta em n * 2 ^ n estados a serem calculados, que crescem muito rapidamente.

O código atual é mostrado abaixo:

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;
}

O que eu considerei

Algumas opções que me perguntam são:

1. Cache de resultados intermediários. O cálculo da distância repete muitas simulações e os resultados intermediários podem ser armazenados em cache.
   No entanto, não acho que isso impediria de ter complexidade exponencial.

2. Um algoritmo de busca A *, embora não esteja claro para mim qual seria uma heurística admissível apropriada e quão eficaz isso seria na prática.

3. Investigar bons algoritmos para o problema do caixeiro-viajante e ver se eles se aplicam a este problema.

4. Tentar provar que o problema é NP-difícil e, portanto, irracional, buscar uma resposta ótima para ele.

Você pesquisou a literatura? Encontrei estes papéis que parecem analisar seu problema:

• "Rastreamento de alvos móveis e o problema do caixeiro viajante não estacionário": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.85.9940

• "O problema do caixeiro viajante com alvo móvel": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.6403

ATUALIZAÇÃO 1:

Os dois artigos acima parecem se concentrar no movimento linear para a métrica euclidiana.

Método ganancioso

Uma abordagem sugerida nos comentários é ir primeiro ao alvo mais próximo.

Eu coloquei uma versão da demonstração que inclui o custo calculado por meio desse método ganancioso aqui .

O código é:

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 alvos, é cerca de duas vezes a distância ideal, mas às vezes muito mais (por exemplo, * 4) e ocasionalmente até atinge o ideal.

Essa abordagem é muito eficiente, então posso pagar alguns ciclos para melhorar a resposta.

Em seguida, estou pensando em usar métodos de colônia de formigas para ver se eles podem explorar o espaço de solução de forma eficaz.

Método de colônia de formigas

Um método de colônia de formigas parece funcionar muito bem para esse problema. O link nesta resposta agora compara os resultados ao usar o método da colônia gananciosa e da colônia de formigas.

A ideia é que as formigas escolham sua rota probabilisticamente com base no nível atual de feromônio. A cada 10 tentativas, depositamos feromônios adicionais ao longo da trilha mais curta que eles encontraram.

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 colônia de formigas usando 100 repetições de 10 formigas ainda é muito rápido (37ms para 16 alvos em comparação com 3700ms para a busca exaustiva) e parece muito preciso.

A tabela abaixo mostra os resultados de 10 testes usando 16 alvos:

   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

O método das formigas parece significativamente melhor do que o guloso e muitas vezes está muito próximo do ideal.

O problema pode ser representado em termos do Problema do Caixeiro Viajante Generalizado e então convertido em um Problema do Caixeiro Viajante convencional. Este é um problema bem estudado. É possível que as soluções mais eficientes para o problema do OP não sejam mais eficientes do que as soluções para o TSP, mas de forma alguma certas (provavelmente estou deixando de aproveitar alguns aspectos da estrutura do problema do OP que permitiriam uma solução mais rápida , como sua natureza cíclica). De qualquer forma, é um bom ponto de partida.

De C. Noon & J.Bean, Uma transformação eficiente do problema do caixeiro viajante generalizado :

O Problema Generalizado do Caixeiro Viajante (GTSP) é um modelo útil para problemas envolvendo decisões de seleção e sequência. A versão assimétrica do problema é definida em um grafo direcionado com nós N, conectando os arcos A e um vetor de custos de arco correspondentes c. Os nós são pré-agrupados em conjuntos de nós mutuamente exclusivos e exaustivos. Os arcos de conexão são definidos apenas entre nós pertencentes a conjuntos diferentes, ou seja, não há arcos intraset. Cada arco definido tem um custo não negativo correspondente. O GTSP pode ser definido como o problema de encontrar um ciclo de arco m de custo mínimo que inclui exatamente um nó de cada conjunto de nós .

Para o problema do OP:

• Cada membro de N é a localização de um determinado peixe em um determinado momento. Representa isso como (x, y, t), onde (x, y)é uma coordenada de grade e té o momento em que o peixe estará nesta coordenada. Para o peixe mais à esquerda no exemplo do OP, os primeiros (baseados em 1) são: (3, 9, 1), (4, 9, 2), (5, 9, 3)conforme o peixe se move para a direita.
• Para qualquer membro de N let fish(n_i) retornar o ID do peixe representado pelo nó. Para quaisquer dois membros de N, podemos calcular manhattan(n_i, n_j)a distância de manhattan entre os dois nós e time(n_i, n_j) para o deslocamento de tempo entre os nós.
• O número de subconjuntos disjuntos m é igual ao número de peixes. O subconjunto disjunto S_iconsistirá apenas nos nós para os quais fish(n) == i.
• Se por dois nós iej fish(n_i) != fish(n_j) , em seguida, há um arco entre ie j.
• O custo entre o nó i e o nó j é time(n_i, n_j) , ou indefinido se time(n_i, n_j) < distance(n_i, n_j)(ou seja, a localização não pode ser alcançada antes que o peixe chegue lá, talvez porque esteja para trás no tempo). Os arcos deste último tipo podem ser removidos.
• Um nó extra precisará ser adicionado representando a localização do jogador com arcos e custos para todos os outros nós.

Resolver este problema resultaria em uma única visita a cada subconjunto de nós (ou seja, cada peixe é obtido uma vez) para um caminho com custo mínimo (ou seja, tempo mínimo para todos os peixes serem obtidos).

O artigo segue descrevendo como a formulação acima pode ser transformada em um problema tradicional do caixeiro viajante e, subsequentemente, resolvida ou aproximada com as técnicas existentes. Não li os detalhes, mas outro artigo que faz isso de uma forma que proclama ser eficiente é este .

Existem problemas óbvios com a complexidade. Em particular, o espaço do nó é infinito! Isso pode ser aliviado gerando nós apenas até um determinado horizonte de tempo. Se tfor o número de passos de tempo para gerar nós e ffor o número de peixes, então o tamanho do espaço do nó será t * f. Um nó por vez jterá no máximo (f - 1) * (t - j)arcos de saída (já que ele não pode voltar no tempo ou para seu próprio subconjunto). O número total de arcos será na ordem dos t^2 * f^2arcos. A estrutura do arco provavelmente pode ser arrumada, para aproveitar o fato de que os caminhos dos peixes são eventualmente cíclicos. Os peixes repetirão sua configuração uma vez a cada mínimo denominador comum de sua duração de ciclo, então talvez este fato possa ser usado.

Não sei o suficiente sobre o TSP para dizer se isso é viável ou não, e não acho que isso significa que o problema postado é necessariamente NP-difícil ... mas é uma abordagem para encontrar uma solução ótima ou limitada .

Acho que outra abordagem seria:

• calcular o caminho dos alvos - preditivo.
• do que usar diagramas de Voronoi

Citar wikipedia:

Em matemática, um diagrama de Voronoi é uma maneira de dividir o espaço em várias regiões. Um conjunto de pontos (chamados sementes, locais ou geradores) é especificado de antemão e para cada semente haverá uma região correspondente que consiste em todos os pontos mais próximos daquela semente do que de qualquer outra.

Então, você escolhe um alvo, segue seu caminho por alguns passos e define um ponto de semente ali. Faça isso com todos os outros alvos também e você obterá um diagrama de voroni. Dependendo de qual área você está, você se move para o ponto de origem dela. Viola, você pegou o primeiro peixe. Agora repita este passo até que você tenha pensado em todos eles.