IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Логистика, (из точка A точку B)
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


Ребята, выручайте. Задача интересная, прикладная, но что-то я подвис с её решением.
Чтобы проще понять, что требуется, представьте себе, что у вас есть некая страна, в которой есть для простоты 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 городов, как в данном примере). Т.е. надо сделать общий алгоритм этих вычислений. И такая печаль, что у меня ни фига не получается в связи с описанными, как для меня, проблемами. Ребята, очень прошу помощи. Там есть ещё графическое продолжение, но хотя бы эту часть. Дальше я сам.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Большевик–концептуал
**

Группа: Пользователи
Сообщений: 132
Пол: Мужской
Реальное имя: Иван Левашев
Jabber: octagram@jabber.ru
Skype: i.levashew
QQ: 3152538431
WeChat
Ада: Сторонник
Embarcadero Delphi: Сторонник
Free Pascal: Разработчик
Turbo Pascal: Установлен

Репутация: -  0  +


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

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

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

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

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

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


--------------------
If you want to get to the top, you have to start at the bottom
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


Цитата(OCTAGRAM @ 20.12.2017 10:01) *

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

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



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

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 16.01.2018 14:19
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"