Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.80/15: Рейтинг темы: голосов - 15, средняя оценка - 4.80
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
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
29.04.2021, 16:12
Ответы с готовыми решениями:

Определение расстояния между объектами
Вообщем есть задача следующая: нужно определить расстояние от одного объекта до нескольких других. Возможные варианты реализации: ...

Вычисление расстояния между объектами
Есть 2 класса: Class1 и Class2 От Class2 наследуются классы Class2_1, Class2_2, Class2_3 Есть несколько объектов Class1 (стоят на...

Расчёт расстояния между географическими объектами
Доброго времени суток. Усть географические координаты точек в файле. В цикле они считываются, затем происходит обращение к...

21
Модератор
Эксперт функциональных языков программирования
3133 / 2280 / 469
Регистрация: 26.03.2015
Сообщений: 8,874
29.04.2021, 16:52
Цитата Сообщение от Constcat Посмотреть сообщение
с учетом этого же условия - никакая другая "оса" не должна быть ближе к предполагаемой "мухе"
Не следует из указанного условия. В условии "не гонится". То есть, оса1 может быть ближе к мухе2, чем оса2, но гнаться за мухой1. Почему в этом случае осе2 не погнаться за мухой2?

Добавлено через 2 минуты
Если оса может гнаться мухой, только если никакая другая оса не ближе к мухе... То для каждой мухи находим осу, которая может за ней гнаться. Группируем получившиеся пары по осам и для каждой выбираем ближайшую муху из группы.
0
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
29.04.2021, 17:19  [ТС]
Цитата Сообщение от Shamil1 Посмотреть сообщение
Не следует из указанного условия. В условии "не гонится". То есть, оса1 может быть ближе к мухе2, чем оса2, но гнаться за мухой1. Почему в этом случае осе2 не погнаться за мухой2?
Наверное, я невнятно объяснил. "Оса1" гонится за "мухой1". Если в процессе погони "муха2" стала ближе - "оса1" должна переключиться на "муху2".

С другой стороны, если к "мухе1" приблизилась "оса2" на меньшее расстояние, чем "оса1" (или "муха1" сблизилась с "осой2"), то "оса1" должна искать другую ближайшую "муху", а "оса2" будет гоняться за "мухой1".

Другими словами, в круге диаметром "осаN" - "мухаM" и центром в половине расстояния между ними, не должно быть ни одного другого объекта.

Один из моих пробных алгоритмов я так и реализовывал. Брал очередную "осу" и "расширял" от нее круг, пока туда не попадал какой-то другой объект. Если это была "муха" - то пара была найдена. А если другая "оса" - то переключался на нее, рисовал круг, ожидал "муху", и так далее, пока не находил пару "оса-муха". Возвращался к предыдущим "кругам" и продолжал искать, исключив найденную пару.
Цитата Сообщение от Shamil1 Посмотреть сообщение
Если оса может гнаться мухой, только если никакая другая оса не ближе к мухе... То для каждой мухи находим осу, которая может за ней гнаться.
Так тоже не совсем получается.
Вот, к примеру, я беру "муху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  [ТС]
Цитата Сообщение от Mikhaylo Посмотреть сообщение
Если критерий - минимальное время для покусания всех мух, то предыстория гоняния за мухами не должна определять то, как в текущий момент осы должны перераспределиться.
Критерий - минимальное расстояние. Никакой инерции нет. Все объекты делают один ход за один демо-цикл. "Мухи" ходят первыми, "осы" - после них. "Мухи" двигаются по случайным траекториям, каждая "оса" должна двигаться за ближайшей "мухой", при условии, что расстояние от это "мухи" до любой другой "осы" больше.
Предыстория вообще не должна ни на что влиять. Каждый ход каждая "оса" должна выбрать цель. При этом совершенно не важно, за кем эта "оса" гонялась в прошлом ходу.
0
698 / 572 / 75
Регистрация: 20.09.2014
Сообщений: 3,700
29.04.2021, 19:22
Цитата Сообщение от Constcat Посмотреть сообщение
Критерий - минимальное расстояние.
У нас не одна скалярная величина, а целый вектор расстояний. А критерий к вектору не применим. Ибо непонятно, что лучше: два расстояния 1,0 и 1,0 или другие два расстояния 0,0001 и 1000000. Понимаете? Обычно в таком случае уточняют, что именно у векторов сравнивать. Подсказка: например, евклидову длину векторов, либо как расстояние Минковского, либо простую сумму модулей координат вектора....

Цитата Сообщение от Constcat Посмотреть сообщение
Все объекты делают один ход за один демо-цикл.
Может просто рассмотреть один цикл и не говорить о том, что мухи летают и делают это хаотично, это задачи вообще не касается и сбивает с толку.
0
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
29.04.2021, 19:43  [ТС]
Цитата Сообщение от Mikhaylo Посмотреть сообщение
У нас не одна скалярная величина, а целый вектор расстояний. А критерий к вектору не применим. Ибо непонятно, что лучше: два расстояния 1,0 и 1,0 или другие два расстояния 0,0001 и 1000000. Понимаете? Обычно в таком случае уточняют, что именно у векторов сравнивать. Подсказка: например, евклидову длину векторов, либо как расстояние Минковского, либо простую сумму модулей координат вектора....
Что-то вы как-то усложняете...
Под расстоянием я имею ввиду следующее: sqrt((X1-X2)^2+(Y1-Y2)^2). Для ускорения процесса я корень квадратный не беру.
Цитата Сообщение от Mikhaylo Посмотреть сообщение
Может просто рассмотреть один цикл и не говорить о том, что мухи летают и делают это хаотично, это задачи вообще не касается и сбивает с толку.
Разумеется. Собственно, так и происходит - я считаю расстояния для неподвижных объектов.
Но сам факт того, что это - не статичная картинка и не разовый расчет, требует оптимального алгоритма. Объекты должны двигаться с визуально приемлемой скоростью.
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  [ТС]
Цитата Сообщение от Mikhaylo Посмотреть сообщение
Вы поняли про пары расстояний 1,0 и 1,0; 0,0001 и 100000? Это не координаты, это уже вычисленные варианты евклидовых расстояний (по вашей формуле).
Нет, не понял. У меня объекты расположены в плоскости с заданными ограничениями по X и Y. Для меня расстояние между двумя объектами однозначно определяются вышеуказанной формулой.
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  [ТС]
Цитата Сообщение от Mikhaylo Посмотреть сообщение
Задача с одной мухой и одной осой тривиальна.)))
А с двумя мухами и двумя осами уже не настолько тривиальна:
Оса1 в верхнем левом углу, Оса2 ближе к центру. Муха1 ближе к центру, Муха2 в нижнем правом углу.
Если искать от Осы1, то ближайшая Муха - это Муха1. Но за ней должна гоняться Оса2, а Оса1 должна гоняться за Мухой2, хотя она дальше.

А если Мух и Ос несколько сотен, то расчеты перестают быть томными.
0
Модератор
Эксперт функциональных языков программирования
3133 / 2280 / 469
Регистрация: 26.03.2015
Сообщений: 8,874
30.04.2021, 01:42
Цитата Сообщение от Constcat Посмотреть сообщение
Но нет никакой гарантии, что для "мухиN" эта "оса" не окажется ближе.
Группируем получившиеся пары по осам и для каждой выбираем ближайшую муху из группы.

Добавлено через 4 минуты
Цитата Сообщение от Constcat Посмотреть сообщение
Но за ней должна гоняться Оса2, а Оса1 должна гоняться за Мухой2, хотя она дальше.
Цитата Сообщение от Constcat Посмотреть сообщение
с учетом этого же условия - никакая другая "оса" не должна быть ближе к предполагаемой "мухе".
Противоречие.
1
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
30.04.2021, 01:47  [ТС]
Цитата Сообщение от Shamil1 Посмотреть сообщение
Противоречие.
Да нет же. Я пытался объяснить, что, несмотря на то, что Муха1 ближе к Осе1, чем Муха2, но Оса1 должна будет гоняться за Мухой2, т.к, за Мухой1 будет гоняться Оса2 (т.к. она ближе).

Цитата Сообщение от Shamil1 Посмотреть сообщение
Группируем получившиеся пары по осам и для каждой выбираем ближайшую муху из группы.
Над этим я подумаю, спасибо!
0
Эксперт Python
 Аватар для Red white socks
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
Цитата Сообщение от Constcat Посмотреть сообщение
никакая другая "оса" не должна быть ближе к предполагаемой "мухе"
Цитата Сообщение от Constcat Посмотреть сообщение
Оса1 должна будет гоняться за Мухой2
Правильно ли я понимаю итоговый вариант:
Оса2 ближе к Мухе2, но, не смотря на это, Оса1 должна гоняться за Мухой2 (так как Оса2 занята другой мухой)
0
242 / 208 / 36
Регистрация: 19.02.2021
Сообщений: 1,431
30.04.2021, 11:11  [ТС]
Цитата Сообщение от Shamil1 Посмотреть сообщение
Оса2 ближе к Мухе2, но, не смотря на это, Оса1 должна гоняться за Мухой2 (так как Оса2 занята другой мухой)
(Мухи - зеленые, Осы - красные)
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  [ТС]
Цитата Сообщение от Red white socks Посмотреть сообщение
1.Составляем матрицу расстояний от i-й осы до j-й мухи.
А можно подробнее? У нас есть, допустим, 200 Мух и 50 Ос. Как по мне, это не матрица будет, а что-то типа графов. От каждой к каждой.
И каждый ход это пересчитывать - будет очень медленно. Я пробовал такой способ. Умножение - медленная операция, а для каждого расстояния ее нужно по два раза выполнять (вместо возведения в квадрат я умножение использую).
0
Эксперт Python
 Аватар для Red white socks
4523 / 1899 / 336
Регистрация: 18.01.2021
Сообщений: 3,489
30.04.2021, 11:57
Это https://www.cyberforum.ru/cgi-bin/latex.cgi?N^3 алгоритм. Наверняка можно оптимизировать и до https://www.cyberforum.ru/cgi-bin/latex.cgi?N^{2+\varepsilon}, но по вашим данным этого не требуется.
В приведенном случае потребуется посчитать 200*50=10000 расстояний. А потом 50 раз провести поиск минимума в этом массиве. Итого 500 000. Копейки.

Добавлено через 26 минут
На самом деле еще меньше, потому что второй поиск производится уже в массиве 199х49, третий в 198х48 и т.д. То есть количество операций будет еще в 2 раза меньше.
0
Эксперт Python
 Аватар для Red white socks
4523 / 1899 / 336
Регистрация: 18.01.2021
Сообщений: 3,489
01.05.2021, 01:56
Код на яве.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public class WaspAndFly {
 
    public static int WASPCOUNT = 500;
    public static int FLYCOUNT = 500;
    static final long START = System.nanoTime();
    static final double NANO = 1000000000;
 
    public static void main(String[] args) {
        double[][] waspCoord = new double[WASPCOUNT][2];
        double[][] flyCoord = new double[FLYCOUNT][2];
        for (int i = 0; i < WASPCOUNT; i++) {
            waspCoord[i][0] = Math.random();
            waspCoord[i][1] = Math.random();
        }
        for (int i = 0; i < FLYCOUNT; i++) {
            flyCoord[i][0] = Math.random();
            flyCoord[i][1] = Math.random();
        }
        //формируем матрицу расстояний
        double[][] distanceSquare = new double[WASPCOUNT][FLYCOUNT];
        for (int i = 0; i < WASPCOUNT; i++) {
            for (int j = 0; j < FLYCOUNT; j++) {
                distanceSquare[i][j] = Math.pow(waspCoord[i][0] - flyCoord[j][0], 2) + Math.pow(waspCoord[i][1] - flyCoord[j][1], 2);
            }
        }
        Map<Integer, Integer> swapToFly = new HashMap();//сюда складываем найденные соответствия
        //формируем 2 списка с нераспределенными осами и мухами
        ArrayList<Integer> swapFree = IntStream.range(0, WASPCOUNT).collect(ArrayList::new, ArrayList::add, ArrayList::addAll);
        ArrayList<Integer> flyFree = IntStream.range(0, FLYCOUNT).collect(ArrayList::new, ArrayList::add, ArrayList::addAll);
        //основная часть алгоритма. Ищем пару с минимальным расстоянием
        while (!swapFree.isEmpty() && !flyFree.isEmpty()) {
            double minDistance = Double.MAX_VALUE;
            int flyMin = 0;
            int swapMin = 0;
            for (Integer i : swapFree) {
                for (Integer j : flyFree) {
                    if (distanceSquare[i][j] < minDistance) {
                        minDistance = distanceSquare[i][j];
                        flyMin = j;
                        swapMin = i;
                    }
                }
            }
            swapToFly.put(swapMin, flyMin); //добавляем найденное соответствие
            //исключаем пару из дальнейшего рассмотрения
            swapFree.remove(Integer.valueOf(swapMin)); 
            flyFree.remove(Integer.valueOf(flyMin));
        }
        //Выводим найденные соответствия (10 значений)
        swapToFly.entrySet().stream()
                .limit(10)
                .collect(Collectors.toMap(p -> p.getKey(), p -> p.getValue()))
                .forEach((k, v) -> System.out.println("Swap " + k + " to fly " + v));
        System.out.println("Время выполнения - " + (System.nanoTime() - START) / NANO + "с");
    }
}
Результат выполнения
Кликните здесь для просмотра всего текста

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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
01.05.2021, 01:56
Помогаю со студенческими работами здесь

Как включить показ расстояния между объектами?
Не высвечивается расстояние между объектами, когда их двигаешь. Как включить? Вот мои настройки (скрин). Спасибо.

API для определения расстояния между объектами
Всем привет! Стоит задача создать калькулятор расчета грузоперевозки. Сейчас столкнулся с проблемой, как рассчитать расстояние от объекта к...

Нужен скрипт, реагирующий на расстояния между объектами
Подскажите пожалуйста нужен скрипт который будет реагировать на расстояния между обьектами, к примеру этот обьект до которого считать...

Измерение минимального расстояния между отрезками в пространстве
Подскажите пожалуйста, как измерить коротчайшее расстояние между двумя отрезками в пространстве в AutoCAD? Даны четыре точки с такими...

Нахождение минимального расстояния между двумя точками
ЗАДАЧА: Даны два множества A и B, состоящие из N1 и N2 (вводятся с клавиатуры) точек соответственно (точки заданы своими координатами на...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
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
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru