ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм обхода точек на плоскости за минимальное время
25 сообщений из 63, страница 1 из 3
  1  все
Алгоритм обхода точек на плоскости за минимальное время
    #38337433
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Джентльмены (и дамы, конечно), есть небольшая задачка:
Имеется массив точек на плоскости и стартовая точка
...
Рейтинг: 0 / 0
19.07.2013, 18:47
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337436
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Пардон, рука дернулась.
Задача:
Составить алгоритм обхода всех точек за минимальное время. Скорость движения можно считать постоянной, так что задача сводится к минимизации пройденного расстояния. Есть два варианта движения - одновременно по двум координатам и поочередно.

Пока в голову приходит простой алгоритм - упорядочить точки в порядке убывания расстояний от предыдущей.
Может, есть что-то эффективнее?
...
Рейтинг: 0 / 0
19.07.2013, 18:50
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337439
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Соколинский БорисЕсть два варианта движения - одновременно по двум координатам и поочередно.Вот тут чуть подробнее. "одновременно по двум координатам" - с разной скоростью по каждой из координат или с одинаковой?
...
Рейтинг: 0 / 0
19.07.2013, 18:52
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337442
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
miksoft,
В первом приближении считаем одинаковой.
...
Рейтинг: 0 / 0
19.07.2013, 18:54
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337444
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
Соедини все точки. Получишь граф. А потом берешь алгортим Дейкстры и задача решена.
...
Рейтинг: 0 / 0
19.07.2013, 18:54
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337447
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
а не, чего-то я читаю не тем глазом....
Тут не Дейкстра нужен, а http://ru.wikipedia.org/wiki/Задача_коммивояжёра
...
Рейтинг: 0 / 0
19.07.2013, 18:56
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337455
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
White Owl,
Нутром чувствовал, что надо в логистику копать.
Тут нет требования возврата в исходную точку, наверное первый алгоритм более подходящий. Я, по сути, его и имел в голове.
...
Рейтинг: 0 / 0
19.07.2013, 19:02
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337478
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Соколинский Борис,

N сильно велико? если прямым перебором, то получается порядка N! вариантов
...
Рейтинг: 0 / 0
19.07.2013, 19:27
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337486
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Соколинский Борисmiksoft,
В первом приближении считаем одинаковой.Т.е. так?
...
Рейтинг: 0 / 0
19.07.2013, 19:37
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337491
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
miksoftN сильно велико? если прямым перебором, то получается порядка N! вариантов
Не особо, 100-1000.

miksoftТ.е. так?
Да, именно. Одновременно двигаемся по двум направлениям пока не попадем в одну координату, потом до оставшейся.
...
Рейтинг: 0 / 0
19.07.2013, 19:42
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337495
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Соколинский БорисmiksoftN сильно велико? если прямым перебором, то получается порядка N! вариантов
Не особо, 100-1000.Это много, прямым перебором уже не решается :(

А что нибудь известно о характере расположения точек? Они как-то группируются? Или, например, равномерно разбросаны по квадрату? Или еще что-то?
...
Рейтинг: 0 / 0
19.07.2013, 19:46
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337501
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
miksoftЭто много, прямым перебором уже не решается :(
Почему?
Тут на N!, а N*(N-1)/2 итераций, мелочь, в общем...

miksoftА что нибудь известно о характере расположения точек? Они как-то группируются? Или, например, равномерно разбросаны по квадрату? Заранее ничего не известно.
...
Рейтинг: 0 / 0
19.07.2013, 19:52
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337521
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Соколинский БорисmiksoftЭто много, прямым перебором уже не решается :(
Почему?
Тут на N!, а N*(N-1)/2 итераций, мелочь, в общем...N*(N-1)/2 - это отрезков, которые соединяют точки.
А из них еще нужно путь собрать.
...
Рейтинг: 0 / 0
19.07.2013, 20:15
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337530
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
Нет, это при последовательном построении: выбираем первую, вторую и т.д. N! это все возможные варианты, понятно что тупым перебором не получится.
...
Рейтинг: 0 / 0
19.07.2013, 20:39
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337540
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
Соколинский БорисНет, это при последовательном построении: выбираем первую, вторую и т.д. N! это все возможные варианты, понятно что тупым перебором не получится.Ну почему-же "не получится"? Как раз только тупым перебором и может получиться.
...
Рейтинг: 0 / 0
19.07.2013, 20:55
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337557
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
White OwlНу почему-же "не получится"? Как раз только тупым перебором и может получиться.
Вообще все перебирать слишком долго. Можно, наверное, группировать точки на блоки близкорасположеных, потом оптимизировать обход блоков а затем расставлять внутри блока.
...
Рейтинг: 0 / 0
19.07.2013, 21:17
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337628
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
Соколинский БорисWhite OwlНу почему-же "не получится"? Как раз только тупым перебором и может получиться.
Вообще все перебирать слишком долго. Можно, наверное, группировать точки на блоки близкорасположеных, потом оптимизировать обход блоков а затем расставлять внутри блока.




Создать матрицу, заполнить нулями, отметить точки
Соколинский Борис и стартовая точка


значнием 1.


Самый короткий маршрут ( по диагонали ) отметить значениями -1 .

Найти самые близлежащие точки со значением 1 от почти линии отмеченной точками -1.


----------
мой блог
...
Рейтинг: 0 / 0
19.07.2013, 23:11
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337636
Фотография Малыхин Сергей
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Малыхин Сергей
Участник
Соколинский БорисНет, это при последовательном построении: выбираем первую, вторую и т.д. N! это все возможные варианты, понятно что тупым перебором не получится.
NP полная задача естественно в лоб не решается =)
нужно приближенное решение
...
Рейтинг: 0 / 0
19.07.2013, 23:28
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337641
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
Соколинский БорисWhite OwlНу почему-же "не получится"? Как раз только тупым перебором и может получиться.
Вообще все перебирать слишком долго. Можно, наверное, группировать точки на блоки близкорасположеных, потом оптимизировать обход блоков а затем расставлять внутри блока.Ну я тебе уже ткнул пальцем. Задача коммивояжера описана в куче литературы. То что у тебя путь не замкнут это все-го лишь частный вариант основной задачи.

В принципе, незамкнутый путь по всем вершинам графа имеет собственное название: Hamiltonian Path. Можешь поискать литературу по этому названию. Хотя оно тебе не много даст. На полном графе всегда можно нарисовать путь через все вершины, так что классические алгоритмы по поиску возможного пути которые быстрее чем O(n!) тебе не подойдут. Потому что тебе придется найти минимальный из всех путей, а этих путей на полном графе n!.
...
Рейтинг: 0 / 0
19.07.2013, 23:41
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337644
Фотография Малыхин Сергей
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Малыхин Сергей
Участник
имхо: вроде R-дерево строят для нахождения минимальных расстояний в координатах
...
Рейтинг: 0 / 0
19.07.2013, 23:43
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337649
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
White OwlНу я тебе уже ткнул пальцем. [/quot]Я прочитал, методов решений хороших пока не нашел.
Это задача реального времени, на весь алгоритм дается 1-2 секунды, не больше.
Поэтому варианты с O(N!) отбрасываются сразу.
...
Рейтинг: 0 / 0
19.07.2013, 23:51
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337651
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
Малыхин Сергейимхо: вроде R-дерево строят для нахождения минимальных расстояний в координатахНет. R-tree это решение другой задачи. Есть граф, найди кратчайший путь между двумя вершинами. Нет требования обхода всех вершин.
...
Рейтинг: 0 / 0
19.07.2013, 23:52
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337653
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
Соколинский БорисЭто задача реального времени, на весь алгоритм дается 1-2 секунды, не больше.
Поэтому варианты с O(N!) отбрасываются сразу.Ну тогда используй приближенное решение. Одно из самых оптимальных ты уже сам почти угадал в начале этого топика.
1) От старта найти ближайшую точку, сдвинуться,
2) Найти ближайшую не посещенную, сдвинуться
3) Если точки кончились выйти, иначе повторить шаг 2
Получишь O(n^2).
Результат может быть конечно не самым оптимальным, но чтобы это доказать понадобиться перебрать все возможные пути - O(n!). Так что можешь смело посылать всех сомневающихся в оптимальности результата :)
NP проблема это не шутки.
...
Рейтинг: 0 / 0
20.07.2013, 00:02
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337657
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Соколинский Борис
Участник
White OwlНу тогда используй приближенное решение. Одно из самых оптимальных ты уже сам почти угадал в начале этого топика.
Мне тоже так казалось, пока не начал думать :)
Мне не нравится в этом алгоритме один нюанс:
Предположим, N-1 точек располагаются на окружности, последняя - на неком удалении от нее, стартовая - в центре. Хороший алгоритм должен быть построен так, чтобы последней из точек окружности была ближайшая к (Xn,Yn). Ближайший сосед, скорее всего, выберет неоптимальный маршрут. Собс-но, из-за этого стал думать в сторону кластеризации.
...
Рейтинг: 0 / 0
20.07.2013, 00:08
| Ответить | Цитировать | Написать  
Алгоритм обхода точек на плоскости за минимальное время
    #38337667
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
Да, все верно. Но не забывай что кластеризация сама по себе потребует некоторое количество ресурсов.
...
Рейтинг: 0 / 0
20.07.2013, 00:31
| Ответить | Цитировать | Написать  
25 сообщений из 63, страница 1 из 3
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм обхода точек на плоскости за минимальное время
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=38337478&tid=1341703]:
 0ms
get settings:
 12ms
get forum list:
 19ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 412ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 74ms
get tp. blocked users:
 1ms
others: 241ms
total:  776ms
созд. / загр.: 776ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]