Вот, озаботился я прокладкой маршрута по карте. Пока что нахожусь в процессе сбора информации по теме, но уже захотелось иметь в перспективе компонент для BlackBox
Никто не занимается вопросами карт? Масса вопросов уже возникла, хочется обсудить
| 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 [ 19.21 КБ | Просмотров: 6986 ] Одновременная перестановка в трёх парах точек: Вложение: 3.png [ 22.76 КБ | Просмотров: 6986 ] Одновременная перестановка в четырёх парах точек: Вложение: 4.png [ 25.67 КБ | Просмотров: 6986 ] Первый вариант пути вычисляется как угодно, например, жадным алгоритмом. Потом пытаемся уменьшить длину пути перебирая всевозможные перестановки в двух парах точек, затем пробуем все трёхпарные перестановки, потом все четырёхпарные, и так далее. ------- А на счёт точного алгоритма для 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/ |
|