2

На Wiki есть некий псевдокод:

BFS(start_node, goal_node) {
  return BFS'({start_node}, ∅, goal_node);
}
BFS'(fringe, visited, goal_node) {
  if(fringe == ∅) {
    // Целевой узел не найден
    return false; 
  }
  if (goal_node ∈ fringe) {
    return true;
  }
  return BFS'({child | x ∈ fringe, child ∈ expand(x)} \ visited, visited ∪ fringe, goal_node);
}

Но в нем есть много непонятного, а именно последняя строчка возврата функции.

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

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

Как это работает?

  • Получаем новую вершину.;
  • Загоняем ее в функцию, помечаем черным цветом;
  • Проверяем смежные вершины и если они белые - кидаем в очередь;
  • Для каждого элемента запоминаем его родителя в отдельный массив родителей;
  • Далее крутим по кругу пока очередь не будет пустая;
  • После завершения функции запускаем функцию восстановления пути, которая восстанавливает путь реверсивно, начиная с конечной вершины и заканчивая начальной, с помощью массива с родителями.

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

4
  • а вы уверены что вам все кратчайшие пути нужны? Их может быть оочень много.
    – pavel
    29 сен 2016 в 17:02
  • @pavel суть в том что граф для задачи предоставлен и в нем всего-лишь 2 кратчайших пути, каждый длиной по 3 вершины. В общем это задания чисто для обучения, но что-то я никак не пойму как сделать это "прямыми руками", а не как у меня.
    – Telion
    29 сен 2016 в 17:07
  • динамика простейшая тогда... Но пути потом ещё восстанавливать
    – pavel
    29 сен 2016 в 17:08
  • @pavel вы не могли бы показать пример на каком-либо С-подобном языке или написать какие-либо наброски кода/псевдокода? Пройти по всем вершинам и пометить их в черный дело 5-ти минут, но отследить все пути и проверка на ответ как-то я не смог записать в рекурсивный вариант решения.
    – Telion
    29 сен 2016 в 17:12

1 ответ 1

1

Пишу алгоритм более простой для понимания.

Запускаете очередь из начальной точки. Val - массив расстояний от 1 точки до всех остальных. После этого вы должны запустить очередь от финишной клетки и идти только если Val[cur] == Val[new] + 1. Значение в тех клетках, которые мы не посетили, нужно выставить в бесконечность.

Теперь у нас есть клетки которые точно входят хотя бы в 1 оптимальный путь. Вам нужны сами пути, хотите рекурсией, можно и ей.

функция (параметр текущая клетка) --> набор путей
    для каждой соседней по стороне клетке
        если Val[cur] == Val[new] + 1
            то вызовём функцию с новой клеткой
            добавим в список путей всё что нам вернули, приписав нашу клетку в каждый

Запускать из начальной точки.

Важно, количество путей может расти экпоненциально (или близко к этому). Если вам нужно только число таких путей то используйте мемоизацию.

4
  • Очередь при окончании действия функции должна быть пустой иначе выхода не произойдет, вы предлагаете ее сохранить для прохода в обратную сторону? И что вы имеете ввиду под Val[cur] == Val[new] + 1, это поиск смежных вершин?
    – Telion
    29 сен 2016 в 17:29
  • нет. Вы же где-то храните массив не самой очереди, а расстояний от 1 точки к тем, до которых дошли. Кстати, не прерывайте очередь как только дошли до нужной вершины.
    – pavel
    29 сен 2016 в 17:30
  • Расстояния в плане между точками? Они все равны между собой. Расстояния от начальной к конечной нет. Пока что. Это если его знать можно запустить такой же проход только с вылетом выше этого значения. Я правильно понял?
    – Telion
    29 сен 2016 в 17:33
  • Окей, прочитал обновленный ответ. Вы предлагаете сделать массив с расстояниями от начальной точки к остальным, верно? Хм.. Это еще нужно придумать как его сделать.
    – Telion
    29 сен 2016 в 17:47

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.