Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.138.200.66] |
|
Сообщ.
#1
,
|
|
|
Всем хай! Сходу к делу!
Условие задачи: - есть 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, но, очевидно, что таких "седловых" точек может быть недостаточно + надо еще учитывать одноместников как-то, т к их возраст делится пополам и добавляется к итоговому значению. Дальше мыслей вообще нет никаких. Непонятно, к чему стремится. Подскажите как быть-то, буду признателен. спс за внимание |
Сообщ.
#2
,
|
|
|
Насколько я могу судить эта задача эквивалентна задаче о назначениях, которая эквивалентна задачам о максимальном паросочетании и транспортной задаче. Соответственно подходит и метод решения этой задачи.
В исходной формулировке эта эквивалентность не видна. Поэтому немного изменим условие. Ясно, что общее количество людей в группах равно количеству одноместных номеров плюс удвоенное количество двухместных номеров (H1 + H2 = N1 + 2*N2). Это так для справки. Также H1 <= N1 + N2 и H2 <= N1 + N2. Иначе придётся селить в один номер двух человек из одной группы. А теперь само изменение. Пусть люди уже как-то расселены по номерам. Представим, что в одноместных номерах подселен фиктивный человек из другой группы. В результате получаем группы равного размера, равного общему числу номеров. В каждый номер поселяются один человек из первой группы и один из второй. Единственное ограничение - в один номер нельзя селить двух фиктивных жильцов, но оно легко решается установкой большой цены таким парам. И вот мы имеем классическую задачу о назначениях, для решения которой имеется эффективный алгоритм. |
Сообщ.
#3
,
|
|
|
1) Берём старшего из одной группы и старшего из другой группы. Селим их вместе.
2) Переход к п. 1. Оставшихся в одноместные. |
Сообщ.
#4
,
|
|
|
Цитата scrambrella @ 1) Берём старшего из одной группы и старшего из другой группы. Селим их вместе. 2) Переход к п. 1. Дурь. Группа 1 - (18, 60), группа 2 - (18), 1 одно- и 1 двухместный номер. По твоему "алгоритму" результат 51. При оптимальном расселении - 30. Добавлено Цитата FasterHarder @ - кому не хватило пары - селят в одноместные номера. Значит ли это, что количество двухместных номеров не меньше, чем количество народу в любой группе? или иными словами - значит ли это, что все люди группы, в которой меньше народу, будут поселены в двухместные номера? Это я к тому, что, например, если в одной группе 1 чел на 18, в другой 1 чел на 60, их выгоднее поселить в одноместные (39), а не в двухместный (42). |
Сообщ.
#5
,
|
|
|
Цитата Akina @ Цитата scrambrella @ 1) Берём старшего из одной группы и старшего из другой группы. Селим их вместе. 2) Переход к п. 1. Дурь. Группа 1 - (18, 60), группа 2 - (18), 1 одно- и 1 двухместный номер. По твоему "алгоритму" результат 51. При оптимальном расселении - 30. Для промышленного решения задачи и мой алгоритм пойдёт. При большом числе людей с равномерным распределением возрастов результат будет хорошим. |
Сообщ.
#6
,
|
|
|
scrambrella
Алгоритм не гарантирует оптимального решения. Более того, существует набор входных параметров, когда он даёт неоптимальное решение (что для жадных алгоритмов обычное дело, кстати). Значит, он ошибочный. Какой смысл говорить, что "а вот есть условия, когда он даст хороший результат"? Причём опять-таки - не оптимальный, а только хороший. Ну да, ну есть... |
Сообщ.
#7
,
|
|
|
Akina
Промышленный алгоритм не должен давать оптимальное решение. Он должен давать решение которое устроит пользователя. |
Сообщ.
#8
,
|
|
|
amk, спс за наводку.
Цитата amk @ Насколько я могу судить эта задача эквивалентна задаче о назначениях, которая эквивалентна задачам о максимальном паросочетании и транспортной задаче. Соответственно подходит и метод решения этой задачи. абсолютно точное попадание (как я понял позже, когда посмотрел инфу об этой задаче) Цитата amk @ А теперь само изменение. Пусть люди уже как-то расселены по номерам. Представим, что в одноместных номерах подселен фиктивный человек из другой группы. В результате получаем группы равного размера, равного общему числу номеров. это ведь синоним этого, как я понимаю: Цитата FasterHarder @ Дальше была мысль добавить фантомные вершины в одну из долей, чтобы выровнять количество вершин/людей в группах и назначить им возраст = 0. Вроде это плохая идея.. Только насчет возраста = 0 пока непонятно (но это я сам буду раскуривать потихоньку). Значит, идея была правильной, но(!) оценить адекватно идею, ну, лично мне не представляется возможным. Это проблема, да (это я за себя говорю). В итоге нашел задачу о назначениях. Это оказывается фундаментальная задача комбинаторной оптимизации, использующая взвешенный двудольный граф (а вот и графы подъехали - отлично!). И конечная точка - применить венгерский алгоритм (пару раз слышал о нем, пришла пора изучать...). Вывод для себя такой сделал: чтобы корректно решить поставленную задачу минимально из того, что надо бы знать: Из выше представленного списка мне надо раскуривать 85-90%). Работы надолго хватит... Цитата Akina @ Значит ли это, что количество двухместных номеров не меньше, чем количество народу в любой группе? как я понимаю из постановки, кол-во одно-, двухместных номером - бесконечно, т е пока есть пары, их селят в двухместные. для поста №3. Одно из фундаментальнейших свойств алгоритма - массовость (информатика 8 класс: один и тот же алгоритм должен выдавать правильный результат на любых допустимых входных данных). Akina опроверг твой "алгоритм" тривиальным примером, поэтому, применительно к данной задаче, твой "алгоритм" не является Алгоритмом. К какой-нибудь другой, да, возможно, но не к этой... amk, Akina спс за обсуждение. По данному алгоритму все понятно, точнее мало, что понятно, но понятно на 100% куда копать. Дело за малым - разобраться с этим). Вопрос решен. |
Сообщ.
#9
,
|
|
|
Цитата FasterHarder @ Вывод для себя такой сделал: чтобы корректно решить поставленную задачу минимально из того, что надо бы знать: Одного венгерского алгоритма достаточно. Тем более, что его можно реализовать просто и изящно в пару десяток строк. Добавлено Цитата FasterHarder @ как я понимаю из постановки, кол-во одно-, двухместных номером - бесконечно, т е пока есть пары, их селят в двухместные. Но это не всегда выгодно. Пару с максимальной разницей в возрасте, например, выгодней раздельно селить. |
Сообщ.
#10
,
|
|
|
Цитата FasterHarder @ для поста №3. Одно из фундаментальнейших свойств алгоритма - массовость (информатика 8 класс: один и тот же алгоритм должен выдавать правильный результат на любых допустимых входных данных). Akina опроверг твой "алгоритм" тривиальным примером, поэтому, применительно к данной задаче, твой "алгоритм" не является Алгоритмом. К какой-нибудь другой, да, возможно, но не к этой... Я дал алгоритм который можно использовать В ПРОМЫШЛЕННОСТИ для решения реальной экономической задачи. Его сложность n*log(n) а сложность задачи о назначениях n^4. Для промышленности важна не строгая оптимальность а эффективность. |
Сообщ.
#11
,
|
|
|
Цитата FasterHarder @ В моём случае неважно, как именно вычисляется недовольство для одноместных номеров. Да и для двухместных тоже. адо просто уметь вычислять это недовольство.Только насчет возраста = 0 пока непонятно В нашем случае, если оба человека реальны — берётся разность их возрастов Если оба фиктивны — любое большое число. Думаю годится возраст самого старшего. Для надёжности можно его удвоить. Если один фиктивен, другой реален — половина возраста реального. Вариант, когда число номеров бесконечно (достаточно, чтобы поселить хоть всех отдельно) задачу не усложняет, меняется лишь оценка для двух фиктивных жильцов — она обнуляется и больше не вносит вклада в общее недовольство, позволяя оставлять пустыми двухместные номера. Задача значительно усложняется, когда кроме необходимых для расселения, есть дополнительные номера. В этом случае аадача всё ещё сводится к задаче о назначениях, но придётся вводить фиктивных жильцов двух типов, один такой же как вышеописанный, а второй можно селить в двухместный номер без штрафа с таким же фиктивным из другой группы. Число таких фиктивных жильцов второго типа должно равняться числу освободждаемых даухместных номеров. Но эта задача имеет не много смысла. В реальной гостинице состав гостей заранее неизвестен. Там нужны другие подходы, так как при недостатке информации в принципе невозможно получить оптимальное решение, и целью становится получить хорошее или хотя бы удовлетворительное решение (которое постфактум может оказаться и оптимальным) с минимальной опасностью получить плохое. Цитата FasterHarder @ Именно так. Просто ты сразу перешёл к графам, и у тебя потерялись номера, как часть задачи. Поэтому стало непонятно, как и какие дополнительные вершины надо вводить. это ведь синоним этого, как я понимаю: |
Сообщ.
#12
,
|
|
|
Какое решение исходной задачи?
У меня получилось решить через алгоритм задачи о назначениях, результат - 42,5 Двухместные: 21-21, 43-46, 55-59, 39-38 Одноместные: 28, 19, 22 Итого: 0 + 3 + 4 + 1 + (28+19+22) / 2 = 42,5 |
Сообщ.
#13
,
|
|
|
Если задача еще актуальна
Решение в Excel, Симплекс методом через "Поиск решения" Можно свести исходную задачу в задачу о назначениях и решать венгерским алгоритмом Прикреплённый файл____________________.zip (8,17 Кбайт, скачиваний: 44) |