Форум на Исходниках.RU

Алгоритм спасения людей от ядерной бомбы в бомбоубежищах

swf — Sat, 20 Jul 2019 17:31:05 +0000

swf: Самый простой случай задачи на построение потока, конечно. Но при построении потока никак не используется наличие эвклидовой метрики.
Только чтобы вычислить все расстояния, уже нужно O(n²)операций.
Может, там и расстояния вычислять не нужно?

Алгоритм спасения людей от ядерной бомбы в бомбоубежищах

amk — Sat, 20 Jul 2019 15:41:18 +0000

amk: В принципе это обычная задача о минимальном паросочетании, распределении работ или транспортная задача (в принципе все эти задачи легко сводятся друг к другу, даже Тр.З. в случае целочисленных объёмов даёт целочисленный ответ).
Для каждого ребра вводится вес: если надо минимизировать сумму проходимых расстояний это сами расстояния, если сумму квадратов, то квадраты расстояний.
Сложность представляет случай, когда минимизировать надо максимальное расстояние, так как в этом случае надо в качестве весов использовать бесконечные степени расстояний. Однако хорошее приближение получается, если использовать просто большую степень. А можно исхитриться и поработать с самими бесконечными степенями. Ведь там в алгоритмах фигурируют всего лишь суммы (разности) не более чем четырёх весов. И интерес представляют не сами суммы/разности, а только их знаки.

Алгоритм спасения людей от ядерной бомбы в бомбоубежищах

swf — Sat, 13 Jul 2019 07:15:02 +0000

swf: Неправильно граф построила, извиняюсь.
Ещё надо исключить случай, когда два человека идут в одно убежище. Чтобы в такой ситуации также образовывался цикл, соединим всех людей с помощью линейного графа, стоимости рёбер + бесконечность.
Вот теперь в минимальное дерево войдёт линейный граф нулевой стоимости, соединяющий убежища, и рёбра, соединяющие людей и убежища. Можно сказать, перестановка, каждому человеку соответствует ровно одно убежище.

Добавлено 13.07.19, 07:25
Нет, эти рёбра бесконечной стоимости просто не войдут в минимальное дерево. То есть случай, когда два человека идут в одно убежище, остаётся.
С минимальным деревом не получилось.
--------------------------------------------------------------
Вот что точно здесь будет работать - это алгоритм построения потока минимальной стоимости.
Фиктивный источник соединяется с людьми, дуги стоимости 0, пропускной способности 1.
Люди соединяются с убежищами, стоимость дуги = расстоюнию, пропускная способность равна 1.
Убежища соединяются с фиктивным стоком, дуги стоимости 0, пропускной способности 1.
Строим поток минимальной стоимости за то ли O(n³) , то ли O(n⁴), не помню.
Но для указанной размерности всё равно много.

Алгоритм спасения людей от ядерной бомбы в бомбоубежищах

swf — Fri, 12 Jul 2019 19:15:25 +0000

swf: Добрый вечер.

Задачу можно свести к построению дерева минимальной стоимости.
Строим двудольный граф n (люди) X n (убежища) вершин.
Соединяем каждого человека со всеми убежищами, стоимость ребра равна расстоянию.
Убежища нумеруем и соединяем последовательно в порядке возрастания, получаем n-1 ребро, стоимость каждого ребра полагаем равной 0.
Построение графа требует O(n²)шагов.

Теперь строим каркас (стягивающее дерево) минимальной стоимости. Вроде это можно за O(lg n) сделать.
Ну, тут нужно рассмотреть способы соединения. Каждый человек должен соединяться хотя бы с одним убежищем.
Если один человек будет соединён больше чем с одним убежищем, то рёбра нулевой стоимости будут замещаться "лишними" рёбрами ненулевой стоимости.
Поэтому в минимальном стягивающем дереве каждый человек будет соединён ровно с одним убежищем, все убежища будут соединены линейным графом нулевой стоимости, и стоимость дерева равна суммарному расстоянию.

Алгоритм спасения людей от ядерной бомбы в бомбоубежищах

amk — Sat, 06 Oct 2018 19:03:54 +0000

amk:

Цитата Tiranas @ 06.10.18, 13:49

Я бы сделал проще, разбил на сектора, принадлежащие тому или иному убежищу и все дела.

Ага, теперь предложи разумный алгоритм разбивки на сектора. Речь здесь идёт не об организации спасения людей в убежища (оповещении и т.п., об этом пусть ГО думает), а об оптимальном распределении их по убежищам.

Алгоритм спасения людей от ядерной бомбы в бомбоубежищах

Tiranas — Sat, 06 Oct 2018 13:49:05 +0000

Tiranas: Я бы сделал проще, разбил на сектора, принадлежащие тому или иному убежищу и все дела.
Если ресурсы позволяют, можно сделать их немного перекрывающимися, для реалистичности.
Вот тоже намутили. ;)

Алгоритм спасения людей от ядерной бомбы в бомбоубежищах

OpenGL — Mon, 13 Aug 2018 11:21:34 +0000

OpenGL:

Цитата FasterHarder @ 13.08.18, 07:30

задача еще люто усложнится, если должно выполняться условие L(max)/L(min) <= 2 (т е отношение расстояние самого большого к самому малому не превосходит 2

Это да - вероятно, в такой формулировке без перебора не решится

Цитата FasterHarder @ 13.08.18, 07:30

есть препятствия на поле + у людей разный вес ---> различная скорость

Это не влияет - просто вычисляешь время в пути в соответствии с этими условиями и решаешь всё той же венгеркой.

Алгоритм спасения людей от ядерной бомбы в бомбоубежищах

Akina — Mon, 13 Aug 2018 10:17:30 +0000

Akina:

Цитата FasterHarder @ 13.08.18, 06:49

спастись должны ВСЕ люди, т е все N человек

В условии этого нет. А что они там хотят - дело десятое. Ну да ладно.

Цитата FasterHarder @ 13.08.18, 07:30

+ есть препятствия на поле + у людей разный вес ---> различная скорость перемещения

Не влияет, от слова "совсем". На этапе построения ты препятствия учитываешь, а скорости тут в принципе не влияют (впрочем, если ставится задача достижения убежища не более чем за заданное время - просто те убежища, что для заданного чела далековаты при его скорости, объявляются недостижимыми...) - либо вместо расстояний критерием становится время достижения.

Цитата FasterHarder @ 13.08.18, 07:30

задача еще люто усложнится, если должно выполняться условие L(max)/L(min) <= 2 (т е отношение расстояние самого большого к самому малому не превосходит 2)

Скорее наоборот - ведь при этом часть маршрутов (те, что длиннее двух текущих минимумов) просто объявляются недостижимыми. Если решение не найдено - минимум объявляется недостижимым, и выполняется пересчёт с новыми условиями. В принципе это просто изменение порядка просчёта по переборному алгоритму, да к тому же сопровождающееся уменьшением количества значимых элементов матрицы.

В принципе можно взять такую интерпретацию решения - менять местами строки (столбцы), минимизируя сумму элементов главной диагонали.

Алгоритм спасения людей от ядерной бомбы в бомбоубежищах

FasterHarder — Mon, 13 Aug 2018 07:30:23 +0000

FasterHarder:

Цитата MBo @ 13.08.18, 07:21

Задача называется Euclidean assignment problem или Euclideam bipartite (perfect) matching problem.

Судя по тому, что проблему 250 лет изучают, и всё ищут приличные эвристики, она не проста.

о! спс. MBo за науку ;)
Ну, то бишь, нужно смотреть в сторону "Венгерского" алгоритма.

ЗЫ: как я понимаю, задача еще люто усложнится, если должно выполняться условие L(max)/L(min) <= 2 (т е отношение расстояние самого большого к самому малому не превосходит 2) + есть препятствия на поле + у людей разный вес ---> различная скорость перемещения

Алгоритм спасения людей от ядерной бомбы в бомбоубежищах

MBo — Mon, 13 Aug 2018 07:21:27 +0000

MBo: Задача называется Euclidean assignment problem или Euclideam bipartite (perfect) matching problem.

Судя по тому, что проблему 250 лет изучают, и всё ищут приличные эвристики, она не проста.

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

На e-maxx упоминается "улучшенная реализация", которая использует построенное эвристически какое-то решение и оптимизирует его. Не знаю, насколько это ускорит в данном случае.

Алгоритм спасения людей от ядерной бомбы в бомбоубежищах

OpenGL — Mon, 13 Aug 2018 07:14:04 +0000

OpenGL:

Оффтоп

Это вообще странный критерий - минимальность суммы расстояний. Логичнее минимизировать максимальное расстояние. И то только при условии, что все люди идут с одинаковой скоростью :D

Алгоритм спасения людей от ядерной бомбы в бомбоубежищах

FasterHarder — Mon, 13 Aug 2018 06:49:37 +0000

FasterHarder: Akina
)

Цитата Akina @ 13.08.18, 04:29

То есть оптимальным НЕ подразумевается спасение максимально возможного количества людей?

спастись должны ВСЕ люди, т е все N человек!

Алгоритм спасения людей от ядерной бомбы в бомбоубежищах

Akina — Mon, 13 Aug 2018 04:29:44 +0000

Akina:

Цитата FasterHarder @ 12.08.18, 20:20

Под оптимальностью понимается, что суммарное расстояние пройденной всеми людьми будет МИНИМАЛЬНЫМ.

То есть оптимальным НЕ подразумевается спасение максимально возможного количества людей?

В таком случае решение тривиально. Никто никуда не бежит, расстояние равно нулю, меньше некуда. Всё.

Алгоритм спасения людей от ядерной бомбы в бомбоубежищах

OpenGL — Mon, 13 Aug 2018 04:06:27 +0000

OpenGL: Пока в голову приходит только Задача о назначениях. Ограничения для неё великоваты, но это по крайней мере полиномиальное решение.

Алгоритм спасения людей от ядерной бомбы в бомбоубежищах

Славян — Mon, 13 Aug 2018 01:10:36 +0000

Славян:

Цитата FasterHarder @ 12.08.18, 20:20

4. Взять 1-го человека и найти от него ближайшее бомбоубежище, потом 2-го и для него найти ближайшее и т.д. Но вроде это чешуя

Да, плохой способ. Достаточно посмотреть на прямой:
2 бомбоубежища: 0 и 2; 2 человека 1+ε и K(большое).
Получится по этому алгоритму: d = 2-(1+ε) + K = K+1-ε, а настоящее минимальное (первый пошёл в 0) будет: 1+ε + K-2 = K-1 + ε, что короче (ε - мало́)! (Чтобы всё было в целых можно отмасштабировать).

Добавлено 13.08.18, 01:30

Цитата FasterHarder @ 12.08.18, 20:20

2. Использовать графы. Но какого типа графа? И какой алгоритм применить?

Элементарно Гамильтонов цикл:
1. Меж всеми бомбоубежищами делаем архикрохотное расстояние (в графе устанавливаем расстояние для ребра), меж всеми людьми тоже.
2. Ищем гамильтонов цикл, глядя на который получаем нужные пары.
3. Для целочисленности всё надо будет сильно отмасштабировать!.. :)

Алгоритм спасения людей от ядерной бомбы в бомбоубежищах

FasterHarder — Sun, 12 Aug 2018 20:20:12 +0000

FasterHarder: Всем хай! Сходу к делу!
Постановка задачи: на координатной бесконечной плоскости есть N человек и N бомбоубежищ (10 <= N <= 1 000 000)! Все эти объекты (чел. и бомбуб.) задаются двумя целочисленными координатами (x, y). В одно бомбоубежище помещается строго один человек. В случае ядерного удара все люди типа хотят остаться в живых и спрятаться в бомбоубежищах. Нужно оптимальным образом доставить каждого человека до бомбоубежища. Под оптимальностью понимается, что суммарное расстояние пройденной всеми людьми будет МИНИМАЛЬНЫМ.

я хотел поинтересоваться насчет алгоритма:
1. Понятно, что можно запустить полный перебор, но для случая N = 1 000 000 получаем N! вариантов - не вариант, т к потребуются "миллиарды" лет для перебора)
2. Использовать графы. Но какого типа графа? И какой алгоритм применить?
3. Что-то мутить на списках с последующей сортировкой.
4. Взять 1-го человека и найти от него ближайшее бомбоубежище, потом 2-го и для него найти ближайшее и т.д. Но вроде это чешуя + нужно доказать, что это даст оптимальное решение.

Подскажите, куда копать, что грызть...