На главную
ПРАВИЛА 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 @
                      есть препятствия на поле + у людей разный вес ---> различная скорость

                      Это не влияет - просто вычисляешь время в пути в соответствии с этими условиями и решаешь всё той же венгеркой.
                      Подпись была включена в связи с окончанием срока наказания
                        Я бы сделал проще, разбил на сектора, принадлежащие тому или иному убежищу и все дела.
                        Если ресурсы позволяют, можно сделать их немного перекрывающимися, для реалистичности.
                        Вот тоже намутили. ;)
                        Подпись выключена.
                          Цитата Tiranas @
                          Я бы сделал проще, разбил на сектора, принадлежащие тому или иному убежищу и все дела.
                          Ага, теперь предложи разумный алгоритм разбивки на сектора. Речь здесь идёт не об организации спасения людей в убежища (оповещении и т.п., об этом пусть ГО думает), а об оптимальном распределении их по убежищам.
                          Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                            Добрый вечер.

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

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

                              Добавлено
                              Нет, эти рёбра бесконечной стоимости просто не войдут в минимальное дерево. То есть случай, когда два человека идут в одно убежище, остаётся.
                              С минимальным деревом не получилось.
                              --------------------------------------------------------------
                              Вот что точно здесь будет работать - это алгоритм построения потока минимальной стоимости.
                              Фиктивный источник соединяется с людьми, дуги стоимости 0, пропускной способности 1.
                              Люди соединяются с убежищами, стоимость дуги = расстоюнию, пропускная способность равна 1.
                              Убежища соединяются с фиктивным стоком, дуги стоимости 0, пропускной способности 1.
                              Строим поток минимальной стоимости за то ли O(n3) , то ли O(n4), не помню.
                              Но для указанной размерности всё равно много.
                                В принципе это обычная задача о минимальном паросочетании, распределении работ или транспортная задача (в принципе все эти задачи легко сводятся друг к другу, даже Тр.З. в случае целочисленных объёмов даёт целочисленный ответ).
                                Для каждого ребра вводится вес: если надо минимизировать сумму проходимых расстояний это сами расстояния, если сумму квадратов, то квадраты расстояний.
                                Сложность представляет случай, когда минимизировать надо максимальное расстояние, так как в этом случае надо в качестве весов использовать бесконечные степени расстояний. Однако хорошее приближение получается, если использовать просто большую степень. А можно исхитриться и поработать с самими бесконечными степенями. Ведь там в алгоритмах фигурируют всего лишь суммы (разности) не более чем четырёх весов. И интерес представляют не сами суммы/разности, а только их знаки.
                                Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                                  Самый простой случай задачи на построение потока, конечно. Но при построении потока никак не используется наличие эвклидовой метрики.
                                  Только чтобы вычислить все расстояния, уже нужно O(n2)операций.
                                  Может, там и расстояния вычислять не нужно?
                                  0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                  0 пользователей:


                                  Рейтинг@Mail.ru
                                  [ Script Execution time: 0,1402 ]   [ 17 queries used ]   [ Generated: 23.10.19, 13:32 GMT ]