vaso007 Posted June 28, 2012 Share Posted June 28, 2012 Друзья!!! очень прошу помощи, в общем озадачился я тут одной задачкой имеет 10 точек с координатами, нужно через них проложить оптимальный маршрут, НО старт и финиш находится в одной точке, как построить оптимальный маршрут через все точки, голову уже сломал какой должен быть алгоритм Link to post Share on other sites
ERER Posted June 28, 2012 Share Posted June 28, 2012 Друзья!!! очень прошу помощи, в общем озадачился я тут одной задачкой имеет 10 точек с координатами, нужно через них проложить оптимальный маршрут, НО старт и финиш находится в одной точке, как построить оптимальный маршрут через все точки, голову уже сломал какой должен быть алгоритм http://goo.gl/9q5Fc 1 Link to post Share on other sites
vaso007 Posted June 28, 2012 Author Share Posted June 28, 2012 ERER, спасибо, будем разбираться, но хотелось бы еще и обсудить, но простым языком Link to post Share on other sites
eklmn Posted June 28, 2012 Share Posted June 28, 2012 А по простому, перебирают все возможные варианты маршрута через эти точки - и потом выбирается лучший. Link to post Share on other sites
ERER Posted June 28, 2012 Share Posted June 28, 2012 А по простому, перебирают все возможные варианты маршрута через эти точки - и потом выбирается лучший. ЕМНИП при 10 точках это будет 362880 вариантов. Приятного расчета и выбора. ;) Link to post Share on other sites
eklmn Posted June 28, 2012 Share Posted June 28, 2012 (edited) Так это в простом случае, если от каждой точки до другой есть только один безальнернативный путь. А в нашем случае дорога не одна... Так что 362 тыщи вариантов - это для оптимистов :) Edited June 28, 2012 by eklmn Link to post Share on other sites
БукаШка Posted June 28, 2012 Share Posted June 28, 2012 Друзья!!! очень прошу помощи, в общем озадачился я тут одной задачкой имеет 10 точек с координатами, нужно через них проложить оптимальный маршрут, НО старт и финиш находится в одной точке, как построить оптимальный маршрут через все точки, голову уже сломал какой должен быть алгоритм Недостаточно исходной информации )) Оптимальный по времени или по расстоянию ? Link to post Share on other sites
vaso007 Posted June 28, 2012 Author Share Posted June 28, 2012 оптимальный это по двум параметрам, если по расстоянию то это короткий, если по времени то быстрый, а нам нужен оптимальный тоесть по времени и расстоянию, но думаю давайте задачу упростим, пусть для начала будет короткий Link to post Share on other sites
БукаШка Posted June 28, 2012 Share Posted June 28, 2012 оптимальный это по двум параметрам, если по расстоянию то это короткий, если по времени то быстрый, а нам нужен оптимальный тоесть по времени и расстоянию, но думаю давайте задачу упростим, пусть для начала будет короткий Тогда наиболее оптимальный маршрут это такой который максимально близок к окружности. Это если не учитывать важность посещаемых мест, а считать контрольные точки равнозначными, а дороги одинаковыми по качеству и скоростному режиму. Link to post Share on other sites
/DiOs Posted June 28, 2012 Share Posted June 28, 2012 vaso007, Вась, TSP -- она и в Африке TSP, и критерий оптимизации, собственно, похер. Link to post Share on other sites
eklmn Posted June 29, 2012 Share Posted June 29, 2012 Тогда наиболее оптимальный маршрут это такой который максимально близок к окружности. Т.е. по-вашему, оптимальный маршрут из Питера в Москву - через Вологду? :blink: Link to post Share on other sites
zoodov Posted June 29, 2012 Share Posted June 29, 2012 Т.е. по-вашему, оптимальный маршрут из Питера в Москву - через Вологду? Ну если старт и финиш в одной точке :) Link to post Share on other sites
Recommended Posts