OberonCore
https://forum.oberoncore.ru/

Картография
https://forum.oberoncore.ru/viewtopic.php?f=27&t=1794
Страница 1 из 1

Автор:  Иван Кузьмицкий [ Среда, 02 Сентябрь, 2009 13:43 ]
Заголовок сообщения:  Картография

Вот, озаботился я прокладкой маршрута по карте. Пока что нахожусь в процессе сбора информации по теме, но уже захотелось иметь в перспективе компонент для BlackBox :)

Никто не занимается вопросами карт? Масса вопросов уже возникла, хочется обсудить :)

Автор:  Илья Ермаков [ Среда, 02 Сентябрь, 2009 18:58 ]
Заголовок сообщения:  Re: Картография

Под картой понимается граф транспортной сети типа городской?
Тогда это просто поиск кратчайшего пути в графе.

Автор:  Info21 [ Среда, 02 Сентябрь, 2009 20:53 ]
Заголовок сообщения:  Re: Картография

Илья Ермаков писал(а):
просто поиск кратчайшего пути в графе.
Реальные задачи могут и не быть такими простыми. И часто не бывают.

Автор:  Илья Ермаков [ Среда, 02 Сентябрь, 2009 21:25 ]
Заголовок сообщения:  Re: Картография

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

Автор:  Иван Кузьмицкий [ Среда, 02 Сентябрь, 2009 21:45 ]
Заголовок сообщения:  Re: Картография

Нужно проложить маршрут от точки А в точку Б по городским улицам и посчитать длину маршрута.

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

Автор:  Сергей Губанов [ Среда, 02 Сентябрь, 2009 22:40 ]
Заголовок сообщения:  Re: Картография

Поиск кратчайших путей это ерунда (можно даже чуть-чуть быстрее Дейкстровского N Log N если памяти не жалко), вот задача коммивояжёра другое дело.

Шесть лет назад я работал в ООО НИКА КОМ и написал там первую версию программы "Маршрут Мастер":

http://www.ncom.ru/win/soft/marsh_master.php

Она умела решать задачу коммивояжёра точно для 18 точек примерно минуты за три (на пентиуме 4), и для 30-40 точек -- приближённо примерно за час. Первое неплохое приближение выдавала через несколько секунд, а потом улучшала моим методом который я назвал "распутывание узлов" -- это типа теории возмущений: путь представляется узлом с тремя перехлёстами, с четырьмя, с пятью и т.д.. Распутывание узла третьего порядка уменьшало длину пути процентов на 10-20, четвертого - на 1-2, пятого -- на 0.1-0.2%, а меньше и не нужно было -- с такой точностью карту не задашь.

Автор:  Info21 [ Среда, 02 Сентябрь, 2009 22:54 ]
Заголовок сообщения:  Re: Картография

Сергей Губанов писал(а):
Первое неплохое приближение выдавала через несколько секунд, а потом улучшала моим методом который я назвал "распутывание узлов" -- это типа теории возмущений ...
Публикации нет? Это же, вроде, очень публикабельная вещь. Даже я бы почитал, раз уж теория возмущений :)

Автор:  Валерий Лаптев [ Четверг, 03 Сентябрь, 2009 15:23 ]
Заголовок сообщения:  Re: Картография

А уж я - обязательно почитал бы ... :)

Автор:  Сергей Губанов [ Четверг, 03 Сентябрь, 2009 18:23 ]
Заголовок сообщения:  Re: Картография

Как таковой публикации нет, только на форумах algolist-а трепался, там ни кому не нужно было.

Идея улучшения пути понятна из следующих рисунков.

Одновременная перестановка в двух парах точек:
Вложение:
2.png
2.png [ 19.21 КБ | Просмотров: 4583 ]


Одновременная перестановка в трёх парах точек:
Вложение:
3.png
3.png [ 22.76 КБ | Просмотров: 4583 ]


Одновременная перестановка в четырёх парах точек:
Вложение:
4.png
4.png [ 25.67 КБ | Просмотров: 4583 ]


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

-------

А на счёт точного алгоритма для 18 точек, так там просто на каждом шаге построения пути надо оборачиваться и смотреть назад. Если окажется, что последние N точек можно было пройти в какой-то иной последовательности и путь стал бы короче, значит дальше этот вариант пути не рассматриваем так как он заведомо не оптимальный. Чем глубже назад смотреть, т.е. чем больше N тем лучше, однако такой просмотр стоит O(N!), значит слишком глубоко смотреть назад тоже нельзя. Эмпирически установил, что овчинка стоит выделки при N<=7. Написал кодогенератор, который составил код проверки для 7! = 5040 вариантов + код для 6!, 5!, 4!, 3! и 2 вариантов которые нужны в самом начале построения варианта пути когда количество точек ещё меньше семи. Ну вот и получилось, что точное решение для 18 точек вычислялось примерно за три минуты (для 19 точек -- в 19 раз дольше, т.е. примерно за час, а для 20 точек значит примерно за сутки).

Автор:  Сергей Губанов [ Четверг, 03 Сентябрь, 2009 18:38 ]
Заголовок сообщения:  Re: Картография

Сергей Губанов писал(а):
Первый вариант пути вычисляется как угодно, например, жадным алгоритмом. Потом пытаемся уменьшить длину пути перебирая всевозможные перестановки в двух парах точек, затем пробуем все трёхпарные перестановки, потом все четырёхпарные, и так далее.


На практике получалось что-то вроде следующего. После двухпарных распутываний путь, например, 70 километров, после трёхпарных, например, 65 км, после четырёхпарных, например, 64, а после пятипарных - 63.8 км. То есть пятипарное распутывание улучшало путь метров на двести, но с такой точностью общей длины пути мы и карту-то задать не могли. Так что реально прерывать алгоритм можно было уже после трёхпарных распутываний.

Автор:  Info21 [ Четверг, 03 Сентябрь, 2009 19:11 ]
Заголовок сообщения:  Re: Картография

Сергей Юрьевич, напишите текст и просто хотя бы выложите в соотв. раздел в архиве http://arxiv.org/corr/home

Автор:  Сергей Губанов [ Четверг, 03 Сентябрь, 2009 22:04 ]
Заголовок сообщения:  Re: Картография

Как найду свободное время напишу, выложу. Там ведь на русском тоже можно выкладывать?

Кстати, забыл ещё сказать, что в результате распутывания узла вполне может случится так, что в новом пути появятся узлы более низкого порядка чем был он. Так что надо откатываться назад и проверять/распутывать узлы более низких порядков заново.

Автор:  Info21 [ Четверг, 03 Сентябрь, 2009 22:43 ]
Заголовок сообщения:  Re: Картография

Сергей Губанов писал(а):
Там ведь на русском тоже можно выкладывать?
Нет, на русском нельзя. Но усилие приложить стоит.[/quote]

Сергей Губанов писал(а):
... Так что надо откатываться назад и проверять/распутывать узлы более низких порядков заново.
Я бы вообще попробовал со случайными начальными конфигурациями.
Механизм сам по себе.
А потом и поиграть можно с подготовкой начальной конфигурации.

Интересный алгоритмец. (Как раз леча организм развлекаюсь вязанием узлов. Надо же, как совпало :))

Страница 1 из 1 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/