OpenStreetMap Forum

Aclz

Member

Registered: 2012-08-01

Posts: 34

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

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

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

andriano

Member

Registered: 2009-06-15

Posts: 1,667

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

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

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

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

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

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

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

Cd_spb

Member

From: Санкт-Петербург

Registered: 2011-11-04

Posts: 1,267

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

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

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