Форум программистов, компьютерный форум, киберфорум
Наши страницы
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
RDDare
0 / 0 / 0
Регистрация: 27.08.2014
Сообщений: 4
1

Алгоритм двойного поиска "k" первых минимальных путей

16.01.2016, 08:56. Просмотров 527. Ответов 1
Метки нет (Все метки)

Всем привет! Ищу реализацию алгоритма двойного поиска на C#.
Что представляет из себя задача и алгоритм:
Поиск "K" минимальных путей от заданной вершины до остальных вершин графа.
Например имеется мультиорграф (см. прикрепления)
Перепишем его в табличный вид:
 abcd
a[0, _, _][4, _, _][-3, 2, _][6, _, _]
b[-1, 2, _][0, _, _][_, _, _][_, _, _]
c[4, _, _][_, _, _][0, _, _][9, _, _]
d[_, _, _][-1, 3, 4][-8, 1, 2][0, _, _]
Задача найти 3 первых минимальных пути от вершины "а" до остальных вершин.
Алгоритм двойного поиска является обобщенным вариантом алгоритма Беллмана-Мура, но подходящего ничего не нашёл.
Алгоритм итерационный и состоит из двух этапов: обратный и прямой поиск.
Сначала выполняется обратный поиск, потом прямой, после этого сравниваются полученные матрицы.
Если они разные, то итерация увеличивается и поиск выполняется повторно.
Если одинаковые то восстанавливаются минимальные пути.
Это всё что мне известно.
0
Изображения
 
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.01.2016, 08:56
Ответы с готовыми решениями:

Алгоритм флойда для поиска кратчайших путей в графе
алгоритм флойда для поиска кратчайших путей в графе. Вывожу длину путей между...

Описать класс "поезд", содержащий поля "пункт назначения", "номер поезда", "время отправления"
Помогите пожалуйста с классом Описать класс «поезд», содержащий следующие...

Методом вычислить тип треугольника: "не существует", "тупоугольный", "прямоугольный", "остроугольный"
Помогите пожалуйста С помощью метода вычислить тип треугольника::cry: 1) если...

Проблема при сравнении: "Оператор ">" не может применяться к операндам типа "Т" и "Т""
Добрый день , пишу сортировку , все делаю на основе Т , но вот в чем проблемма...

Построить иерархию классов "Студент", "преподаватель", "персона", "заведующий кафедрой"
Построить иерархию классов: Студент, преподаватель, персона, заведующий...

1
cos02
0 / 0 / 0
Регистрация: 30.01.2017
Сообщений: 1
30.01.2017, 14:36 2
Получилось найти решение? Разве это Беллман-Мур?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.01.2017, 14:36

Напишите программу, которая подсчитывает, сколько учащихся получило "2", "3", "4" и "5"
Помогите, пожалуйста, с решением следующей задачи: учащиеся сдают экзамены по...

Составить программу по управлению манипулятором "мышь". Выбор типа курсора организовать по нажатию на клавиши "q","w","r
Составить программу по управлению манипулятором "мышь". Выбор типа курсора...

Поиск в массиве. Ошибка "Оператор "&&" не может применяться к операндам типа "bool" и "double""
Найти номер последнего минимального элемента среди положительных четных...


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

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

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