Алгоритм BFS - кратчайший путь по сетке с ограниченными шагами - PullRequest
Новая
       2

Алгоритм BFS - кратчайший путь по сетке с ограниченными шагами

0 голосов
/ 21 ноября 2010

Проблема в следующем: странник начинает с координат сетки (x, y) и хочет достичь координат (0,0).Из каждой точки сетки странник может пройти 8 шагов на север ИЛИ 3 шага на юг ИЛИ 5 шагов на восток ИЛИ 6 шагов на запад (8N / 3S / 5E / 6W).

Как найти кратчайший маршрут из (X,Y) - (0,0) с использованием поиска в ширину?

Уточнения:

  • Неограниченная сетка
  • Допускаются отрицательные координаты
  • Aдолжна использоваться очередь (связанный список или массив)
  • Нет препятствий

Ответы [ 4 ]

2 голосов
/ 21 ноября 2010

Алгоритм для этой проблемы будет:

Для каждой оси шагайте к ней, пока ваше положение на другой оси не станет 0.

псевдокод: 

while (x!=0) {
  if (x>0) x-=6;
  else x+=5;
}
while (y!=0) {
  if (y>0) y-=8;
  else y+=3;
}

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

1 голос
/ 05 января 2011

Вот мой ответ (действительно основанный на ответе jh), который использует очередь: 

//set x to start position
//set y to start position
do {
  if (x<0) Queue.Push(8N);
  if (x>0) Queue.Push(3S);
  if (y<0) Queue.Push(5E);
  if (y>0) Queue.Push(6W);
  while (!Queue.Empty())
  {
    Move(Queue.Pop());
  }
} while (x && y);

Он запутанный, но следует указаниям.

1 голос
/ 21 ноября 2010

Как отметил "thejh", поиск не нужен, но ваше назначение требует его.

Разумный подход -

  1. Анализ.Возможно ли все для произвольной (x, y) начальной позиции?Проверяя разрешенные ходы, вы видите, что они могут быть объединены для получения 1-шаговых горизонтальных и 1-шаговых вертикальных ходов, так что ответ на этот вопрос - да (для вашей руки предоставьте детали этого).

  2. Выясните, что такое «поиск в ширину».Википедия - ваш друг (хотя, если у вас есть доступ к университетской библиотеке, я действительно рекомендую старый 10101 * искусственный интеллект Патрика Генри Уинстона , это действительно хорошие, очень ясные объяснения).Попробуйте с более простой задачей.

  3. Выполните задачу назначения примерно так же.Спросите здесь, если вы столкнулись с какой-либо технической проблемой C ++.

Cheers & hth.,

0 голосов
/ 27 ноября 2010

Я собираюсь пойти дальше и ответить на свой вопрос для дальнейшего использования.

Psuedocode: 

while (true) {
    if (destination reached)
        break;
    addToQueue(go north);
    addToQueue(go south);
    addToQueue(go east);
    addToQueue(go west);
    getNextFromQueue;
}

Следует также отметить, что время выполнения этого приложения очень сильно увеличивается, очень быстро, поэтому проверьте это с небольшими значениями координат.Например, координаты (1,1) дают 7 уровней ширины и требуют 16384 итерации.

...