Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
0 / 0 / 0
Регистрация: 21.04.2015
Сообщений: 7
1

Из пункта А в пункт Б самый быстрый путь

17.12.2017, 22:43. Показов 1451. Ответов 3

Ребята, выручайте. Задача интересная, прикладная, но что-то я подвис с её решением.
Чтобы проще понять, что требуется, представьте себе, что у вас есть некая страна, в которой есть для простоты 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 городов, как в данном примере). Т.е. надо сделать общий алгоритм этих вычислений. И такая печаль, что у меня ни фига не получается в связи с описанными, как для меня, проблемами. Ребята, очень прошу помощи. Там есть ещё графическое продолжение, но хотя бы эту часть. Дальше я сам.
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.12.2017, 22:43
Ответы с готовыми решениями:

Самый быстрый путь изучения XSLT
Подскажите, пожалуйста, учебные материалы (в первую очередь на русском) для быстрого освоения...

Сколько времени потребуется первому пешеходу на путь из пункта А в пункт В?
Два пешехода выходят одновременно навстречу друг другу из пунктов А и В и встречаются через 3 часа....

Равномерное ДВИЖЕНИЕ тела из пункта А в пункт В движется велосипедист с постоянной скоростью V через 0.5 часа после его старта из пункта а стартовал в
Равномерное ДВИЖЕНИЕ тела из пункта А в пункт В движется велосипедист с постоянной скоростью V...

Задачка: добраться из пункта A в пункт B
Друзья, помогите с задачей. У нас есть поле размера N. Пользователь также вбивает координаты машины...

3
Заклинатель змей
609 / 507 / 213
Регистрация: 30.04.2016
Сообщений: 2,417
17.12.2017, 23:27 2
Лучший ответ Сообщение было отмечено cyberip как решение

Решение

cyberip, описанная задача представляет собой кратчайший обход взвешенного графа. Алгоритм Дейкстры прекрасно подойдёт, только надо будет правильно читать матрицу связей
1
0 / 0 / 0
Регистрация: 21.04.2015
Сообщений: 7
17.12.2017, 23:36  [ТС] 3
в этом и проблема как правильно считать матрицу
0
Заклинатель змей
609 / 507 / 213
Регистрация: 30.04.2016
Сообщений: 2,417
22.12.2017, 19:57 4
cyberip, как двумерную матрицу связи для каждого элемента, например
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.12.2017, 19:57

Самый быстрый сервер
Здравствуйте, подскажите пожалуйста. где можно найти исходники самого быстрого сервера...

Самый быстрый алгоритм Факториала
Всем привет ! Как можно реализовать факториал за log(n) . Помогите плиз ! Знаю ,что можно рекурсией...

самый быстрый МК общего применения
От МК требуется, чтобы он очень быстро считал. Из периферии нужны только порты ввода/вывода и USB....

Какой самый быстрый архиватор ?
Какой самый быстрый архиватор и распаковщик ?:help:


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.