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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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