Форум на Исходниках.RU

Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3898080 Tue, 19 Dec 2023 07:19:08 +0000 алгоритм Дейкстры с доп.условием https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3898080 Цитата FasterHarder @ 28.06.22, 02:58

Нужно построить маршрут движения поезда между двумя заданными городами, чтобы по нему могли ездить поезда максимально возможного веса.
Это случаем не построение остова, только не минимального, как принято, а максимального? + при этом фактор протяженности вообще не играет никакой роли, как понимаю, нужно смотреть ТОЛЬКО на тоннаж.
Или есть какое-то стандартное название алгоритма для такого задания?

Получилось решить?
Фактор протяженности влияет, но и дополнительное условие есть.
Насколько знаю, такая задача называется - Constrained Shortest Path First]]> Квант Алгоритмы https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870610 Sat, 02 Jul 2022 10:06:56 +0000 алгоритм Дейкстры с доп.условием https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870610 FasterHarder, посмотри видосик - возможно тебя это заинтересует.]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870546 Fri, 01 Jul 2022 10:02:38 +0000 алгоритм Дейкстры с доп.условием https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870546 Цитата m-ch @ 01.07.22, 06:01

3. По найденному маршруту определяем минимальный вес в маршруте, это и будет ограничение поезда из одного города в другой

Вот как-то неочевидно.
Минимальное остовное дерево минимизирует именно вес всего дерева, а не максимальную стоимость ребра этого дерева. Аналогично-обратно и для максимального дерева.

Цитата m-ch @ 01.07.22, 06:01

при этом вес поезда будет не менее уже определенного

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

Добавлено 01.07.22, 10:07

В теории задача решается экстенсивно (не знаю как будет с производительностью).

Просто берём и волновым или иным алгоритмом тупо убеждаемся, что узел назначения достижим из исходного узла. Плюя ядовитой слюной на длину и пропускную способность.
Выбрасываем минимальное по пропускной способности ребро (если использовали не волну, а что-то ещё, и на предыдущем поиске фиксировали путь - выбрасываем минимальное ребро пути и сразу все меньшие рёбра, в путь не входящие). Повторяем.
Выбрасываем рёбра до тех пор, пока при очередном выбрасывании не получим недостижимость.
Вот собственно вес этого последнего выброшенного ребра и будет возможным максимумом пропускной способности любого пути от исходного узла до узла назначения. Более того, любой маршрут будет проходить через это ребро.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870518 Fri, 01 Jul 2022 06:01:02 +0000 алгоритм Дейкстры с доп.условием https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870518
1. Строим максимальное оставное дерево (аналогично, как и минимальное), используя пропускную способность ребер.
2. Находим по остову маршрут от заданных точек начала и конца любым алгоритмом (наверно подойдет волновой алгоритм)
3. По найденному маршруту определяем минимальный вес в маршруте, это и будет ограничение поезда из одного города в другой
4. Из исходного графа удаляем все ребра с пропускной способностью менее найденной и далее строим кратчайший маршрут Дейкстрой (или алгоритмом Левита, или Форда-Беллмана)от начальной до конечной точки, при этом вес поезда будет не менее уже определенного, а маршрут будет кратчайший из возможных.

Есть мысль, что п. 1 и 2 можно решить достаточно просто, немного изменив алгоритм Флойда-Уоршелла и за O(n^3) найдем все возможные максимальные веса поездов между всеми вершинами.
Если граф большой - несколько тысяч вершин, что вполне может быть для описание всех железнодорожных станций, то перебор O(n^3) будет сделать затруднительно]]> m-ch Алгоритмы https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870514 Thu, 30 Jun 2022 21:19:33 +0000 алгоритм Дейкстры с доп.условием https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870514 Цитата esperanto @ 30.06.22, 17:37

Есть задача найти путь когда длина пути это вес максимального ребра в нем, кажется это то, что надо?

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

зы: кстати, макс. остов обычно строят, просто меняя заданные веса ребер на отрицательные ( то, что было самым большим, становится самым маленьким ) и затем стандартный мин.остов]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870464 Thu, 30 Jun 2022 17:37:42 +0000 алгоритм Дейкстры с доп.условием https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870464
Есть задача найти путь когда длина пути это вес максимального ребра в нем, кажется это то, что надо?]]> esperanto Алгоритмы https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870309 Thu, 30 Jun 2022 03:26:38 +0000 алгоритм Дейкстры с доп.условием https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870309 m-ch
я бы рад, но у меня и в помине нет никакого реального графа.
Количество вершин и ребер - произвольное количество ( в рамках разумного ).

m-ch, у меня по этой задачке все алгоритмически почти готово ( Дейкстра на 100% ), а это макс. дерево на 80%, т к еще не оч.понятно, как восстанавливать путь между заданными вершинами. Над этим потихоньку думаю.]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870264 Wed, 29 Jun 2022 12:05:12 +0000 алгоритм Дейкстры с доп.условием https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870264 FasterHarder
Можешь приложить описание реального графа (сети дорог)?
Сколько вершин и сколько ребер ориентировочно?]]> m-ch Алгоритмы https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870258 Wed, 29 Jun 2022 11:47:39 +0000 алгоритм Дейкстры с доп.условием https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870258 Цитата Akina @ 29.06.22, 04:27

Какой смысл соглашаться или не соглашаться с совсем другим методом?

а я вообще ни на грамм не уверен, что у них правильно написано, т к не понимаю до конца)

Цитата Akina @ 29.06.22, 04:27

Что DFS, что BFS - они в основном предназначены для поиска в древовидных и близких к ним графах и имеют определённые проблемы при работе с полными и близкими к ним графами

это золотые слова!

Цитата Akina @ 29.06.22, 04:27

тут ты был, наверное, прав

ну, хоть один раз из 100, хоть в чем-то, наверное, прав :D
----------------------------------------------------

Касательно построения максимального остова - встретил такое понятие в теории графов - редкая штука. В 1000 раз чаще минимальным остовом орудуют.
Вот граф для подзадачи #2. Весом ребер выступает прочность железной дороги. Здесь вообще не сдалась инфо о протяженности, поэтому отбросим ее сразу, чтоб НЕ мешала и НЕ отвлекала:
max_ostov.png (, : 471)

Максимальным остов получается вроде таким:
max_ostov_2.png (, : 500)

Как я понимаю, справедливы следующие утверждения:
1. Т к сначала задаются города для проложения маршрута, то выбирать можно ребро ( с макс. прочностью ) инцидентное стартовой вершине
2. Необязательно строить ВЕСЬ макс. остов. Если было добавлено ребро, инцидентное конечной вершине - конец - маршрут проложен + он не может быть улучшен по прочности.
3. Ответом является самое слабое по прочности ребро. Его можно сразу рассчитывать, при добавлении очередного ребра в макс остов.

По сложности работы алго все достаточно плохо. В худшем случае, когда лишь на последней итерации прокладываются ребро до конечной вершины ( n - 1 по счету итерация, где n - количество вершин ), получается что-то около O( n^3 ), т к на каждой итерации надо просмотреть каждую вершину, которая "в работе" + у нее всех соседей. Все это дело помрет, наверное, уже от 500-1000 вершин).

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

Не уверен, что этот макс. остов вот прям всегда работает правильно, т к эти графы бесконечно коварны и в запасе у них море подлянок))]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870205 Wed, 29 Jun 2022 04:27:53 +0000 алгоритм Дейкстры с доп.условием https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870205 Цитата FasterHarder @ 28.06.22, 20:41

Я так понимаю, что ты с ними категорически не согласен?

Какой смысл соглашаться или не соглашаться с совсем другим методом?

Всё прекрасно получится. Другой вопрос, что поиск в ширину не выглядит оптимальным при фиксированных начальном и конечном узлах - но он так только выглядит. Ведь и тот, и другой поиски предполагают полный перебор и различаются только в порядке перебора. Как, кстати, и Дейкстра.

Хотя есть и подвох. Что DFS, что BFS - они в основном предназначены для поиска в древовидных и близких к ним графах и имеют определённые проблемы при работе с полными и близкими к ним графами, в случае которых (тут ты был, наверное, прав) надо скорее думать о волновом алгоритме.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870202 Tue, 28 Jun 2022 20:41:25 +0000 алгоритм Дейкстры с доп.условием https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870202 Цитата Akina @ 28.06.22, 12:51

А кто мешает-то? Только я как-то смысла не вижу. От поиска в ширину он будет отличаться исключительно порядком сканирования вершин.

ну, ничего не мешает, конечно, просто понятнее немного, как это будет
кстати, встретил такую фразу в одном пособии, которое описывает поиск всех путей между заданными вершинами ( приложу скрин )
not_BFS.png (, : 510)
Я так понимаю, что ты с ними категорически не согласен? ))

Цитата Akina @ 28.06.22, 12:51

Зачем? проще её сразу тащить - всё равно вес-то тащим.

попробую подумать над этим моментом

Akina, в целом большое спс. за помощь. Мне нужно подтягивать знания в вариантах, когда нужно что-то перебирать на графах рекурсивно, т к плоховато понимаю, как внедрить в таких случаях эти BFS / DFS...]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870104 Tue, 28 Jun 2022 12:51:38 +0000 алгоритм Дейкстры с доп.условием https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870104 Цитата FasterHarder @ 28.06.22, 11:51

а разве нельзя и в этой подзадаче применить Дейкстру

Цитата FasterHarder @ 28.06.22, 11:51

Затем восстанавливаем траекторию

Зачем? проще её сразу тащить - всё равно вес-то тащим.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870097 Tue, 28 Jun 2022 11:51:40 +0000 алгоритм Дейкстры с доп.условием https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870097 Цитата Akina @ 28.06.22, 08:17

Применительно к нагрузочной способности ребра. Т.е. поезд в 7 тонн нельзя разделить на два, в 3 и 4 тонны, и пропустить по ребру с нагрузочной способностью не более 5 тонн.

ааааа, теперь я понял о чем речь. Такие моменты могут сильно влиять на ядра алгоритмов), но в этой задаче делить не будем.

По заданию #2 вот еще раз формулировка: "нужно найти МАРШРУТ между двумя разными городами, чтобы проехал поезд макс. веса".
Т е нужно найти единственный маршрут. Если их несколько, то любой подойдет, наверное.
А ведь в графе может быть бесконечное число маршрутов, т к в маршруте могут повторяться ребра и вершины. Но здесь это бессмысленно ( петлять поезду нет смысла ), т к пройденное расстояние вообще ни на что не влияет. Поэтому задачу можно свести к поиску пути ( все ребра и все вершины различны ) вроде бы.

Чтобы найти нужный маршрут нужно перебрать их все. То есть от перебора никуда не деться.
Кстати, ответом будет прочность самого слабого звена маршрута/пути - именно поезд такого предельного веса сможет курсировать по этой траектории.
---------------------------------------------
Akina, поясни, плиз, а разве нельзя и в этой подзадаче применить Дейкстру, только перевернутого.
Т е есть матрица прочности ( хранит тоннаж ).
От заданного города находим максимальные "расстояние" до каждой вершины.
Затем восстанавливаем траекторию: от конечного города двигаемся к начальному и одновременно с этим запоминаем минимальный тоннаж ( это и будет ответом ) + можно и сам маршрут вывести.
Разве это не будет работать и это полный бред??)

Просто BFS / DFS больше предназначен для обхода + там какая-то рекурсия неудобная вроде и пр. неприятности ), а перевернутый Дейскстра мне понятен на 99%...]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870068 Tue, 28 Jun 2022 08:17:59 +0000 алгоритм Дейкстры с доп.условием https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870068 Цитата FasterHarder @ 28.06.22, 07:04

в каком контексте имеешь ввиду "делимость поезда"?

Цитата FasterHarder @ 28.06.22, 07:04

Обычный поиск ВСЕХ путей графа - это ведь полный перебор получается всех возможных путей + их надо где-то сохранить, чтобы потом отсортировать тупой сортировкой

У тебя не поиск всех путей, а поиск всех путей из заданного начала в заданный конец. И тут подойдёт обычный поиск в ширину, например.

Цитата FasterHarder @ 28.06.22, 07:04

для задачи #1 достаточно иметь матрицу расстояний.

А эта задача вообще не оперирует весом состава. А если его учитывать - то получается задача с двумя критериями, для которых ты не задаёшь приоритет. Что лучше - маршрут 100 км на 5 тонн или 150 км, но на 7 тонн? а фиг знает... критерий должен быть один, а не два.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870051 Tue, 28 Jun 2022 07:04:51 +0000 алгоритм Дейкстры с доп.условием https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870051 Цитата Akina @ 28.06.22, 04:29

1. Если поезд неделим, то да - выбрасываем рёбра, не отвечающие условию, применяем Дейкстру.

отлично! Значит с подзадачей #1 все понятно.
Единственное уточнение, в каком контексте имеешь ввиду "делимость поезда"? Или речь о том, что поезд настолько длинный, что может не помещаться в рамках одной железной дороги?)
Можно ведь рассматривать физ.модель графа, где поезд является некоторой точкой какого-то заданного веса.
Но про делимость поезда мне любопытно понять, как это может влиять здесь, поясни, плз.

Цитата Akina @ 28.06.22, 04:29

2. Это будет обычный поиск всех путей в графе между заданными узлами. Просто в процессе построения дополнительно считается и вес, который пропустит путь. Ну а потом тупая сортировка.

Так, а вот здесь хочется кое-что понять.
Обычный поиск ВСЕХ путей графа - это ведь полный перебор получается всех возможных путей + их надо где-то сохранить, чтобы потом отсортировать тупой сортировкой).
И поясни, плз, чем вариант с построением максимального остова плох?? Там тоже сначала надо будет отсортировать по убыванию нагрузки дороги и добавлять по одному ребру, начиная, с самого тяжелого. Разве это НЕ проще, чем полный перебор путей? + нет полных переборов, т е время работы алго будет быстрее. Возможно, что я здесь дико туплю и чего-то не выкупаю с этим макс.остовом.
Кстати, этих остовов макс. тоже может быть больше 1го(. Да, наверное, не факт, что это ПРОЩЕ, чем полный перебор всех путей...
*"прочность" искомого маршрута характеризуется самым слабым его звеном - просто так написал)
Если искать все пути, то это ведь рекурсивный BFS/DFS, наверное...

Цитата Akina @ 28.06.22, 04:29

3. Я бы выбрал именно матрицу смежности. Просто вместо тупых единичек там будет нагрузочная способность ребра.

+1, для задачи #1 достаточно иметь матрицу расстояний. Для задачи #2 пока непонятно, поэтому структуры данных нужно будет еще тщательно продумать...

m-ch, привет! Залетай почаще в обсуждения графов - любопытно почитать твои мысли по ним)

Цитата m-ch @ 28.06.22, 05:57

Исходя их картинки, то граф достаточно разреженный (от каждой вершины идет по небольшому количеству ребер)

ну это так на данный картинке, теоретически граф может быть полным.
кстати, это деление на разреженные/не разреженные графы вроде как условно.
припоминаю, что считают некий коэффициент, как отношение [текущего количества ребер] / [количество ребер полного графа]. Если K = 1 - полный граф, если 0 - пустой, у которого все вершины изолированные.
Чему должен быть равен этот коэффициент ( из интервала ( 0; 1 ) ), чтобы отнести граф к разреженным?) Ты для себя, чему этот коэффициент принимаешь или на "глазок" больше?

Цитата m-ch @ 28.06.22, 05:57

Может подойдет алгоритм Форда-Беллмана

емнип, у него акцент на орграфы + когда есть отр.веса. В этой задаче все числа положительные + неорграф.
Хотя понятно, что и Дейкстру и Форд-Беллман можно применить, но по Дейкстре хоть что-то помню), поэтому выберу Dijkstra

Akina, m-ch, спс за ответы]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870044 Tue, 28 Jun 2022 05:57:15 +0000 алгоритм Дейкстры с доп.условием https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870044 Цитата

Какой формат описания графа является оптимальным для решения этих подзадач?

Исходя их картинки, то граф достаточно разреженный (от каждой вершины идет по небольшому количеству ребер)
В данном случае лучше реализовать алгоритм Дейкстры для разреженных графов, будет считать быстрее, если граф большой.

Цитата

Нужно построить маршрут движения поезда между двумя заданными городами, чтобы по нему могли ездить поезда максимально возможного веса

Может подойдет алгоритм Форда-Беллмана, только вместо выбора минимального веса в ребрах выбирать максимальную грузоподъёмность
По сути задача похожа на эту: https://www.cyberforum.ru/algorithms/thread2992509.html]]> m-ch Алгоритмы https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870040 Tue, 28 Jun 2022 04:29:18 +0000 алгоритм Дейкстры с доп.условием https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870040 2. Это будет обычный поиск всех путей в графе между заданными узлами. Просто в процессе построения дополнительно считается и вес, который пропустит путь. Ну а потом тупая сортировка.
3. Я бы выбрал именно матрицу смежности. Просто вместо тупых единичек там будет нагрузочная способность ребра.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870039 Tue, 28 Jun 2022 02:58:08 +0000 алгоритм Дейкстры с доп.условием https://forum.sources.ru/index.php?showtopic=428213&view=findpost&p=3870039
Условие такое.
Есть города, которые связаны двусторонней железной дорогой ( т е, если поезд может доехать из А в Б, то автоматом может и из Б в А - намек на неориентированный граф ).
Каждая железная дорога характеризуется:
1. своей протяженностью ( например, в км. )
2. максимальным весом ( например, в тонн. ) поезда, который может по ней ехать.

Вот один из примеров:
start_graph.png (, : 613)
Например, железная дорога из Самары в Новгород ( или наоборот - не важно ) имеет протяженность 4 км. и по ней может ехать поезд весом НЕ БОЛЕЕ 7 тонн.
И нужно найти кратчайший путь ( в км. ) между двумя заданными городами.
--------------------------------------------------------------------------------
Я так понимаю, что здесь почти классический алгоритм Dijkstra, но с ограничением на тоннаж поезда. Если убрать тоннаж, то в чистом виде Дейкстра был бы.
Поэтому достаточно просто исключить ВСЕ дороги между городами, у которых допустимый вес поезда строго меньше веса поезда.
Например, берем вес поезда = 5 тонн.
Получается такое что-то:
drop_tonn.png (, : 602)
Если совсем удалить дороги, то получается такое:
drop_tonn_2.png (, : 580)
И после этого запускается алгоритм Дейкстры от заданного города и все.
Все верно в этих рассуждениях?) Уверен на 95%, что, да, так и нужно, но мало ли...
--------------------------------------------------------------------------------
И 2ой момент по этому заданию, который плоховато понимаю совсем.
Нужно построить маршрут движения поезда между двумя заданными городами, чтобы по нему могли ездить поезда максимально возможного веса.
Это случаем не построение остова, только не минимального, как принято, а максимального? + при этом фактор протяженности вообще не играет никакой роли, как понимаю, нужно смотреть ТОЛЬКО на тоннаж.
Или есть какое-то стандартное название алгоритма для такого задания?
--------------------------------------------------------------------------------
И момент 3ий.
Какой формат описания графа является оптимальным для решения этих подзадач? Скорее всего, здесь либо матрица смежности, точнее весовая матрица + матрица протяженности, либо список смежности. Но вроде с весовыми матрицами поудобнее работать + попроще, что ли. Какой бы формат выбрали вы? Возможно, что для разных подзадач ( #1, #2 ) не один и тот же.

спс. за внимание, буду очень признателен за любую помощь]]> FasterHarder Алгоритмы