Как найти кратчайший путь между 100 движущимися целями? (Живая демонстрация включена.)

89

Задний план

Это изображение иллюстрирует проблему: square_grid_with_arrows_giving_directions

Я могу контролировать красный круг. Цели - синие треугольники. Черные стрелки указывают направление, в котором будут двигаться цели.

Я хочу собрать все мишени за минимальное количество шагов.

Каждый ход я должен делать 1 шаг влево / вправо / вверх или вниз.

Каждый ход мишени также перемещаются на 1 шаг в соответствии с указаниями на доске.

Демо

Я разместил игровую демонстрацию проблемы здесь, в Google appengine .

Мне было бы очень интересно, сможет ли кто-нибудь побить целевой показатель, поскольку это покажет, что мой текущий алгоритм не оптимален. (Если вам это удастся, следует распечатать поздравительное сообщение!)

Проблема

Мой текущий алгоритм очень плохо масштабируется с количеством целей. Время растет экспоненциально и для 16 рыбок уже несколько секунд.

Я хотел бы вычислить ответ для доски размером 32 * 32 и со 100 движущимися мишенями.

Вопрос

Каков эффективный алгоритм (в идеале на Javascript) для вычисления минимального количества шагов для сбора всех целей?

Что я пробовал

Мой нынешний подход основан на воспоминаниях, но он очень медленный, и я не знаю, всегда ли он будет давать лучшее решение.

Я решаю подзадачу «каково минимальное количество шагов, чтобы собрать данный набор целей и попасть в конкретную цель?».

Подзадача решается рекурсивно, проверяя каждый выбор предыдущей цели, которую нужно посетить. Я предполагаю, что всегда оптимально собрать предыдущее подмножество целей как можно быстрее, а затем как можно быстрее перейти от позиции, в которой вы закончили, к текущей цели (хотя я не знаю, является ли это допустимым предположением).

Это приводит к вычислению n * 2 ^ 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;
}

Что я рассмотрел

Вот некоторые варианты, о которых я задумался:

  1. Кеширование промежуточных результатов. Расчет расстояния повторяет множество симуляций, и промежуточные результаты можно кэшировать.
    Однако я не думаю, что это остановит экспоненциальную сложность.

  2. Алгоритм поиска A *, хотя мне не ясно, какой будет подходящая допустимая эвристика и насколько она эффективна на практике.

  3. Изучите хорошие алгоритмы задачи коммивояжера и посмотрите, применимы ли они к этой проблеме.

  4. Пытаться доказать, что проблема NP-сложна и, следовательно, неразумно искать для нее оптимальный ответ.

javascript algorithm graph-theory Питер де Риваз
источник
1
Я бы выбрал №4, а затем №3: с достаточно большими досками он довольно хорошо имитирует TSP.
John Dvorak
2
Насколько мне известно, TSP NP-сложен как с евклидовой метрикой, так и с манхэттенской метрикой (квадратная сетка).
John Dvorak
1
Если вы сделаете это простым поиском по дереву, да, он будет экспоненциальным. Однако, если вы можете найти приличную эвристику на каждом этапе, она может быть не совсем оптимальной, но может быть очень хорошей. Один из возможных вариантов эвристики: глядя на текущий набор рыб, к какой из них можно добраться быстрее всего? Вторичная эвристика может быть такой: до каких 2 рыб я смогу добраться быстрее всего?
Mike Dunlavey
2
@MikeDunlavey, который соответствовал бы жадному алгоритму TSP, и он очень хорошо работает на практике. Поймать ближайшую рыбу кажется хорошей идеей
Джон Дворжак
1
+1 за один из лучших вопросов, которые я видел за последнее время, как по содержанию, так и по структуре.
surfitscrollit

Ответы:

24

Вы искали литературу? Я нашел эти документы, которые, кажется, анализируют вашу проблему:

ОБНОВЛЕНИЕ 1:

Две вышеуказанные статьи, кажется, сосредоточены на линейном движении евклидовой метрики.

Uldall
источник
Спасибо - я не видел этих бумаг, но они выглядят очень актуальными. Я посмотрю, смогу ли я адаптировать генетический алгоритм для работы в моем случае, и сравню его с результатами метода грубой силы.
Питер де Риваз
13

Жадный метод

Один из подходов, предложенных в комментариях, - сначала перейти к ближайшей цели.

Я мириться версию демо , которая включает в себя стоимость рассчитывается по этому жадному методу здесь .

Код такой:

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

Для 10 целей это примерно вдвое больше оптимального расстояния, но иногда намного больше (например, * 4), а иногда даже достигает оптимального.

Этот подход очень эффективен, поэтому я могу позволить себе несколько циклов, чтобы улучшить ответ.

Затем я подумываю об использовании методов колонии муравьев, чтобы увидеть, могут ли они эффективно исследовать пространство решений.

Метод колонии муравьев

Метод Ant колонии , кажется, работает замечательный хорошо для этой задачи. Ссылка в этом ответе теперь сравнивает результаты при использовании как жадного метода, так и метода муравьиной колонии.

Идея состоит в том, что муравьи выбирают свой путь вероятностно в зависимости от текущего уровня феромона. После каждых 10 испытаний мы вносим дополнительный феромон по кратчайшему пути, который они нашли.

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

Полученные результаты

Этот метод колонии муравьев с использованием 100 повторов 10 муравьев по-прежнему очень быстр (37 мс для 16 целей по сравнению с 3700 мс для исчерпывающего поиска) и кажется очень точным.

В таблице ниже показаны результаты 10 испытаний с 16 мишенями:

   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

Муравьиный метод кажется значительно лучше жадного и часто очень близким к оптимальному.

Питер де Риваз
источник
Ницца. Возможно, у вас еще нет оптимальных результатов от исчерпывающего поиска (или, возможно, никогда из-за его непреодолимости!), Но было бы интересно посмотреть, как колония муравьев масштабируется с размером доски (32x32) с тем же количеством целей.
timxyz
8

Задача может быть представлена ​​в терминах обобщенной задачи коммивояжера, а затем преобразована в обычную задачу коммивояжера. Это хорошо изученная проблема. Возможно, что наиболее эффективные решения проблемы OP не более эффективны, чем решения TSP, но ни в коем случае не уверены (я, вероятно, не могу воспользоваться некоторыми аспектами структуры проблем OP, которые позволили бы быстрее решить , например, его цикличность). В любом случае, это хорошая отправная точка.

Из К. Нун и Дж. Бина, Эффективное преобразование обобщенной задачи коммивояжера :

Обобщенная задача коммивояжера (GTSP) является полезной моделью для решения проблем , связанных с отбора и последовательности. Асимметричный вариант задачи задается на ориентированном графе с узлами N, соединяющими дуги A и вектор соответствующих стоимостей дуг c. Узлы предварительно сгруппированы в m взаимоисключающих и исчерпывающих наборов узлов. Соединительные дуги определяются только между узлами, принадлежащими разным наборам, то есть внутримножественных дуг нет. Каждая заданная дуга имеет соответствующую неотрицательную стоимость. GTSP можно сформулировать как задачу поиска цикла m-дуги с минимальной стоимостью, который включает ровно один узел из каждого набора узлов .

Для проблемы OP:

  • Каждый член N- это определенная рыба в определенное время. Представьте это как (x, y, t), где (x, y)- координата сетки, а tвремя, в которое рыба будет находиться в этой координате. Для самой левой рыбы в примере с OP первые несколько из них (на основе 1): (3, 9, 1), (4, 9, 2), (5, 9, 3)когда рыба движется вправо.
  • Для любого члена N позвольте fish(n_i)вернуть идентификатор рыбы, представленной узлом. Для любых двух членов N мы можем вычислить manhattan(n_i, n_j)манхэттенское расстояние между двумя узлами и time(n_i, n_j) для временного смещения между узлами.
  • Количество непересекающихся подмножеств m равно количеству рыбок. Непересекающееся подмножество S_iбудет состоять только из узлов, для которых fish(n) == i.
  • Если для двух узлов, iа j fish(n_i) != fish(n_j)то есть дуга между iи j.
  • Стоимость между узлом i и узлом j равна time(n_i, n_j)или не определена, если time(n_i, n_j) < distance(n_i, n_j)(т. Е. Место не может быть достигнуто до того, как рыба доберется туда, возможно, потому, что оно идет назад во времени). Дуги этого последнего типа можно удалить.
  • Необходимо добавить дополнительный узел, представляющий местоположение игрока с дугами и стоимостью для всех остальных узлов.

Решение этой проблемы привело бы к однократному посещению каждого подмножества узлов (т.е. каждая рыба получена один раз) для пути с минимальными затратами (т.е. минимальным временем для получения всей рыбы).

В статье описывается, как приведенная выше формулировка может быть преобразована в традиционную задачу коммивояжера и впоследствии решена или приближена с помощью существующих методов. Я не читал через детали , но еще один документ , который делает это таким образом , что провозглашается быть эффективным является этот один .

Есть очевидные проблемы со сложностью. В частности, пространство узлов бесконечно! Этого можно избежать, создавая узлы только до определенного временного горизонта. Если t- количество временных шагов для генерации узлов, и f- количество рыб, то размер пространства узлов будет равен t * f. Узел во время jбудет иметь максимум (f - 1) * (t - j)исходящих дуг (так как он не может перемещаться назад во времени или к своему собственному подмножеству). Общее количество дуг будет в порядке t^2 * f^2дуг. Дуговую структуру, вероятно, можно привести в порядок, чтобы воспользоваться тем фактом, что траектории рыбы в конечном итоге являются цикличными. Рыба будет повторять свою конфигурацию один раз для каждого наименьшего общего знаменателя длины их цикла, так что, возможно, этот факт можно использовать.

Я недостаточно знаю о TSP, чтобы сказать, возможно ли это или нет, и я не думаю, что это означает, что опубликованная проблема обязательно NP-трудная ... но это один из подходов к поиску оптимального или ограниченного решения .

Timxyz
источник
Спасибо, это ново для меня и очень интересно. Я думаю, что смогу использовать это преобразование в сочетании с алгоритмом Кристофидеса, чтобы эффективно найти решение с коэффициентом приближения 3/2 от оптимального. Если у меня все заработает, я добавлю созданные маршруты на демонстрационную страницу.
Питер де Риваз,
Ах, я думаю, что есть проблема с моим планом в том, что, хотя моя первоначальная проблема - это полный граф, удовлетворяющий соответствующему неравенству по метрике, описанное преобразование приводит к неполному графу, и поэтому алгоритм Кристофидеса больше не применяется. В любом случае спасибо за интересную перспективу.
Питер де Риваз
Да, я забыл упомянуть, что неравенство треугольника больше не выполняется. Однако это хорошая отправная точка для эвристических решений и более общих приближений.
timxyz
1

Я думаю, что другой подход был бы:

Цитата из Википедии:

В математике диаграмма Вороного - это способ разделения пространства на несколько областей. Набор точек (называемых семенами, сайтами или генераторами) указывается заранее, и для каждого семени будет соответствующая область, состоящая из всех точек, более близких к этому семени, чем к любому другому.

Итак, вы выбираете цель, проходите по ней несколько шагов и устанавливаете там начальную точку. Проделайте то же самое со всеми другими целями, и вы получите диаграмму Ворони. В зависимости от того, в какой области вы находитесь, вы переходите к ее исходной точке. Виола, у тебя первая рыба. Теперь повторяйте этот шаг, пока не выловите их все.

Юрген Штюрмер
источник