Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3859487 Mon, 21 Feb 2022 13:56:55 +0000 Поиск минимальной суммы на биграфе https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3859487 Решение в Excel, Симплекс методом через "Поиск решения"
Можно свести исходную задачу в задачу о назначениях и решать венгерским алгоритмом
____________________.zip (, : 88) ]]> m-ch Алгоритмы https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3857652 Fri, 14 Jan 2022 05:30:44 +0000 Поиск минимальной суммы на биграфе https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3857652 У меня получилось решить через алгоритм задачи о назначениях, результат - 42,5
Двухместные: 21-21, 43-46, 55-59, 39-38
Одноместные: 28, 19, 22

Итого: 0 + 3 + 4 + 1 + (28+19+22) / 2 = 42,5]]> m-ch Алгоритмы https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3856202 Sun, 12 Dec 2021 10:59:17 +0000 Поиск минимальной суммы на биграфе https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3856202 Цитата FasterHarder @
Только насчет возраста = 0 пока непонятно
В моём случае неважно, как именно вычисляется недовольство для одноместных номеров. Да и для двухместных тоже. адо просто уметь вычислять это недовольство.
В нашем случае, если оба человека реальны — берётся разность их возрастов
Если оба фиктивны — любое большое число. Думаю годится возраст самого старшего. Для надёжности можно его удвоить.
Если один фиктивен, другой реален — половина возраста реального.

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

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

Цитата FasterHarder @
это ведь синоним этого, как я понимаю:
Именно так. Просто ты сразу перешёл к графам, и у тебя потерялись номера, как часть задачи. Поэтому стало непонятно, как и какие дополнительные вершины надо вводить.]]> amk Алгоритмы https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855827 Tue, 07 Dec 2021 16:00:19 +0000 Поиск минимальной суммы на биграфе https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855827 Цитата FasterHarder @
для поста №3. Одно из фундаментальнейших свойств алгоритма - массовость (информатика 8 класс: один и тот же алгоритм должен выдавать правильный результат на любых допустимых входных данных). Akina опроверг твой "алгоритм" тривиальным примером, поэтому, применительно к данной задаче, твой "алгоритм" не является Алгоритмом. К какой-нибудь другой, да, возможно, но не к этой...

Я дал алгоритм который можно использовать В ПРОМЫШЛЕННОСТИ для решения реальной экономической задачи. Его сложность n*log(n) а сложность задачи о назначениях n^4. Для промышленности важна не строгая оптимальность а эффективность.]]> scrambrella Алгоритмы https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855812 Tue, 07 Dec 2021 13:39:11 +0000 Поиск минимальной суммы на биграфе https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855812 Цитата FasterHarder @
Вывод для себя такой сделал: чтобы корректно решить поставленную задачу минимально из того, что надо бы знать:

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

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

Но это не всегда выгодно. Пару с максимальной разницей в возрасте, например, выгодней раздельно селить.]]> OpenGL Алгоритмы https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855787 Tue, 07 Dec 2021 10:01:45 +0000 Поиск минимальной суммы на биграфе https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855787 amk, спс за наводку.

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

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

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

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

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

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

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

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

Цитата Akina @

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

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

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

amk, Akina спс за обсуждение. По данному алгоритму все понятно, точнее мало, что понятно, но понятно на 100% куда копать. Дело за малым - разобраться с этим).
Вопрос решен.]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855782 Tue, 07 Dec 2021 09:46:09 +0000 Поиск минимальной суммы на биграфе https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855782 Akina
Промышленный алгоритм не должен давать оптимальное решение. Он должен давать решение которое устроит пользователя.]]> scrambrella Алгоритмы https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855769 Tue, 07 Dec 2021 08:12:45 +0000 Поиск минимальной суммы на биграфе https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855769 scrambrella
Алгоритм не гарантирует оптимального решения. Более того, существует набор входных параметров, когда он даёт неоптимальное решение (что для жадных алгоритмов обычное дело, кстати). Значит, он ошибочный.

Какой смысл говорить, что "а вот есть условия, когда он даст хороший результат"? Причём опять-таки - не оптимальный, а только хороший. Ну да, ну есть...]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855758 Tue, 07 Dec 2021 06:26:51 +0000 Поиск минимальной суммы на биграфе https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855758 Цитата Akina @
Цитата scrambrella @
1) Берём старшего из одной группы и старшего из другой группы. Селим их вместе.
2) Переход к п. 1.

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

Для промышленного решения задачи и мой алгоритм пойдёт. При большом числе людей с равномерным распределением возрастов результат будет хорошим.]]> scrambrella Алгоритмы https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855756 Tue, 07 Dec 2021 05:28:00 +0000 Поиск минимальной суммы на биграфе https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855756 Цитата scrambrella @
1) Берём старшего из одной группы и старшего из другой группы. Селим их вместе.
2) Переход к п. 1.

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

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

Значит ли это, что количество двухместных номеров не меньше, чем количество народу в любой группе? или иными словами - значит ли это, что все люди группы, в которой меньше народу, будут поселены в двухместные номера?
Это я к тому, что, например, если в одной группе 1 чел на 18, в другой 1 чел на 60, их выгоднее поселить в одноместные (39), а не в двухместный (42).]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855739 Mon, 06 Dec 2021 18:53:45 +0000 Поиск минимальной суммы на биграфе https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855739 2) Переход к п. 1.

Оставшихся в одноместные.]]> scrambrella Алгоритмы https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855735 Mon, 06 Dec 2021 18:12:40 +0000 Поиск минимальной суммы на биграфе https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855735
В исходной формулировке эта эквивалентность не видна. Поэтому немного изменим условие.
Ясно, что общее количество людей в группах равно количеству одноместных номеров плюс удвоенное количество двухместных номеров (H1 + H2 = N1 + 2*N2). Это так для справки.
Также H1 <= N1 + N2 и H2 <= N1 + N2. Иначе придётся селить в один номер двух человек из одной группы.

А теперь само изменение. Пусть люди уже как-то расселены по номерам. Представим, что в одноместных номерах подселен фиктивный человек из другой группы. В результате получаем группы равного размера, равного общему числу номеров. В каждый номер поселяются один человек из первой группы и один из второй. Единственное ограничение - в один номер нельзя селить двух фиктивных жильцов, но оно легко решается установкой большой цены таким парам. И вот мы имеем классическую задачу о назначениях, для решения которой имеется эффективный алгоритм.]]> amk Алгоритмы https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855706 Mon, 06 Dec 2021 16:06:34 +0000 Поиск минимальной суммы на биграфе https://forum.sources.ru/index.php?showtopic=424548&view=findpost&p=3855706
Условие задачи:
- есть 2 группы людей;
- возраст любого человека в любой группе из отрезка [18; 60];
- количество людей в группах может быть различным;
- есть гостиница с одноместными и двухместными номерами;
- в двухместные номера разрешено селить людей ТОЛЬКО из разных групп;
- кому не хватило пары - селят в одноместные номера.

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

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

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

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

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

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

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

спс за внимание]]> FasterHarder Алгоритмы