маршрут через несколько точек, нужно поскрипеть мозгами

[vaso007]

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

[ERER]

  В 28.06.2012 в 08:11, vaso007 сказал:

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

http://goo.gl/9q5Fc

[vaso007]

ERER, спасибо, будем разбираться, но хотелось бы еще и обсудить, но простым языком

[eklmn]

А по простому, перебирают все возможные варианты маршрута через эти точки - и потом выбирается лучший.

[ERER]

  В 28.06.2012 в 08:47, eklmn сказал:

А по простому, перебирают все возможные варианты маршрута через эти точки - и потом выбирается лучший.

ЕМНИП при 10 точках это будет 362880 вариантов. Приятного расчета и выбора. ;)

[eklmn]

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

А в нашем случае дорога не одна...

Так что 362 тыщи вариантов - это для оптимистов :)

Изменено 28 июня, 2012 пользователем eklmn

[БукаШка]

  В 28.06.2012 в 08:11, vaso007 сказал:

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

Недостаточно исходной информации ))

Оптимальный по времени или по расстоянию ?

[vaso007]

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

[БукаШка]

  В 28.06.2012 в 11:07, vaso007 сказал:

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

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

[/DiOs]

vaso007, Вась, TSP -- она и в Африке TSP, и критерий оптимизации, собственно, похер.

[eklmn]

  Цитата

Тогда наиболее оптимальный маршрут это такой который максимально близок к окружности.

Т.е. по-вашему, оптимальный маршрут из Питера в Москву - через Вологду? :blink:

[zoodov]

  В 29.06.2012 в 05:06, eklmn сказал:

Т.е. по-вашему, оптимальный маршрут из Питера в Москву - через Вологду?

Ну если старт и финиш в одной точке :)