|
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
|
|
Алгоритм поиска минимального расстояния между объектами29.04.2021, 16:12. Показов 3433. Ответов 21
Метки нет (Все метки)
Пишу простенькую демку, где одни объекты (назовем их "осами") гоняются за другими ("мухи").
"Мухи" летают хаотично, а "осы" должны выбрать для себя ближайшую цель и гоняться за ней. При этом: 1. "Оса" должна догонять ближайшую к себе "муху" только в том случае, если ее не догоняет другая "оса", которая находится еще ближе. В этом случае "оса" должна выбрать следующую по дистанции "муху", с учетом этого же условия - никакая другая "оса" не должна быть ближе к предполагаемой "мухе". Если не получается найти подходящую "муху" - "оса" пропускает ход. 2. "Укушенная" "муха" на некоторое время превращается в "осу" и начинает гоняться за своими бывшими "коллегами" (с учетом условия описанного в п. 1). Объектов может быть достаточно много, ориентировочно - несколько сотен. Я накидал приблизительный алгоритм реализации п.1 - он рекурсивно вычисляет расстояние от одного объекта до ближайшего. Примерно так: 1. Берем очередную "осу". 2. Перебираем всех "мух", вычисляя расстояние, оставляем "муху" с минимальным расстоянием. 3. Далее перебираем всех "ос" уже от "мухи", найденной в п.2, оставляем "осу" с минимальным расстоянием. 4. Если "оса" из п.1 совпадает с "осой" из п.2 - то пара найдена, она помечается и исключается из дальнейших поисков. 5. Если нет - повторяем пп. 2 - 3, меняя местами "ос" и "мух" и вычисляя таким образом пару с минимальным расстоянием. 6. "Оса", оставшаяся без пары, пропускает ход. Алгоритм получился дико громоздким, запутанным и очень медленным. Настолько медленным, что он просто не годится. Как я понимаю, нужен оптимальный алгоритм поиска минимального расстояния между объектами, находящихся в разных множествах. Может, кто-то что-то посоветует?
0
|
|
| 29.04.2021, 16:12 | |
|
Ответы с готовыми решениями:
21
Определение расстояния между объектами Вычисление расстояния между объектами Расчёт расстояния между географическими объектами |
|
Модератор
3133 / 2280 / 469
Регистрация: 26.03.2015
Сообщений: 8,874
|
||
| 29.04.2021, 16:52 | ||
|
Добавлено через 2 минуты Если оса может гнаться мухой, только если никакая другая оса не ближе к мухе... То для каждой мухи находим осу, которая может за ней гнаться. Группируем получившиеся пары по осам и для каждой выбираем ближайшую муху из группы.
0
|
||
|
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
|
|||
| 29.04.2021, 17:19 [ТС] | |||
|
С другой стороны, если к "мухе1" приблизилась "оса2" на меньшее расстояние, чем "оса1" (или "муха1" сблизилась с "осой2"), то "оса1" должна искать другую ближайшую "муху", а "оса2" будет гоняться за "мухой1". Другими словами, в круге диаметром "осаN" - "мухаM" и центром в половине расстояния между ними, не должно быть ни одного другого объекта. Один из моих пробных алгоритмов я так и реализовывал. Брал очередную "осу" и "расширял" от нее круг, пока туда не попадал какой-то другой объект. Если это была "муха" - то пара была найдена. А если другая "оса" - то переключался на нее, рисовал круг, ожидал "муху", и так далее, пока не находил пару "оса-муха". Возвращался к предыдущим "кругам" и продолжал искать, исключив найденную пару. Вот, к примеру, я беру "муху1" и ищу ближайшую "осу". Нашел. Но нет никакой гарантии, что для "мухиN" эта "оса" не окажется ближе. Т.е., мне все равно приходится дополнительно проверять остальные объекты.
0
|
|||
|
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
|
|
| 29.04.2021, 17:33 [ТС] | |
|
Вот, например, такая ситуация (мухи - зеленые, осы - красные):
1. Если искать от Мухи1, то ближайшая - Оса1. 2. Но к Осе1 Муха3 ближе. 3. Но к Мухе3 ближе Оса2. Т.е., после всех вычислений расклад должен получится такой: 1. Оса2-Муха3 2. Оса1-Муха1 (но это выяснится после нахождения пары в п.1) 3. Оса3-Муха2 (по остаточному принципу).
0
|
|
|
698 / 572 / 75
Регистрация: 20.09.2014
Сообщений: 3,700
|
|
| 29.04.2021, 18:28 | |
|
Если критерий - минимальное время для покусания всех мух, то предыстория гоняния за мухами не должна определять то, как в текущий момент осы должны перераспределиться.
Добавлено через 2 минуты Но это если осы не обладают инерцией. Мы ничего не знаем про физику полета, скорости и т.п. Добавлено через 9 секунд Но это если осы не обладают инерцией. Мы ничего не знаем про физику полета, скорости и т.п.
0
|
|
|
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
|
||
| 29.04.2021, 19:07 [ТС] | ||
|
Предыстория вообще не должна ни на что влиять. Каждый ход каждая "оса" должна выбрать цель. При этом совершенно не важно, за кем эта "оса" гонялась в прошлом ходу.
0
|
||
|
698 / 572 / 75
Регистрация: 20.09.2014
Сообщений: 3,700
|
|||
| 29.04.2021, 19:22 | |||
|
0
|
|||
|
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
|
|||
| 29.04.2021, 19:43 [ТС] | |||
|
Под расстоянием я имею ввиду следующее: sqrt((X1-X2)^2+(Y1-Y2)^2). Для ускорения процесса я корень квадратный не беру. Но сам факт того, что это - не статичная картинка и не разовый расчет, требует оптимального алгоритма. Объекты должны двигаться с визуально приемлемой скоростью.
0
|
|||
|
698 / 572 / 75
Регистрация: 20.09.2014
Сообщений: 3,700
|
|
| 29.04.2021, 19:48 | |
|
Вы поняли про пары расстояний 1,0 и 1,0; 0,0001 и 100000? Это не координаты, это уже вычисленные варианты евклидовых расстояний (по вашей формуле). Что лучше?
0
|
|
|
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
|
||
| 29.04.2021, 19:50 [ТС] | ||
|
0
|
||
|
698 / 572 / 75
Регистрация: 20.09.2014
Сообщений: 3,700
|
|
| 29.04.2021, 19:53 | |
|
Задача с одной мухой и одной осой тривиальна.))) А кто-то уже наверняка моделирует уравнения движений мух и ос по второму закону Ньютона.)
0
|
|
|
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
|
||
| 29.04.2021, 23:36 [ТС] | ||
|
Оса1 в верхнем левом углу, Оса2 ближе к центру. Муха1 ближе к центру, Муха2 в нижнем правом углу. Если искать от Осы1, то ближайшая Муха - это Муха1. Но за ней должна гоняться Оса2, а Оса1 должна гоняться за Мухой2, хотя она дальше. А если Мух и Ос несколько сотен, то расчеты перестают быть томными.
0
|
||
|
Модератор
3133 / 2280 / 469
Регистрация: 26.03.2015
Сообщений: 8,874
|
||||
| 30.04.2021, 01:42 | ||||
|
Добавлено через 4 минуты
1
|
||||
|
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
|
|||
| 30.04.2021, 01:47 [ТС] | |||
|
0
|
|||
|
4523 / 1899 / 336
Регистрация: 18.01.2021
Сообщений: 3,489
|
|
| 30.04.2021, 10:41 | |
|
Самый тупой способ.
1.Составляем матрицу расстояний от i-й осы до j-й мухи. 2.Находим глобальный минимум. Присваиваем соответствующей осе соответствующую муху 3.Удаляем строку и столбец с этим минимумом. 4.Переходим к шагу 2. Все это можно было бы оптимизировать, если бы у нас этих объектов миллион был. А до тысячи все и так мгновенно вычисляется. Так что и заморачиваться не стоит.
0
|
|
|
Модератор
3133 / 2280 / 469
Регистрация: 26.03.2015
Сообщений: 8,874
|
|||
| 30.04.2021, 10:55 | |||
|
Оса2 ближе к Мухе2, но, не смотря на это, Оса1 должна гоняться за Мухой2 (так как Оса2 занята другой мухой)
0
|
|||
|
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
|
||
| 30.04.2021, 11:11 [ТС] | ||
|
1. К Осе1 ближе Муха1, чем Муха2. 2. Но поскольку Оса2 ближе к Мухе1, чем Оса1, то за Мухой1 будет гоняться Оса2. 3. А Осе2 остается Муха2.
0
|
||
|
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
|
||
| 30.04.2021, 11:24 [ТС] | ||
|
И каждый ход это пересчитывать - будет очень медленно. Я пробовал такой способ. Умножение - медленная операция, а для каждого расстояния ее нужно по два раза выполнять (вместо возведения в квадрат я умножение использую).
0
|
||
|
4523 / 1899 / 336
Регистрация: 18.01.2021
Сообщений: 3,489
|
|
| 30.04.2021, 11:57 | |
|
Это
В приведенном случае потребуется посчитать 200*50=10000 расстояний. А потом 50 раз провести поиск минимума в этом массиве. Итого 500 000. Копейки. Добавлено через 26 минут На самом деле еще меньше, потому что второй поиск производится уже в массиве 199х49, третий в 198х48 и т.д. То есть количество операций будет еще в 2 раза меньше.
0
|
|
|
4523 / 1899 / 336
Регистрация: 18.01.2021
Сообщений: 3,489
|
||||||
| 01.05.2021, 01:56 | ||||||
|
Код на яве.
Кликните здесь для просмотра всего текста
Swap 0 to fly 87 Swap 1 to fly 334 Swap 2 to fly 83 Swap 3 to fly 440 Swap 4 to fly 269 Swap 5 to fly 402 Swap 6 to fly 495 Swap 7 to fly 427 Swap 8 to fly 420 Swap 9 to fly 406 Время выполнения - 0.2337157с Я сознательно сделал основное тело программы в более-менее универсальном коде, без всяких примочек, потоков и распараллеливаний. Как видите, самый примитивный код для 500мух/500 ос отрабатывает за доли секунды на моем не самом быстром ноуте.
1
|
||||||
| 01.05.2021, 01:56 | |
|
Помогаю со студенческими работами здесь
20
Как включить показ расстояния между объектами? API для определения расстояния между объектами Нужен скрипт, реагирующий на расстояния между объектами Измерение минимального расстояния между отрезками в пространстве
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
||||
|
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Налог на собак: https:/ / **********/ gallery/ V06K53e
Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf
Пост отсюда. . .
|
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop?
Ниже её машинный перевод.
После долгих разбирательств я наконец-то вернула себе. . .
|
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод
Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод.
Thinkpad X220 Tablet —. . .
|
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта
Симптом:
После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
|
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
|
|
Новый ноутбук
volvo 07.12.2025
Всем привет.
По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне:
Ryzen 5 7533HS
64 Gb DDR5
1Tb NVMe
16" Full HD Display
Win11 Pro
|
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
|
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
|
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов
На странице:
https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/
нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
|
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов.
. . .
|