Помощь - Поиск - Пользователи - Календарь
Полная версия: Логистика
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
ipconnect
Ребята, выручайте. Задача интересная, прикладная, но что-то я подвис с её решением.
Чтобы проще понять, что требуется, представьте себе, что у вас есть некая страна, в которой есть для простоты 9 городов. Каждый город для удобства обозначен уникальной цифрой от 1 до 9. Между городами есть дороги (не между всеми), которые имеют определённую протяжённость, заранее известную. По некоторым дорогам можно проехать только в одну сторону, по другим - в обе. В общем всё это вышеописанное дело можно задать вот таким двумерным массивом чисел (номер строки - точка отправления, номер столбца - точка прибытия):
00 01--02-03-04--05-06--07-08-09
01(-1)(10)(-1)(11)(15)(-1)(-1)(-1)(-1)
02(-1)(-1)(21)(-1)(12)(-1)(-1)(-1)(-1)
03(-1)(21)(-1)(-1)(-1)(-1)(-1)(-1)(-1)
04(-1)(-1)(-1)(-1)(18)(19)(-1)(-1)(-1)
05(-1)(-1)(-1)(-1)(-1)(-1)(17)(-1)(-1)
06(-1)(-1)(-1)(-1)(-1)(-1)(-1)(14)(13)
07(-1)(-1)(-1)(-1)(-1)(-1)(-1)(-1)(20)
08(-1)(-1)(-1)(-1)(-1)(-1)(-1)(-1)(16)
09(-1)(-1)(-1)(-1)(-1)(-1)(-1)(-1)(-1)
В данной табличке неотрицательные цифры - это и есть расстояния между городами (может быть и ноль), а (-1) это признак того, что между этими городами в данном направлении дорога отсутствует. К примеру, между городами 1 и 2 автомобилю необходимо проехать 10 км, между городами 1 и 3 прямой дороги нет, а между городами 2 и 3 дорога в обе стороны длиной 21 км в одну сторону. Вот такие исходные данные. А вот в чём задача, которая вызывает у меня проблему, я сейчас попробую описать. У вас есть автомобиль, который должен ехать из пункта А в пункт Б. Он перемещается по одному из возможных путей, заданных в массиве. Необходимо подсчитать все возможные длины путей из точки А в точку Б, запомнив сам путь перемещения (к примеру из точки 1 в точку 9 пути 1-2-5-7-9 или 1-4-6-8-9 и т.п.) и его длину. Дальше надо сравнить эти маршруты и найти наиболее короткий (ну, это легко). Проблема вторая если один из участков между городами упирается в город, путь из которого возможен только назад в точку отправления (участок между городами 2 и 3), необходимо учесть и этот участок возможного маршрута (т.е. нарушается логика увеличения цикла, так как надо возвращаться назад).

В итоге в данном примере возможные пути выглядят следующим образом, если пункт А - это 1, а пункт Б -9:
1-2-3-2-5-7-9 (длина пути 101 км)
1-2-5-7-9 (длина пути 59 км)
1-4-5-7-9 (длина пути 56 км)
1-4-6-8-9 (длина пути 60 км)
1-4-6-9 (длина пути 43 км)
1-5-7-9 (длина пути 52 км)
Отсюда минимальное расстояние между точками А (1) и Б (9) равняется 43 км и это расстояние соответствует маршруту 1-4-6-9... Но все эти цифры и выводы надо получить программно при том, что количество городов задаётся произвольным целым числом от 1 и до хотя бы 100 (а не 9 городов, как в данном примере). Т.е. надо сделать общий алгоритм этих вычислений. И такая печаль, что у меня ни фига не получается в связи с описанными, как для меня, проблемами. Ребята, очень прошу помощи. Там есть ещё графическое продолжение, но хотя бы эту часть. Дальше я сам.
OCTAGRAM
Если хранить разные пути не требуется, то алгоритм может быть такой:

Задаётся переменная-ограничитель длины пути, изначально 0.
Для городов задаётся массив из расстояний, за которые они достижимы, а также логический флаг, достигнуты ли они в текущей итерации.
В каждой итерации для каждого достигнутого города смотрим, в какие города можно попасть, и как придётся увеличить ограничитель для этого. Например, если текущий ограничитель 5км (где-то есть достигнутый город, до которого минимум 5км), а до текущего рассматриваемого города минимум 2км, а из него 4км до ещё одного города, то новый ограничитель — 6км. По всем итерациям выбирается минимальный новый ограничитель, он может совпадать с существующим, и новый город помечается как достигнутый, и в массив для него проставляется расстояние.
Итерации повторяются до тех пор, пока не достигнут желаемый город.

После этого делается обратный ход: начиная от желаемого города, пытаемся понять, как можно было попасть в очередной город, обратно к началу. Либо можно ранее при проставлении достижимости также сохранять город, из которого удаётся попасть таким путём.

Если пути сохранять требуется, тогда и проще, и сложнее. Можно сделать и поиском в ширину (BFS), и поиском в глубину (DFS). Поиском в глубину несколько проще, так как он реализуем рекурсией.

Контекст состоит из массива (лучше сказать, вектора) для пройденного маршрута и пройденного пути. Эти контексты складываются в другие вектора. Нужен вектор для законченных маршрутов и вектор незаконченных маршрутов. Если поиск в глубину реализован рекурсией, то первого вектора нет, а вместо него контексты на системном стеке.

В каждой итерации берётся рабочий контекст, и из него производятся другие рабочие контексты, а исходный контекст либо удаляется, либо переносится в законченные. Если поиск в ширину, то новые рабочие контексты заносятся в вектор. Если поиск в глубину рекурсией, то делается рекурсивный вызов. Можно, конечно, поиск в глубину без рекурсии, то есть, новые контексты заносятся в вектор незаконченных маршрутов с того же конца, с которого и извлекаются. При поиске в ширину тоже могут быть вариации: можно делать обработку в порядке очереди (добавляем в один конец, извлекаем с другого конца), и тогда можно ожидать, что первым появится маршрут из наименьшего количества городов, а можно поддерживать сортировку и постоянно извлекать самый короткий незаконченный маршрут.
ipconnect
Цитата(OCTAGRAM @ 20.12.2017 10:01) *

Если хранить разные пути не требуется, то алгоритм может быть такой:

Задаётся переменная-ограничитель длины пути, изначально 0.
Для городов задаётся массив из расстояний, за которые они достижимы, а также логический флаг, достигнуты ли они в текущей итерации.
В каждой итерации для каждого достигнутого города смотрим, в какие города можно попасть, и как придётся увеличить ограничитель для этого. Например, если текущий ограничитель 5км (где-то есть достигнутый город, до которого минимум 5км), а до текущего рассматриваемого города минимум 2км, а из него 4км до ещё одного города, то новый ограничитель — 6км. По всем итерациям выбирается минимальный новый ограничитель, он может совпадать с существующим, и новый город помечается как достигнутый, и в массив для него проставляется расстояние



Спасибо. На другом форуме подсказали хорошую идею - Алгоритм Дейкстры. Но там надо было некоторые нюансы докрутить. В общем задачу решил. Правда не самый общий случай, но впрочем удобоваримо.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.