Russian Qt Forum
Ноябрь 23, 2024, 05:43 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Russian Qt Forum > Forum > Программирование > Алгоритмы > Транспортная логистика
Страниц: 1 [2]   Вниз
« предыдущая тема следующая тема »
  Печать  
Автор Тема: Транспортная логистика  (Прочитано 18347 раз)
Khs
Гость
« Ответ #15 : Январь 10, 2009, 21:51 »
Нет, у меня как раз без этих методов, просто я знаю про них от своего знакомого на курс младше меня, который как раз занимается усовершенствованием алгоритма, с помощью каких-то других вспомогательных методов.
Как спрошу, напишу в личку Улыбающийся
Записан
Khs
Гость
« Ответ #16 : Январь 10, 2009, 21:59 »
Вот щас спросил у него.
1000 вершин за минуту.
1.3гб оперативы.

Приведение матрицы оптимизируется с помощью венгерского алгоритма.
Вычислительная сложность венгерского алгоритма – n3
Записан
Karl-Philipp
Гость
« Ответ #17 : Январь 10, 2009, 22:16 »
долговато будет Улыбающийся
нейронная сеть с таким делом за доли секунды должна справиться Улыбающийся главное обучить её
Записан
Khs
Гость
« Ответ #18 : Январь 10, 2009, 22:34 »
Ну это с учетом что граф полный.

Да и еще, нейронные сети вроде бы дают приближенное решение, как и метод муравьиной колонии, как и генетические алгоритмы, в отличие от метода ветвей и границ.
Так что, это дело повседневного выбора, скорость, либо точность Улыбающийся
Записан
Karl-Philipp
Гость
« Ответ #19 : Январь 10, 2009, 22:53 »
ну а для вашего случая - кто будет ждать решения одну минуту?
Записан
lit-uriy
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 3880


Просмотр профиля WWW
« Ответ #20 : Январь 10, 2009, 22:56 »
да, тема определнно не для раздела Qt, скорее Программирование->Общий
Записан
Юра.
Khs
Гость
« Ответ #21 : Январь 10, 2009, 23:03 »
Так это не мой случай, это случай тестера модификаций данного алгоритма Улыбающийся Это не значит что это практически применять надо Улыбающийся

Естественно, метод ветвей и границ применяется когда вершин не более 100, об этом упоминается чуть ли не в каждом учебнике, где про него есть инфа Улыбающийся

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

Ага, опять не там создал топик Грустный
Записан
xintrea
Супер активный житель
*****
Offline Offline

Сообщений: 754



Просмотр профиля WWW
« Ответ #22 : Январь 10, 2009, 23:55 »
Для транспортной логистики может подойти динамическое программирование.

Посмотри вот этот топик http://habrahabr.ru/blogs/algorithm/48518/ и статью в википеии http://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5.

На хабре чувак касается практической стороны вопроса динамического программирования.

В твоем случае, у тебя есть граф с точками, которые надо объехать, и известны длины связей между ними (расстояние между точками). Ты можешь рассматривать эти длины как энергию (у чувака это интенсивность точек относительно других точек) при просчете эээ.. "карты энергий связей". А при поиске оптимального пути, тебе нужно будет искать цепочку с минимальной энергией, которая и будет оптимальным путем.

В твоем случае найти однозначную ОДНУ цепочку с минимальной энергией, которая будет самая правильная, невозможно. Потому что при поиске у тебя нет однозначного ограничения, как это сделано у перца, что считать "правильной" цепочкой. У тебя, например, возможна ситуация, что выгоднее из одной точки вернуться в предыдущую посещенную. Или в графе будут тупиковые точки, из которых движени возможно только назад. Но как минимум, этим алгоритмом ты сможешь сильно сузить область поиска, а потом уже возможно тупо перебрать решения и выбрать оптимальное.
Записан
Собираю информацию по крупицам
http://webhamster.ru
Khs
Гость
« Ответ #23 : Январь 11, 2009, 00:19 »
Окей, спасибо, гляну Улыбающийся

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

Попозже создам еще топики, касающиеся разработки графической части и функциональной Улыбающийся
Записан
Tonal
Гость
« Ответ #24 : Январь 11, 2009, 12:10 »
А не Алгоритм Дейкстры вы изобресть пытаетесь?

Ежели его, то в BGL есть оптимизированная реализация. Улыбающийся
Кстати, есть русский перевод книжки: C++ Boost Graph Library
Записан
Khs
Гость
« Ответ #25 : Январь 11, 2009, 13:36 »
Нет, не алгоритм Дейкстры Улыбающийся Но за ссылку спасибо, можно выдрать что-нить полезное Улыбающийся
Записан
IKSparrow
Гость
« Ответ #26 : Июль 31, 2009, 08:37 »
Вся красота стройной и логичной схемы транспортной логистики реализованной с помощью математики споткнётся о первую же пробку и/или аварию на дороге. Задачка для ума, не имеющая возможности практической реализации. Подобную систему с успехом заменит пяток грамотных диспетчеров со средствами связи.
Записан
Страниц: 1 [2]   Вверх
  Печать  
« предыдущая тема следующая тема »
 
Перейти в:  


Страница сгенерирована за 0.148 секунд. Запросов: 22.