Russian Qt Forum

Хотелось бы узнать, занимался ли кто-нибудь из имеющихся здесь программистов, проектированием и разработкой логистических систем, как графической стороны, так и функциональной (в моем случае транспортная логистика).
Хотелось бы подискутировать по данному вопросу :)

Ты начинай, а мы подхватим.

Ну посчет графической стороны, я думаю можно всем вместе порассуждать,а насчет математической части хотел бы пообщаться в личке (иль в аське :) ) с человеком, кто занимался данным вопросом, если конечно найдется такой кто захочет чем-либо помочь :))

log1c, ваш ящик лс полон, невозможно отправить сообщение :)

Есть такая аська dendy@jabber.org и такая dendy@jabber.ru

Под графической стороной я подразумеваю редактор карты, с возможностью построения таких объектов как города, дороги и тп.

Под математической частью понимается набор алгоритмов и методов оптимизации доставки товара. Решение задач маршрутизации транспорта и ее разновидностей.

Для обсуждения графической стороны я думаю создать отдельный топик, а в этом я просто хотел найти людей которые могли бы посоветовать чем-либо, если уже занимались таким же вопросом :)

Также здесь я думаю можно писать литературу по данному вопросу, ссылки и тп :)

Для решения задач маршрутизации, как вариант, можно использовать технологии нейронных сетей.
Что скажете?

А вообще подобные вещи существуют, нужна изюминка :)

Может быть я вас огорчу, но я делаю это пока что в учебных целях (это я к тому, что я не спец в данной области):) И я думаю прежде чем переходить на сухофрукты (это я про изюминку :) ) нужно разобраться в том, что уже есть :)

задача поиска оптимального маршрута - одна из разновидностей задачи коммивояжера. Последняя относится к классу NP -трудных задач, то есть задач, решение которых нельзя найти за определенное конечное время.

На сегодняшний день, если не ошибаюсь, самыми быстрыми алгоритмами поиска оптимального решения задачи комивояжёра являются нейронные сети. Обязательно посмотрите про них.

ps ветку по-дальше от Qt :)

Ага, я знаком с задачей коммивояжера, реализовывал точный метод ветвей и границ с возвратом и метод муравьиной колонии :))
Ну да ладно, об этом как говорится, в другой серии :))

А в данном топике, как и писал выше, ищу людей готовых помочь, или просто обсуждать в решении данного вопроса :)

>> реализовывал точный метод ветвей и границ с возвратом и метод муравьиной колонии
а с помощью чего были реализованы данные методы?

Всмысле с помощью чего?! :) На сишарпе писал :)

и какова скорость поиска решения была? :)

Об этом история умалчивает :)
Да нет, просто как таковых, я не проводил экспериментов с кол-вом вершин. Максимум для 40ка вершин вроде тестил. Решение выдавалось почти сразу насколько я помню. Хотя метод ветвей и границ был не совсем оптимизирован. Там есть методы оптимизации приведения матриц, что сокращает время.
Вообщем если найду, то гляну :)

глянь, пожалуйста, про методы приведения матриц - интересно взглянуть

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

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

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

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

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

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

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

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

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

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

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

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

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

Посмотри вот этот топик http://habrahabr.ru/blogs/algorithm/48518/ (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://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://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B) вы изобресть пытаетесь?

Ежели его, то в BGL (http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/index.html) есть оптимизированная реализация. :)
Кстати, есть русский перевод книжки: C++ Boost Graph Library (http://www.rsdn.ru/res/book/cpp/bgl.xml)

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

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