0 / 0 / 0
Регистрация: 25.01.2013
Сообщений: 4
1

Генетический алгоритм поиска кратчайшего пути в графе

06.08.2014, 12:37. Показов 7600. Ответов 5
Метки нет (Все метки)

Преподаватель дал вот такое задание :
"Распараллелить генетический алгоритм на куда, а алгоритм будет искать кратчайший путь в графе. Ну и типа привязать это дело к поиску кратчайших маршрутов в сети ..."
Помогите сделать генетический алгоритм поиска кратчайшего пути. Мож у кого-нибудь какие нибудь исходники завалялись?
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.08.2014, 12:37
Ответы с готовыми решениями:

Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе
Блин я уже так задолбался с этим заданием может кто нибудь поможет: Построить алгоритм поиска...

Разобраться с процедурой поиска кратчайшего пути в графе
В БД содержатся 2 таблицы: edge (id, start, finish, weight) - ребра графа с указанием весов, vertex...

Нахождение кратчайшего пути в графе (алгоритм Дейкстры)
Здравствуйте, помогите пожалуйста, СРОЧНО,написать псевдокод реализации нахождения кратчайшего пути...

Нахождение кратчайшего пути в графе, алгоритм Уоршелла
Привет всем! алгоритм уоршелла, нужно найти кратчайший путь в графе. ввожу матрицу 0 1 5 1 0 2...

5
1471 / 826 / 140
Регистрация: 12.10.2013
Сообщений: 5,456
06.08.2014, 12:42 2
Давычто, это же задача коммивояжера.
https://ru.wikipedia.org/wiki/Задача_коммивояжёра
0
0 / 0 / 0
Регистрация: 25.01.2013
Сообщений: 4
06.08.2014, 13:14  [ТС] 3
Проблема в реализации ГЕНЕТИЧЕСКОГО алгоритма, а не обычного
0
1471 / 826 / 140
Регистрация: 12.10.2013
Сообщений: 5,456
06.08.2014, 14:45 4
Цитата Сообщение от maioneziwe Посмотреть сообщение
ГЕНЕТИЧЕСКОГО алгоритма, а не обычного
Так в этом то и дело, сколько поколений придеться чтобы найти оптимальный + мутации + настройки этих мутаций…
Академики разрабатывали спец методы для решения этих задач, а генетического там и нет. Может неспроста?
“15 городов существует 43 миллиарда маршрутов и для 18 городов уже 177 триллионов.”

Добавлено через 7 минут
Цитата Сообщение от maioneziwe Посмотреть сообщение
Помогите сделать генетический алгоритм
Сколько читал про него и вывод такой: это общее название метода расчета с принятыми в этом методе терминами, а суть его работы проста, но и по ней пишут целые книги…
Цитата Сообщение от maioneziwe Посмотреть сообщение
Мож у кого-нибудь какие нибудь исходники завалялись?
Странная фраза, исходники на каком коде, а диалекты?А для какой среды? Конкретней формулируйте. Вы когда-нибудь читали чужой код? Это ж врагу не пожелаешь, вам нужен не код исходника а псевдокод. Кроме того такая программа это интеллектуальная собственность, вряд ли кто-то выложит исходники просто так.
0
3174 / 1933 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
06.08.2014, 14:50 5
Цитата Сообщение от Excalibur921 Посмотреть сообщение
вряд ли кто-то выложит исходники просто так
Навалом, повсюду. Ex.: Genetic Algorithm Library
1
1471 / 826 / 140
Регистрация: 12.10.2013
Сообщений: 5,456
06.08.2014, 15:18 6
Круто, столько труда, и выложили просто так

Добавлено через 10 минут
Кстати походу там не оптимальное решение, сильно мало поколений.
Наверно в выкипедии что я кидал ссылку сравнивали с Брутто форс этойже задачи ( как эталон), даже для 18 точек городов уже 177 триллионов.
А в примере вроде всего 9000 поколений?
Может это метод считающий генетическим алгоритмом но не находящий близкое к оптимальному решение? (А как они проверят там триллионы вариантов это для НИИ ). Но да, оно считает генетическим алгоритмом, а качество расчета? Ах, оставьте… Посему наверно и
Цитата Сообщение от Excalibur921 Посмотреть сообщение
а генетического там и нет. Может неспроста?
Добавлено через 13 минут
Кстати, а как вы узнаете что близки к правде? Где в задании Брутто Форс результат эталона? И где проходной бал + - сколько процентов от эталона считается правдой?
Ведь без него смысл создавать программу если она будет просто генетический алгоритм расчета который как бы находящий что то там наверно правильно. А нуда это ж от препада, тогда катит любой попроще Сложный – не поверят что вы успели сами, простой – легко понять, вдруг спросит а как…
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.08.2014, 15:18
Помогаю со студенческими работами здесь

Алгоритм Дейкстры (поиск кратчайшего пути в графе)
Доброго времени суток! Пытаюсь разобраться в алгоритме Дейкстры по книжке "Грокаем алгоритмы",...

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

Алгоритм Дейкстры поиска кратчайшего пути
Помогите решить задачу. У меня с графами проблемы Разработать и реализовать в виде программы...

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru