На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS

Дорогие друзья!
Поздравляем вас с Новым 2022 годом!
Всем ЗДОРОВЬЯ, удачи, успеха и благополучия!

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

    Условие задачи:
    - есть 2 группы людей;
    - возраст любого человека в любой группе из отрезка [18; 60];
    - количество людей в группах может быть различным;
    - есть гостиница с одноместными и двухместными номерами;
    - в двухместные номера разрешено селить людей ТОЛЬКО из разных групп;
    - кому не хватило пары - селят в одноместные номера.

    Есть понятие "индекс недовольства", который рассчитывается как разность (модуль) возраста людей, заселенных в один двухместный номер. Для тех, кто живет в одноместном номере, этот индекс равен половине возраста проживающего.

    На вход подается количество людей в каждой группе и возрасты каждого. Требуется найти наименьший суммарный показатель недовольства (сумма показателей всех номеров).
    P.S. Есть требование: решать при помощи графового(графовых) алгоритмов.
    -------------------------------------------------------------------------------
    Решил решать на конкретном примере.
    1 группа(желтая; 4 человека): 21, 43, 55, 39
    2 группа(синяя; 7 человек): 28, 19, 59, 46, 38, 21, 22

    Надо рассматривать все возможные связи каждого человека из 1й группы с каждый из 2ой группы, в итоге получилась такая картина:
    Прикреплённая картинка
    Прикреплённая картинка

    Это ведь двудольный граф (биграф)? Да, это он похоже. И что...
    Дальше была мысль добавить фантомные вершины в одну из долей, чтобы выровнять количество вершин/людей в группах и назначить им возраст = 0. Вроде это плохая идея..

    Поскольку индекс недовольства - разность, значит, надо составить "весовую" матрицу индексов недовольства. В качестве строк - например, возраст людей из 1й группы, колонок - из 2й группы, получилась такая прямоугольная матрица:
    Прикреплённая картинка
    Прикреплённая картинка


    Почти уверен, что это оч.полезная штука для последующего решения.

    И была мысль искать "седловые" точки, т е точки, значения которых минимальны и в строке и в колонке одновременно!
    Например, это [21; 21] = 0 или [43; 46] = 3, но, очевидно, что таких "седловых" точек может быть недостаточно + надо еще учитывать одноместников как-то, т к их возраст делится пополам и добавляется к итоговому значению.

    Дальше мыслей вообще нет никаких. Непонятно, к чему стремится.
    Подскажите как быть-то, буду признателен.

    спс за внимание
      Насколько я могу судить эта задача эквивалентна задаче о назначениях, которая эквивалентна задачам о максимальном паросочетании и транспортной задаче. Соответственно подходит и метод решения этой задачи.

      В исходной формулировке эта эквивалентность не видна. Поэтому немного изменим условие.
      Ясно, что общее количество людей в группах равно количеству одноместных номеров плюс удвоенное количество двухместных номеров (H1 + H2 = N1 + 2*N2). Это так для справки.
      Также H1 <= N1 + N2 и H2 <= N1 + N2. Иначе придётся селить в один номер двух человек из одной группы.

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

        Оставшихся в одноместные.
        Сообщение отредактировано: scrambrella -
          Цитата scrambrella @
          1) Берём старшего из одной группы и старшего из другой группы. Селим их вместе.
          2) Переход к п. 1.

          Дурь.
          Группа 1 - (18, 60), группа 2 - (18), 1 одно- и 1 двухместный номер.
          По твоему "алгоритму" результат 51. При оптимальном расселении - 30.

          Добавлено
          Цитата FasterHarder @
          - кому не хватило пары - селят в одноместные номера.

          Значит ли это, что количество двухместных номеров не меньше, чем количество народу в любой группе? или иными словами - значит ли это, что все люди группы, в которой меньше народу, будут поселены в двухместные номера?
          Это я к тому, что, например, если в одной группе 1 чел на 18, в другой 1 чел на 60, их выгоднее поселить в одноместные (39), а не в двухместный (42).
          Сообщение отредактировано: Akina -
            Цитата Akina @
            Цитата scrambrella @
            1) Берём старшего из одной группы и старшего из другой группы. Селим их вместе.
            2) Переход к п. 1.

            Дурь.
            Группа 1 - (18, 60), группа 2 - (18), 1 одно- и 1 двухместный номер.
            По твоему "алгоритму" результат 51. При оптимальном расселении - 30.

            Для промышленного решения задачи и мой алгоритм пойдёт. При большом числе людей с равномерным распределением возрастов результат будет хорошим.
              scrambrella
              Алгоритм не гарантирует оптимального решения. Более того, существует набор входных параметров, когда он даёт неоптимальное решение (что для жадных алгоритмов обычное дело, кстати). Значит, он ошибочный.

              Какой смысл говорить, что "а вот есть условия, когда он даст хороший результат"? Причём опять-таки - не оптимальный, а только хороший. Ну да, ну есть...
                Akina
                Промышленный алгоритм не должен давать оптимальное решение. Он должен давать решение которое устроит пользователя.
                  amk, спс за наводку.

                  Цитата amk @
                  Насколько я могу судить эта задача эквивалентна задаче о назначениях, которая эквивалентна задачам о максимальном паросочетании и транспортной задаче. Соответственно подходит и метод решения этой задачи.

                  абсолютно точное попадание :yes: (как я понял позже, когда посмотрел инфу об этой задаче)

                  Цитата amk @
                  А теперь само изменение. Пусть люди уже как-то расселены по номерам. Представим, что в одноместных номерах подселен фиктивный человек из другой группы. В результате получаем группы равного размера, равного общему числу номеров.

                  это ведь синоним этого, как я понимаю:
                  Цитата FasterHarder @
                  Дальше была мысль добавить фантомные вершины в одну из долей, чтобы выровнять количество вершин/людей в группах и назначить им возраст = 0. Вроде это плохая идея..

                  Только насчет возраста = 0 пока непонятно (но это я сам буду раскуривать потихоньку). Значит, идея была правильной, но(!) оценить адекватно идею, ну, лично мне не представляется возможным. Это проблема, да (это я за себя говорю).

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

                  И конечная точка - применить венгерский алгоритм (пару раз слышал о нем, пришла пора изучать...).

                  Вывод для себя такой сделал: чтобы корректно решить поставленную задачу минимально из того, что надо бы знать:
                  • транспортная задача;
                  • нахождение потока минимальной стоимости;
                  • методы линейного программирования;
                  • биграф;
                  • венгерский алгоритм(!!).
                  Из выше представленного списка мне надо раскуривать 85-90%). Работы надолго хватит...

                  Цитата Akina @

                  Значит ли это, что количество двухместных номеров не меньше, чем количество народу в любой группе?

                  как я понимаю из постановки, кол-во одно-, двухместных номером - бесконечно, т е пока есть пары, их селят в двухместные.

                  для поста №3. Одно из фундаментальнейших свойств алгоритма - массовость (информатика 8 класс: один и тот же алгоритм должен выдавать правильный результат на любых допустимых входных данных). Akina опроверг твой "алгоритм" тривиальным примером, поэтому, применительно к данной задаче, твой "алгоритм" не является Алгоритмом. К какой-нибудь другой, да, возможно, но не к этой...

                  amk, Akina спс за обсуждение. По данному алгоритму все понятно, точнее мало, что понятно, но понятно на 100% куда копать. Дело за малым - разобраться с этим).
                  Вопрос решен.
                    Цитата FasterHarder @
                    Вывод для себя такой сделал: чтобы корректно решить поставленную задачу минимально из того, что надо бы знать:

                    Одного венгерского алгоритма достаточно. Тем более, что его можно реализовать просто и изящно в пару десяток строк.

                    Добавлено
                    Цитата FasterHarder @
                    как я понимаю из постановки, кол-во одно-, двухместных номером - бесконечно, т е пока есть пары, их селят в двухместные.

                    Но это не всегда выгодно. Пару с максимальной разницей в возрасте, например, выгодней раздельно селить.
                      Цитата FasterHarder @
                      для поста №3. Одно из фундаментальнейших свойств алгоритма - массовость (информатика 8 класс: один и тот же алгоритм должен выдавать правильный результат на любых допустимых входных данных). Akina опроверг твой "алгоритм" тривиальным примером, поэтому, применительно к данной задаче, твой "алгоритм" не является Алгоритмом. К какой-нибудь другой, да, возможно, но не к этой...

                      Я дал алгоритм который можно использовать В ПРОМЫШЛЕННОСТИ для решения реальной экономической задачи. Его сложность n*log(n) а сложность задачи о назначениях n^4. Для промышленности важна не строгая оптимальность а эффективность.
                        Цитата FasterHarder @
                        Только насчет возраста = 0 пока непонятно
                        В моём случае неважно, как именно вычисляется недовольство для одноместных номеров. Да и для двухместных тоже. адо просто уметь вычислять это недовольство.
                        В нашем случае, если оба человека реальны — берётся разность их возрастов
                        Если оба фиктивны — любое большое число. Думаю годится возраст самого старшего. Для надёжности можно его удвоить.
                        Если один фиктивен, другой реален — половина возраста реального.

                        Вариант, когда число номеров бесконечно (достаточно, чтобы поселить хоть всех отдельно) задачу не усложняет, меняется лишь оценка для двух фиктивных жильцов — она обнуляется и больше не вносит вклада в общее недовольство, позволяя оставлять пустыми двухместные номера.

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

                        Цитата FasterHarder @
                        это ведь синоним этого, как я понимаю:
                        Именно так. Просто ты сразу перешёл к графам, и у тебя потерялись номера, как часть задачи. Поэтому стало непонятно, как и какие дополнительные вершины надо вводить.
                          Какое решение исходной задачи?
                          У меня получилось решить через алгоритм задачи о назначениях, результат - 42,5
                          Двухместные: 21-21, 43-46, 55-59, 39-38
                          Одноместные: 28, 19, 22

                          Итого: 0 + 3 + 4 + 1 + (28+19+22) / 2 = 42,5
                          1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                          0 пользователей:


                          Рейтинг@Mail.ru
                          [ Script execution time: 0,0372 ]   [ 16 queries used ]   [ Generated: 21.01.22, 11:31 GMT ]