Выбрать дату в календареВыбрать дату в календаре

Страницы: 1
Поиск кратчайшего пути с пересадками, Как согласовать виды транспорта в узлах?
 
Цитата
MCH написал:
пересадки в городах г1а-г1п
тогда, как без дополнительной аббревиатуры учесть направление дальнейшего движения?
Например, если из узла Г1 есть связи с узлами Г2 и Г3, то описав пересадку в Г1, как Г1А - Г1П, связать эту пересадку с тем куда дальше пойдет движение в Г2 или в Г3, ведь веса связей описывающих пересадку могут различаться в зависимости от того в какой пункт дальше двигаемся. Т.е., будет две связи  Г1А - Г1П и два веса -- один в направлении Г2, а другой в Г3. Алгоритм же их не различит... и выберет минимальный... что может быть не правильно...
или я опять чего-то недопонимаю.... :(

P.S. В приложенном мной примере, я пытался решить эту проблему выразив связь между узлами суммой весов пересадки и связи между узлами, т.е. в проекции на ваши объяснения получалось следующее: (Г1А - Г1П) + (Г1П - Г2П) - сумма двух связей. В таком случае вес пересадки связывался с направлением движения. Но мне не удалось прикрутить сопряжение транспортов в связях.
Самому уже становиться смешно -- сначала не мог увязать виды транспорта, теперь не увязываются пересадки...:)

P.S.2 В общем, скомбинировав ваше предложение (добавление аббревиатуры транспорта к названию узла) и свой подход (суммирование веса пересадки с весом связи между узлами), вроде получилось, пока, согласовать в т.ч. и связь пересадок с следующим узлом. Прогнал пару раз через "Поиск решения", в обоих случаях и пересадки с узлами и виды транспорта оказались согласованными. Погоняю ещё, для разных случаев, посмотрю будут ли ошибки...
Изменено: Vl Vl - 19.10.2020 20:15:45
Поиск кратчайшего пути с пересадками, Как согласовать виды транспорта в узлах?
 
Что-то меня опять заклинило...
Цитата
MCH написал:
При этом в графе должно быть указано, что не возможно из разных городов П перемещаться в разные города А, а можно только с помощью пересадки.
в первом посте об этом писал, как прописать невозможность перехода без пересадки? добавить дополнительные идентификаторы к названию узлов? для примера, есть узлы Г1, Г2 и т.д. и несколько видов транспорта, связи связи между узлами будут:
Г1А - Г2А  - для транспорта А
Г1Б - Г2Б  - для транспорта Б
Г1В - Г2В  - для транспорта В
в Г2 возможны пересадки (связи):
Г2А - Г2Б
Г2А - Г2В
Г2А - Г2В
Г2Б - Г2А
Г2Б - Г2Б
...
т.е. в алгоритме поиска необходимо кроме суммирования весов связей реализовать их увязку.
А как приведенный макрос это поймет и выберет нужное? или как ему это указать?
Спасибо.
Поиск кратчайшего пути с пересадками, Как согласовать виды транспорта в узлах?
 
MCH, благодарю за созданный пример с решением. Для меня в настоящее время решение макросом сложновато, ориентируюсь на более простые (формульные) в которых могу разобраться и использовать в внося модификации и капитально переделывая.
***

P.S.
Всё понял...
Пост удаляю... то что наваял вчера под вечер.
И как это я сам раньше не додумался... :
Цитата
MCH написал:
для этого введя вершины Город1П, Город1А и т.д.где ребро Город1П-Город1А будет являться пересадкой
MCH,ещё раз благодарю.. эта фраза не давала покоя, а потом осенило (то что выделено) - нужно просто изменить названия узлов добавив к ним обозначение видов связей и условий их смены.
В приведенном мной примере все возможные связи и их комбинации уже сформированы, но разнесены по разным колонками - в одних название узлов в других названия связей и т.д. - а надо было их не разделять, а сцепить в одно название и все бы сошлось...
Сейчас понимаю, что вам достаточно было-бы написать приведенную цитату, чутка акцентировав выделенное для того чтобы стало понятно. Но за макрос отдельное спасибо.
Теперь эту задачку смогу и "Поиском решения" реализовать.
Изменено: Vl Vl - 16.10.2020 09:23:08
Поиск кратчайшего пути с пересадками, Как согласовать виды транспорта в узлах?
 
Знаком (видел) с вашим макросом. и согласен, что если связей много то лучше макросом решать - скорость будет другая. Но с макросами я не очень дружен, не часто приходится сталкиваться. С простеньким мог бы разобраться.
Цитата
MCH написал:
можно прописать пересадки, или ограничить их при задании графа, тогда будут учитываться еще и виды транспорта
В целом, для универсального решения, да - можно было бы прикрутить разных ограничений и условий: ограничения по количеству пересадок, согласованность связей и пересадок по видам транспорта, различные ограничения по времени (пути, весу ...) и пр. Но сейчас нужно что-то попроще.
Поэтому и вопрошаю к сообществу, как прописать дополнительное условие в Поиск решения. Как писал в своем посте, пока только получается нарваться на ошибки. печалька.

Насчет алгоритма, которым решается задача, не скажу - какой там алгоритм у Поиска решения....
А так, да, задача чисто графовая.
По самой задаче - количество вершин, возможно до 30-ти, а связей вряд ли будет больше нескольких сотен. Поэтому "Поиска решений" вполне достаточно, а если и больше 200 (по ограничению), то можно прикрутить OpenSolver. Кроме этого и самому, на будущее неплохо бы понять, как подобное реализовать в Экселе по возможности без макросов.
Поиск кратчайшего пути с пересадками, Как согласовать виды транспорта в узлах?
 
Приветствую!
Прошу Вашей помощи в решении задачки.... (вот взялся на свою голову:) )
Посредством надстройки "Поиск решения" пытаюсь в задачу по поиску кратчайшего пути добавить ещё одно условие - согласование различных видов транспорта при выборе связей между узлами. Если этого не учитывать, то выбор пути происходит только по кратчайшему времени (расстоянию), что не правильно.

Для решения задачи использовал подход изложенный на сайте (Пример). Понравилась организация исходных данных.

Из-а ограничений в 100 КБ порезал и поудалял все что мог в файле (в т.ч. и некоторые формулы) и все равно получается больше, поэтому прикладываю в архиве. Оставлены уже готовые связи с их весом.

О содержании файла:
В колонках J и K - все комбинации связей между узлами с учетом видом транспорта и пересадок. В колонках О и Р - выборка, те связи между узлами, что имеют вес и участвуют в дальнейшем решении (следующая колонка - Время - дается суммарное время с учетом пересадки). В колонках: Tij - показана пересадка между транспортом (П - поезд, А - автобус, В - водный, буква "о" обозначает остановку без пересадки), Tj - транспорт, который связывает узлы, ΣT - для наглядности, т.е. если между узлами стоит, например, а2 - а3  ПА + А  - значит в узле а2 предусмотрена пересадка с Поезда на Автобус и дальше в пункт а3 едем на автобусе.

Надо, чтобы при выборе связей (колонка V = 1) учитывался вид транспорта на котором приехал в соответствующий узел. В последней колонке (АВ = Транспорт), как пример приведено решение, в котором первые 3-и строки правильно подобраны (из а1 выезжаем на А, приехав в а3 пересаживаемся на П (АП), дальше в а4 едем на П, в а4 происходит остановка П (оП) без смены транспорта и в а6 добираемся на П. А вот в 4-й строке результат не правильный (транспорт не согласован) - поскольку в этом узле стоит пересадка не с П, на котором туда добрались, а с А на А (АА), что невозможно. Должна быть выбрана такая, например, комбинация: ПА + А или оП + П (других вариантов в а6 не предусмотрено (колонка U).

Может слишком подробно описываю, и все это и так понятно. Но много, не мало.

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

Если рассматривать только 2- вида транспорта, то такой учет не требуется, но с 3-я и более необходим учет.

Признателен за все рекомендации и решения.
Спасибо.
Изменено: Vl Vl - 14.10.2020 12:07:23
Нахождение пути между пунктами, Нужно построить (в таблице) возможные пути между выбранными пунктами
 
Приветствую!
У меня вопрос - предложенное решение может быть использовано для поиска не одного, а нескольких кратчайших маршрутов? Т.е. есть самый короткий и к нему найти ещё определенное (заданное) количество, по возрастанию расстояния.
Может быть интересным рассмотреть все возможные маршруты между двумя точками, но уж больно много их может быть.
Диспетчер имен. Относительная ссылка без привязки к активному листу
 
Вроде соответствует.. зачинщик темы написал:
Цитата
IKor написал:
Подскажите, пожалуйста, можно ли создать именованную_формулу с относительными ссылками без жесткой привязки к активному листу?
Вот и я пытаюсь создать относительную ссылку посредством Диспетчера, но появилась проблемка с работой формулы.
А создавать отдельную тему на схожую тему посчитал излишним.
Диспетчер имен. Относительная ссылка без привязки к активному листу
 
Не подскажете по данной теме... задачка похожего характера.
Попробовал создать команду в диспетчере имен по поиску позиции с относительной строкой на определённом листе. Написал следующую формулу:
=ПОИСКПОЗ(ДВССЫЛ("C" & СТРОКА());База!$D$5:$D$250;0)
но эта конструкция не работает, т.к. результат команды СТРОКА() представляется массивом и как следствие ошибка.
Формула вставленная в ячейку считает без проблем, но введённая в Диспетчер нет.
Если формулу разбить на две части, в том же Диспетчере, как:
1. Ссылка =ДВССЫЛ("C" & СТРОКА())
2. =ПОИСКПОЗ(Ссылка;База!$D$5:$D$250;0)
то работает. а хотелось бы в одну строку не плодя Имена.
Можно сделать, чтобы работало и одной строкой?
Спасибо.
Страницы: 1
Наверх