SusaninLab

Мы ищем оптимальные пути


Синопсис:

Наверняка перед вами стояла следующая задача - объехать несколько мест в городе. Это могут быть магазины или достопримечательности и потратить на это как можно меньше времени или денег. Каждый решает эту вполне обыденную задачу исходя из каких-то личных предположений и опыта. Однако люди далекие от математики даже не предполагают сколь велико может быть число вариантов обхода этих мест. Например, для 5 точек (всего 5!) существует 120 различных способов их обойти. А для 6 это число уже равно 720. В математике это называется факториальный рост.

Первая задача, которую решает наша программа Susanin это поиск наиболее оптимального маршрута. Чуть подробнее это звучит так - необходимо выйти из пункта А, обойти пункты C1, C2, C3… Cn и попасть в пункт B при этом затратив как можно меньше времени (денег, бензина и т. п.). Сами пункты А и В могут совпадать. В этом случае мы получаем одну из классических задач математики - задачу коммивояжера. Вторая задача математическим языком формулируется как задача построения минимального остовного дерева. Ниже мы рассмотрим практическую задачу и как ее решить с помощью нашей программы.

Основные возможности:

Как работает наша программа:

Поиск оптимальных путей

Итак перед нами стоит задача посетить несколько мест в городе и при этом потратить как можно меньше времени, (денег, преодолеть минимум расстояния). Давайте предположим, что мы выделили места в городе, которые мы хотим посетить. Сами мы находимся в точке А, а после обхода всех пунктов нам нужно попасть в точку В. Можно также предположить для конкретности, что мы перемещаемся на автомобиле и хотим потратить как можно меньше денег. С помощью онлайн-карт и линейки для измерения расстояний, мы оцениваем стоимость перемещения между пунктами. Наша программа не является конечным продуктом для решения подобных задач. Поэтому некоторые действия придется осуществлять с помощью сторонних инструментов.

Перед нами возникает следующий набор - точки и линии, которые соединяют эти точки. Такая абстрактная диаграмма в математике называется графом. Если еще немножко добавить математической точности, то линии соединяющие точки называются ребрами. Каждому ребру мы ставим в соответствие некоторое число, которое называется весом, в нашем случае оно означает стоимость перемещения между двумя точками. Например перемещение из А в С3 обойдется нам в 130.5 рублей (пусть будут рубли, см. рис 1). Программа позволяет указать некоторое ребро как ключевое, тогда вес остальных ребер будет вычисляться автоматически из простой арифметической пропорции. На рисунке ниже видно, что ребро соединяющее А и С1, является ключевым. Обратите так же внимание, что не все пункты соединены между собой ребрами. Такое возможно поскольку в городе имеется ограниченное количество дорог, мостов через реку и т.д.


Далее нам необходимо указать в программе, пункт где мы с вами находимся, то есть пункт А. Для этого в блоке Select Node, в выпадающем списке выбираем “Start”.


И с помощью указателя мыши выбираем пункт А. Теперь наш граф имеет такой вид:


Далее выпадающий список в блоке Select node, выставляем в положение Visit и выбираем вершины, которые мы собираемся посетить. Теперь наш граф выглядит так:


И наконец выбираем категорию Finish в блоке Select Node и получаем следующий граф:


Теперь у нас есть все необходимые данные и мы можем расчитать наш маршрут. В блоке Solution нажимаем кнопку Path Start->Finish и получаем схему прохождения маршрута:

A->C1->C2->C5->C8->C4->C3->C7->B.

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

Построение минимального остовного дерева

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


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


Таким образом расстояния между 1 и 2 равно 6.7 км, между 2 и 3 - 9.2 км и т.д. Таковы начальные данные. Также заметим, что не между любыми пунктами можно построить дорогу. Этому могут препятствовать какие-то особенности местности и рельефа. В нашем случае, например, мы не рассматриваем построение дороги между 4 и 10. Далее в программе мы нажимаем кнопку Spanning tree и получаем решение нашей задачи.

Картинка демонстрирует нам, то где какие дороги нужно построить, чтобы обеспечить возможность проезда между данными населенными пунктами, а сама сеть дорог имела бы минимальную длину.

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

Развитие:

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

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

Контакты:

О нас

Мы живем в России, в старинном русском городе Нижнем Новгороде. Мы команда высококвалифицированных специалистов.

Наши профессиональные навыки:

ОС: Windows NT/XP/Vista/7/8/10, Windows Phone, Linux (основные навыки) Языки: C++ (STL, MFC, ATL), C#, VB .NET, XML, HTML, PHP, Perl, SQL, x86 assembler

Технологии и области компетенции:

ООП, COM/DCOM/ActiveX, XPCOM (Mozilla), Microsoft .NET, сетевые протоколы (TCP, UDP, SSL), WEB-технологии (HTML, XML/XSLT, MS IIS, Perl, PHP, Apache, ASP, ASP.NET), базы данных (MySQL, MS SQL Server), графика и мультимедия (GDI, GDI+, DirectX, OpenGL, DirectShow, MS Media Services), Bluetooth (стэки Widcomm, Bluesoleil, MS)

Средства разработки/компиляторы:

MS Visual Studio, Borland C++ Builder, Eclipse IDE

Другие навыки:

Владение системами контроля версий (TFS, GIT, SVN), создание инсталляций (MS Installer, InnoSetup, InstallShield), документирование ПО (MS Word, Visio, DocumentX!, HelpKit-COM Assist), Технический английский на высоком уровне, разговорный - достаточен для общения. Высокий уровень математической подготовки и хорошая алгоритмическая база. Средний опыт работы в ИТ – 12 лет Средний возраст – 38 лет

Наш опыт:

1) Обработка изображений, сравнение изображений на предмет схожести, поиск на изображении определенного фрагмента

2) Захват видео потока с веб-камер, обнаружение движения в камере

3) Создание оригинальной криптографической системы на основе фракталов

4) Разработка сложных модульных приложений

5) Работа с разным аппаратным обеспечением (звук, видео, сканеры, модемы, последовательные и параллельные порты)

6) Графические интерфейсы

7) Сетевое взаимодействие (разработка/имплементация протоколов верхнего уровня)

8) Работа с потоковым аудио и видео

9) Работа с протоколами и профайлами Bluetooth (RFCOMM, OBEX, FTP, Audio Gateway)

10) Создание WEB-сайтов

Пользовательская версия:

Наша программа распространяется на БЕСПЛАТНОЙ ОСНОВЕ.

Версия для программистов:

Наша программа включает в себя две самостоятельных программных библиотеки: ELGraphVisio и ELSusaninPath. ELGraphVisio - это оконный ActiveX компонент, находящийся в центре нашей программы, он обеспечивает всю интерактивную работу с графами - создание и редактирование. ELSusaninPath это ActiveX компонент, который содержит алгоритмы для работы с графами - поиск путей и построение минимальных остовных деревьев. Если вы являетесь программистом и владеете такими языками как C++, C#, VB.NET, а также работаете со средствами разработки, которые поддерживают работу с ActiveX компонентами (например Microsoft Visual Studio), то Вы можете воспользоваться нашими библиотеками для создания собственного приложения. Сами компоненты ELGraphVisio и ELSusaninPath не являются бесплатными. Если вы собираетесь их использовать, напишите нам и мы решим с вами этот вопрос. Это не дорого. Ниже вы можете скачать более подробное описание этих библиотек. В настоящий момент это описание имеется только на английском языке.

Документация ELGraphVisio

Документация ELSusaninPath

Если у Вас есть желание помочь развитию проекта, Вы можете это сделать с помощью формы внизу. Спасибо.

Связаться с нами: