OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Воскресенье, 08 Декабрь, 2019 12:02

Часовой пояс: UTC + 3 часа




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

Зарегистрирован: Четверг, 17 Ноябрь, 2005 11:51
Сообщения: 2933
Откуда: г. Ярославль
Вот, озаботился я прокладкой маршрута по карте. Пока что нахожусь в процессе сбора информации по теме, но уже захотелось иметь в перспективе компонент для BlackBox :)

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Картография
СообщениеДобавлено: Среда, 02 Сентябрь, 2009 18:58 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9162
Откуда: Россия, Орёл
Под картой понимается граф транспортной сети типа городской?
Тогда это просто поиск кратчайшего пути в графе.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Картография
СообщениеДобавлено: Среда, 02 Сентябрь, 2009 20:53 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8209
Откуда: Троицк, Москва
Илья Ермаков писал(а):
просто поиск кратчайшего пути в графе.
Реальные задачи могут и не быть такими простыми. И часто не бывают.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Картография
СообщениеДобавлено: Среда, 02 Сентябрь, 2009 21:25 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9162
Откуда: Россия, Орёл
Ну да.
Тут стоит ввести хотя бы оценку не только длины звена, но и загруженности (а это наверняка понадобится, если я правильно догадываюсь, откуда ноги растут :) ). То уже интересно.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Картография
СообщениеДобавлено: Среда, 02 Сентябрь, 2009 21:45 

Зарегистрирован: Четверг, 17 Ноябрь, 2005 11:51
Сообщения: 2933
Откуда: г. Ярославль
Нужно проложить маршрут от точки А в точку Б по городским улицам и посчитать длину маршрута.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Картография
СообщениеДобавлено: Среда, 02 Сентябрь, 2009 22:40 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Поиск кратчайших путей это ерунда (можно даже чуть-чуть быстрее Дейкстровского N Log N если памяти не жалко), вот задача коммивояжёра другое дело.

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Картография
СообщениеДобавлено: Среда, 02 Сентябрь, 2009 22:54 
Аватара пользователя

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Картография
СообщениеДобавлено: Четверг, 03 Сентябрь, 2009 15:23 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3124
Откуда: Астрахань
А уж я - обязательно почитал бы ... :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Картография
СообщениеДобавлено: Четверг, 03 Сентябрь, 2009 18:23 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Как таковой публикации нет, только на форумах algolist-а трепался, там ни кому не нужно было.

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

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


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


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


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

-------

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Картография
СообщениеДобавлено: Четверг, 03 Сентябрь, 2009 18:38 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Сергей Губанов писал(а):
Первый вариант пути вычисляется как угодно, например, жадным алгоритмом. Потом пытаемся уменьшить длину пути перебирая всевозможные перестановки в двух парах точек, затем пробуем все трёхпарные перестановки, потом все четырёхпарные, и так далее.


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Картография
СообщениеДобавлено: Четверг, 03 Сентябрь, 2009 19:11 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8209
Откуда: Троицк, Москва
Сергей Юрьевич, напишите текст и просто хотя бы выложите в соотв. раздел в архиве http://arxiv.org/corr/home


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Картография
СообщениеДобавлено: Четверг, 03 Сентябрь, 2009 22:04 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Как найду свободное время напишу, выложу. Там ведь на русском тоже можно выкладывать?

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Картография
СообщениеДобавлено: Четверг, 03 Сентябрь, 2009 22:43 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8209
Откуда: Троицк, Москва
Сергей Губанов писал(а):
Там ведь на русском тоже можно выкладывать?
Нет, на русском нельзя. Но усилие приложить стоит.[/quote]

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

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


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: Alexey_Donskoy и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2019, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB