| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Поиск пути во взвешенном графе |
| Автор: alex35 10.9.2006, 17:31 |
| Дан связанный взвешенный граф G с заданной бинарной весовой функцией (т.е. каждое ребро может иметь вес 1 или 0). Даны две вершины a и b и число n. Требуется найти путь (вершины в котором, по определению, не повторяются) из вершины a в вершину b с заданным количеством ребер n и минимальным весом (т.е. минимальным числом ребер в пути с весом 1). Условие по количеству ребер жесткое, должно равняться точно n. Буду очень благодарен за любой предложенный эффективный алгоритм желательно с оценкой сложности О. Псевдо-код, Паскаль, что угодно (кроме может быть, Ассемблера  Заранее спасибо, С уважением, А. |
| Автор: maxim1000 10.9.2006, 20:14 |
| суть такая: определить множество вершин, в которые можно добраться из точки a с нулевой стоимостью определить, куда можно добраться со стоимостью 1 со стоимостью 2 и т.д. на каждом шаге проверять, не попала ли точка b в определяемое множество, как только попала, заканчиваем более подробно: множество A0={a} множество Bn={все вершины, кудаможно добраться из элементов множества An по нулевым рёбрам} потом выбираем все рёбра от элементов Bn, которые имеют вес 1 и заканчиваются в необработанных вершинах (т.е. не в B0,B1,...Bn), их (рёбер) концы составляют следующее множество An+1, а из него опять делаем Bn+1, потом An+2 и т.д. ... Добавлено @ 20:15 упс... не заметил ограничения на количество рёбер в пути... Добавлено @ 20:27 фиксируем a 1. решаем задачу для всех точек и n=1 (в некоторых случаях решения не будет) 2. для n=2 ... (до нужной длины) для того, чтобы из решения для n получить ршение для n+1: для исследуемой точки (к которой пытаемся построить путь длиной n+1) смотрим всех соседей, для которых существует путь с длиной n, из них выбираем путь с минимальным весом Добавлено @ 20:28 ... опять упс  при таком подходе вершины в путях могут повторяться... так что надо как-то алгоритм модифицировать... |
| Автор: comtat 12.9.2006, 12:30 |
Если метод Флойда под это прокатит могу преслать исходник  |
| Автор: comtat 13.9.2006, 08:40 |
| давай мыло плишлю исходник |
| Автор: alex35 13.9.2006, 15:55 |
| comtat, к сожалению, алгоритм Флойда предназначен для нахождения кратчайших путей во взвешенном графе без учета количества ребер в пути. А в моей задачи стоит жесткое условие - заданное количество ребер. Или можно как то адаптировать алгоритм Флойда к определенному числу ребер?  Тогда я не заметил чего то может? |
| Автор: comtat 13.9.2006, 16:09 | ||
Дык, я незнаю, но поэтой теме что нельзя 100 % не дам |
| Автор: alex35 13.9.2006, 16:10 |
| Я вот смотрю на алгоритм Йена (Yen) поиска К кратчайших путей во взвешенном графе и думаю, как его (Йена) адаптировать под мою задачу. Может, у кого нибудь есть мысли на этот счет? |
| Автор: pablo 14.9.2006, 16:07 |
| Мне известны 2 алгоритма: 1) Дейкстры 2) Беллмана - Форда (Если в графе есть отрицательные веса) Реализация обоих есть в boost |
| Автор: comtat 14.9.2006, 17:01 | ||
Могу сказать, что когда Флойд ищет оптимальный путь, то из двух оптимальных путей он выберет тот, у которого ребер меньше. |
| Автор: Sartorius 14.9.2006, 17:11 |
| Вроде не так и сложно (по времени выполнения) генерировать все возможные пути из а длины n и затем, выбрать из них те, которые заканчиваются b. а затем из них - с наименьшим весом. |
| Автор: maxim1000 14.9.2006, 19:06 | ||
зависит от количества рёбер если граф полный, то перебор всех путей из n рёбер будет x^n (x - среднее количество рёбер из вершины) так что скорость роста экспоненциальная, что довольно немало если убрать требование неповторяемости, то мой вариант можно использовать но, чтобы убрать повторяемые узлы, придётся для каждой вершины хранить не только оптимальный путь вообще, а и оптимальный путь, в зависимости от множества используемых вершин, чтобы знать, какой путь через какие вершины проходит, когда выбирать на следующем шаге это приведёт к тому, что придётся для каждой вершины хранить кучу путей, количество которых с ходу и оценить не получается но это - всего лишь один вариант, который мне пришёл в голову, вполне может быть и другой хотя проблема здесь сходна с проблемой построения гамильтонова цикла, а там с вычислительной сложностью тоже проблемы... |
