Транспортная логистика

[Khs]

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

[Khs]

Вот щас спросил у него.
1000 вершин за минуту.
1.3гб оперативы.

Приведение матрицы оптимизируется с помощью венгерского алгоритма.
Вычислительная сложность венгерского алгоритма – n³

[Karl-Philipp]

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

[Khs]

Ну это с учетом что граф полный.

Да и еще, нейронные сети вроде бы дают приближенное решение, как и метод муравьиной колонии, как и генетические алгоритмы, в отличие от метода ветвей и границ.
Так что, это дело повседневного выбора, скорость, либо точность

[Karl-Philipp]

ну а для вашего случая - кто будет ждать решения одну минуту?

[lit-uriy]

да, тема определнно не для раздела Qt, скорее Программирование->Общий

[Khs]

Так это не мой случай, это случай тестера модификаций данного алгоритма Это не значит что это практически применять надо

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

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

Ага, опять не там создал топик

[xintrea]

Для транспортной логистики может подойти динамическое программирование.

Посмотри вот этот топик 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.

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

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

В твоем случае найти однозначную ОДНУ цепочку с минимальной энергией, которая будет самая правильная, невозможно. Потому что при поиске у тебя нет однозначного ограничения, как это сделано у перца, что считать "правильной" цепочкой. У тебя, например, возможна ситуация, что выгоднее из одной точки вернуться в предыдущую посещенную. Или в графе будут тупиковые точки, из которых движени возможно только назад. Но как минимум, этим алгоритмом ты сможешь сильно сузить область поиска, а потом уже возможно тупо перебрать решения и выбрать оптимальное.

[Khs]

Окей, спасибо, гляну

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

Попозже создам еще топики, касающиеся разработки графической части и функциональной

[Tonal]

А не Алгоритм Дейкстры вы изобресть пытаетесь?

Ежели его, то в BGL есть оптимизированная реализация.
Кстати, есть русский перевод книжки: C++ Boost Graph Library

[Khs]

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

[IKSparrow]

Вся красота стройной и логичной схемы транспортной логистики реализованной с помощью математики споткнётся о первую же пробку и/или аварию на дороге. Задачка для ума, не имеющая возможности практической реализации. Подобную систему с успехом заменит пяток грамотных диспетчеров со средствами связи.