Нужен граф дорог России - что делать/с чего начать?

[irony]рисовать авиамаршруты[/irony]

Где-то была тема для предложений о работе…

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

Эта?

Ну, с базами данных я и сам разберусь, но мне просто нужна понятная структура с данными.

Monochrome, давай структуру базы, посмотрю.
Можно на почту, xliosha@gmail.com

https://dl.dropbox.com/u/11083106/DATA.rar

Файл с базой. Там создано три узла и три ребра. Свойства узлов и ребер там задаются заморочено, поэтому для пробега можно просто создать отдельную таблицу, я бы её потом преобразовал.

Хм… А нельзя ли в каком-нть переносимом формате?
MSSQL под рукой нет.

А что есть?

Чтобы структуру посмотреть, dbf или даже csv достаточно

День добрый. В догонку к поднятой теме: а существуют в природе сервисы или API (платные или бесплатные), рассчитывающие помимо маршрута между точками, еще и последовательность проезда?

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

P.S. Если нет на базе OSM, то может есть на базе еще чего (2gis, Я.карты и т.п.), но чтобы считался и межгород, и внутригородские маршруты по РФ.

Задача коммивояжера, штоле?

Да, типа того.

Это NP-полная задача.

Да знаю я ее как решать каноничным способом и при каноничных условиях. Но зачем?
Дело в том, что я не вижу большого смысла изобретать велосипед, и уж тем более, как топикстартер, выкачивать гиги данных дорожного графа, обновлять всё это хозяйство регулярно, писать и отлаживать алгоритмы прокладки маршрута, вникать в форматы, при условии, что я сам не создаю новый суперпуперплатныйкоммерческий сервис. В остальных случаях зачем тратить такую гору ресурсов? Всё уже украдено написано до нас, вопрос лишь в том, чтобы найти подходящую, пусть даже платную, реализацию.
И, к слову, даже если у меня точек всего штук 20, нужно будет построить матрицу расстояний 20х20, сгенерить кучу запросов и обработать их. В том же OSRM построение “таблиц расстояний” запрещено, за что следует бан.

Конкретно для Свердловской области в стародавние времена существовала программа “СвО на блюдечке”, решавшая эту задачу и предоставлявшая платный API. Всё устраивало, но фирма-производитель загнулась и творение перестало отвечать реалиям.
Гугль имеет подобную бесплатную реализацию “Дирекшенс”, но дорожный граф для РФ убог до безобразия, праймари почти нет, нет даже некоторых транков.
ОСМ из того, что видел, справляется с задачей отлично и имеет самую актуальную базу, но все виденные реализации строят маршрут между точками, уже выстроенными в правильном порядке.

Проблема в том, что

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

Скорей всего эти реализации надо среди всяких пакетов логистики искать.

Я, собственно, об этом и веду речь: что решение стоящей задачи нельзя приравнивать к решению задачи коммивояжера, т.к. для решения означенной задачи необходима уже посчитанная матрица расстояний, получение же которой здесь и является самой главной заковыкой.
Обработать матрицу уже проблем нет, т.к. размерность матрицы в данном конкретном случае лежит в пределах 10-20 точек.

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

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

Вы плохо представляете себе сложность задачи.

Это именно обработка матрицы.

Никто не решает подобные задачи перебором, на это есть алгоритмы нелинейного программирования (“муравьиные колонии”, кластеризация точек и мн. др.), где решение ищется до удовлетворения заданного критерия допустимости.

Впрочем, это всё офф, я уже 2 раза написал, что в идеале я вообще хочу избежать процесс решания задачи, положившись на готовые решения.

Похоже пошли по кругу.
Тремя постами ранее:

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

В общем, нет здесь универсального и быстрого алгоритма.

http://shtosm.ru/2013/02/08/1/