На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: shadeofgray, JoeUser
  
> Алгоритм спасения людей от ядерной бомбы в бомбоубежищах
Всем хай! Сходу к делу!
Постановка задачи: на координатной бесконечной плоскости есть N человек и N бомбоубежищ (10 <= N <= 1 000 000)! Все эти объекты (чел. и бомбуб.) задаются двумя целочисленными координатами (x, y). В одно бомбоубежище помещается строго один человек. В случае ядерного удара все люди типа хотят остаться в живых и спрятаться в бомбоубежищах. Нужно оптимальным образом доставить каждого человека до бомбоубежища. Под оптимальностью понимается, что суммарное расстояние пройденной всеми людьми будет МИНИМАЛЬНЫМ.

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

Подскажите, куда копать, что грызть...
I originate
You must appreciate, all the others imitate

SCOOTER "GUEST LIST"

'Pon the mic I'm the teacher!
Spread my words like a preacher!
Yiiihhaaaa!!!!

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

Добавлено
Цитата FasterHarder @
2. Использовать графы. Но какого типа графа? И какой алгоритм применить?
Элементарно Гамильтонов цикл:
1. Меж всеми бомбоубежищами делаем архикрохотное расстояние (в графе устанавливаем расстояние для ребра), меж всеми людьми тоже.
2. Ищем гамильтонов цикл, глядя на который получаем нужные пары.
3. Для целочисленности всё надо будет сильно отмасштабировать!.. :)
Пока в голову приходит только Задача о назначениях. Ограничения для неё великоваты, но это по крайней мере полиномиальное решение.
Подпись была включена в связи с окончанием срока наказания
Цитата FasterHarder @
Под оптимальностью понимается, что суммарное расстояние пройденной всеми людьми будет МИНИМАЛЬНЫМ.

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

В таком случае решение тривиально. Никто никуда не бежит, расстояние равно нулю, меньше некуда. Всё.
Есть претензии ко мне как к модератору? читайте Правила, разделы 5 и 6, и действуйте соответственно.
Есть претензии ко мне как к участнику? да ради бога.
Не нравятся мои ответы? не читайте их.
В общем, берегите себя. Нервные клетки не восстанавливаются.
Akina
)

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

спастись должны ВСЕ люди, т е все N человек!
I originate
You must appreciate, all the others imitate

SCOOTER "GUEST LIST"

'Pon the mic I'm the teacher!
Spread my words like a preacher!
Yiiihhaaaa!!!!

SCOOTER "WEEKEND"
Оффтоп
Это вообще странный критерий - минимальность суммы расстояний. Логичнее минимизировать максимальное расстояние. И то только при условии, что все люди идут с одинаковой скоростью :D
Подпись была включена в связи с окончанием срока наказания
Задача называется Euclidean assignment problem или Euclideam bipartite (perfect) matching problem.

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

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

На e-maxx упоминается "улучшенная реализация", которая использует построенное эвристически какое-то решение и оптимизирует его. Не знаю, насколько это ускорит в данном случае.
Цитата MBo @
Задача называется Euclidean assignment problem или Euclideam bipartite (perfect) matching problem.

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


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

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

SCOOTER "GUEST LIST"

'Pon the mic I'm the teacher!
Spread my words like a preacher!
Yiiihhaaaa!!!!

SCOOTER "WEEKEND"
Цитата FasterHarder @
спастись должны ВСЕ люди, т е все N человек

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

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

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

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

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

В принципе можно взять такую интерпретацию решения - менять местами строки (столбцы), минимизируя сумму элементов главной диагонали.
Есть претензии ко мне как к модератору? читайте Правила, разделы 5 и 6, и действуйте соответственно.
Есть претензии ко мне как к участнику? да ради бога.
Не нравятся мои ответы? не читайте их.
В общем, берегите себя. Нервные клетки не восстанавливаются.
Цитата FasterHarder @
задача еще люто усложнится, если должно выполняться условие L(max)/L(min) <= 2 (т е отношение расстояние самого большого к самому малому не превосходит 2

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

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

Это не влияет - просто вычисляешь время в пути в соответствии с этими условиями и решаешь всё той же венгеркой.
Подпись была включена в связи с окончанием срока наказания
1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
0 пользователей:


Рейтинг@Mail.ru
[ Script Execution time: 0,1367 ]   [ 19 queries used ]   [ Generated: 15.08.18, 03:41 GMT ]