Задача на размещение
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Задача на размещение - 2009-05-25 20:55:08.860000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
В одном небольшом институте одного небольшого города решили в один день провести конференции по физике и по химии. Как оказалось, набор желающий принять участие в обоих конференциях значительно превысил вместимость институтских аудиторий, поэтому было принято решение отдавать аудитории "химикам" и "физикам" по мере регистрации участников. Однако, все аудитории имеют разную вместимость, и может получиться, например, так, что 10 физиков займут аудиторию на 300 человек, а химиков некуда будет разместить даже при том, что в целом в институте всё ещё будет оставаться 290 свободных мест, а этих десятерых физиков можно было бы свободно посадить в какой-нибудь маленькой аудитории, скажем, на 30 человек, занятой химиками.
Задача: разместить максимальное количество желающих при этом не делая "смешанных" аудиторий.
Т. е., на входе имеем последовательность символов Х (химики) и Ф (физики), а также список аудиторий с указанием их вместимости. На выходе получить состояние системы, при котором происходит первый отказ символу из последовательности.
|
|
|
|
|
RE: Задача на размещение - 2009-05-25 21:49:24.360000
|
|
|
gotoxardas
Сообщений: 842
Оценки: 0
Присоединился: 2007-05-25 08:15:21.840000
|
Какие ограничения по количеству аудиторий?
|
|
|
|
|
RE: Задача на размещение - 2009-05-25 23:19:05.510000
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Ограничения ни при чём :). Классическая задача по мат. статистике на распределение.
|
|
|
|
|
RE: Задача на размещение - 2009-05-25 23:25:29.260000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: gotoxardas
Какие ограничения по количеству аудиторий?
Никаких. От одной до бесконечности.
quote:
ORIGINAL: gotoxardas
Ограничения ни при чём :). Классическая задача по мат. статистике на распределение.
Не вижу связи со статистикой или распределением.
|
|
|
|
|
RE: Задача на размещение - 2009-05-26 13:06:53.520000
|
|
|
gotoxardas
Сообщений: 842
Оценки: 0
Присоединился: 2007-05-25 08:15:21.840000
|
Обычная олимпиадная задача. Желательная асимптотика какая? От этого алгоритм решения зависит. С виду динамикой решается, если копать глубже то хз, нужна асимптотика.
|
|
|
|
|
RE: Задача на размещение - 2009-05-26 14:16:50.250000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Задача из жизни, а не с олимпиады, так что возможно несколько решений с различной асимптотикой. Сразу отбрасываются только алгоритмы с экспоненциальным порядком роста. Все остальные можешь предлагать.
|
|
|
|
|
RE: Задача на размещение - 2009-05-30 04:10:25.536666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Так что, ни одного варианта? :)
|
|
|
|
|
RE: Задача на размещение - 2009-05-30 09:55:39.910000
|
|
|
gotoxardas
Сообщений: 842
Оценки: 0
Присоединился: 2007-05-25 08:15:21.840000
|
Так то, что без асимптотики на это уйдет времени раз в 5 больше. Задача не из легчайших, мягко говоря.
Да, и хотя бы пару тестов дал, для более детального понимания задачи.
|
|
|
|
|
RE: Задача на размещение - 2009-05-30 18:01:11.996666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
А ты при написании реальных программ знаешь асимптотику своего будущего алгоритма?
Для тестов можешь сам написать простейшую программу для генерации случайной последовательности символом 'Х' и 'Ф'. Как при этом представлять аудитории - тоже твой выбор. Я бы делал массив int'ов, каждый элемент которого представляет вместимость аудитории.
|
|
|
|
|
RE: Задача на размещение - 2009-05-30 18:13:42.960000
|
|
|
gotoxardas
Сообщений: 842
Оценки: 0
Присоединился: 2007-05-25 08:15:21.840000
|
quote:
ORIGINAL: kreol
А ты при написании реальных программ знаешь асимптотику своего будущего алгоритма?
Для тестов можешь сам написать простейшую программу для генерации случайной последовательности символом 'Х' и 'Ф'. Как при этом представлять аудитории - тоже твой выбор. Я бы делал массив int'ов, каждый элемент которого представляет вместимость аудитории.
Для большего понимания напишу, как я решаю задачи подобного рода. Во-первых - эта задача на разработку эффективного алгоритма, то есть точно такая же, как и олимпиадная. Во-вторых, на олимпиадных задачах, которые решаю я, всегда указываются граничные максимальные значение входных данных, по которым легко определяется асимптотика. В-третьих, там всегда дается пару тестов для понимания того, что от тебя конкретно требуется, и в каком виде это надо считывать, решать и выводить. Для примера предлагаю зайти на topcoder.com и посмотреть то, о чем я написал. Просто я сейчас не до конца могу понять или понять вообще не правильно то, что от меня требуется написать, если нет элементарных тестов.
|
|
|
|
|
RE: Задача на размещение - 2009-05-30 21:45:00.516666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
Во-первых - эта задача на разработку эффективного алгоритма, то есть точно такая же, как и олимпиадная.
Вот поэтому я терпеть не могу спортивное программирование - подход к решению изначально неправильный. Понять, что от тебя требуется? Ну смотри, твой дядя - организатор конференции. Он пока не знает, сколько и каких аудиторий ему выделит руководство. Тем более он не знает, в какой последовательности будут прибывать химики и физики, но руководство заранее сказало: "Планируй так, чтобы влезло максимальное количество людей". Твой дядя просёк, что нужно это автоматизировать и пришёл к тебе. Ты можешь задавать ему любые вопросы по поводу организации конференции, но ни про какие асимптотики он не знает, и какие тебе тесты предоставлять - тоже. От тебя требуется помочь дяде организовать конференцию так, чтобы начальноство осталось довольно.
|
|
|
|
|
RE: Задача на размещение - 2009-05-31 01:21:41.563333
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
Напоминает задачу о рюкзаке… NP Hard?
|
|
|
|
|
RE: Задача на размещение - 2009-05-31 01:30:11.110000
|
|
|
Vary
Сообщений: 31
Оценки: 0
Присоединился: 2009-02-19 15:33:19.930000
|
на вскидку не особо заморачиваясь вот что могу сказать(если канеш я правильно понял что требуется):
- разбираем строку аудиторий на интегерный массив с вместимостями, к нему делаем маркировочный массив;
- по строке символов Х/Ф определяем кол-во химиков/физиков(пусть это переменные kolH и kolF);
- смотрим кого больше, потом берем самую большую аудиторию и пихаем их туда. Не поместившихся пишем в соответствующий kol. поюзанную аудиторию выбрасываем из поля зрения(метим нулем в маркировочном массиве);
- повторяем предыдущий шаг пока аудитории не кончатся или пока kol'ы не обнулятся;
- печатаем аудитории с количествами в них сидящих.
как-то так. если что - поправьте. если ограничений нет - массив берем по максимуму и надеемся на благоразумие составителей тестов))
|
|
|
|
|
RE: Задача на размещение - 2009-05-31 03:58:33.120000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: rgo
Напоминает задачу о рюкзаке… NP Hard?
Я тоже сначала подумал про рюкзак, но здесь не к чему привязать удельную стоимость. Насчёт класса неуверен, возможно есть и решение из P-класса.
quote:
ORIGINAL: Vary
на вскидку не особо заморачиваясь вот что могу сказать(если канеш я правильно понял что требуется):
…
Ну вот примерно к такому же приближённому алгоритму и я пришёл. Вопрос в том, как это математически обосновать?
|
|
|
|
|
RE: Задача на размещение - 2009-05-31 04:02:01.936666
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
здесь вообще нет задачи
если перемещать людей после размещения нельзя, то оптимальное решение отсутствует. берёшь две самых вместительных аудитории, и надеешься что тебе повезёт и ты угадаешь верно. ни эвристики, ни эмпирических данных у тебя нет. угадайка
если перемещать можно, то задача тривиальна - берёшь две самых вместительных аудитории, и набираешь их до окончания места в одной из них. далее сравниваешь вместительность, и либо меняешь местами их содержимое (если место осталось в большей), либо начинаешь отправлять людей в следующую по величине аудиторию. получишь оптимальное размещение в каждый фиксированный момент времени
здесь была бы задача на knapsack packing (опять же, тривиально решаемая динамическим программированием), если бы тебе изначально было известно количество неразбиваемых групп людей и размеры этих групп. количество тебе дано (химики и физики), размеров ты не знаешь
|
|
|
|
|
RE: Задача на размещение - 2009-05-31 16:10:11.630000
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
Я понимаю задачу таким образом. Мы знаем всё о том, какие группы физиков и химиков надо распихивать по аудиторям. Все группы занумерованы от 1 и до N. Наша задача либо распихать все N групп по аудиториям, либо распихать m групп (m < N) с номерами 1,2,…,m и заявить что больше не влезет. Понятно дело, что m должно быть наибольшим при данных условиях. Причём решать эту задачу мы должны в пристойное время. Ну, я думаю, полчаса – это максимум. Как я понимаю, дядя будет сидеть в своём кабинете, принимать очередную группу физиков/химиков, которые пришли записаться и записывать. Ну либо он будет, рассыпаясь в извинениях, говорить им что места больше нет. Соответственно, полчаса можно поразвлекать очередную группу желающую записаться. Но часов пять – это будет уж слишком жёстко.
quote:
здесь была бы задача на knapsack packing (опять же, тривиально решаемая динамическим программированием), если бы тебе изначально было известно количество неразбиваемых групп людей и размеры этих групп.
Ну я и не утверждаю, что это задача о рюкзаке в чистом виде. Но если мы взяли самую большую аудиторию, и пытаемся вместить туда как можно больше химиков, причём заталкиваем их туда неделимыми группами, то это та самая задача в чистом виде.
Насчёт "тривиально решаемая"… А, ну да. Ну да, ну да. Решаемая! В pseudo-polynomial время. Правда в этом есть и свои минусы ;). Если бы рюкзак не решался, можно было бы, наверное, доказать что и эта не решается, и со спокойной совестью искать подходящее решение, вместо полного*. А вот решаемость рюкзака, нам ничего не говорит о решаемости данной задачи в полиномиальное время.
*) Мне почему-то кажется, что данная задача решается дольше чем рюкзак. То есть, если рюкзак решается в O(f(n)) время, то и эта тоже в O(f(n)).
quote:
Ну вот примерно к такому же приближённому алгоритму и я пришёл. Вопрос в том, как это математически обосновать?
А никак. Ведь предложенный алгоритм не позволяет найти лучшее размещение по аудиториям*. То есть такое, которое максимизирует m. Вероятно, он позволит найти подходящее решение. То которое вместит достаточно много, чтобы человек с первого взгляда не видел бы как вместить больше. Но обосновать математически тот факт, что человек с первого (второго/третьего…) взгляда не найдёт лучшего решения – невозможно.
При желании можно просто поговорить об удачности алгоритма. О том как он тратя минимум ресурсов находит очень неплохие решения задачи. Обычно так и делается в подобных ситуациях. А если кто-то сомневается, он может проверить на практике. Эта проверка как раз более-менее формализуется. Садиться человек (или человеки), которые решают задачу. И компьютер решает параллельно им. Их решения сравниваются. И там, в принципе, всё становиться ясно.
*) если я правильно понял. Изложение хромает, и оставляет место вопросам. Но я попробую привести пример, когда алгоритм выдаст не лучший вариант размещения. Ну скажем, три аудитории, одна на 5 мест и две на четыре. И есть четыре группы химиков по 2 человека, и две группы физиков, одна 2 человека, другая 3. Алгоритм говорит что раз химиков больше, то им надо выделить аудиторию в пять мест. Но это ведь не так. В данной ситуации, единственный способ разместить всех – это запихнуть всех физиков в аудиторию на пять рыл, а химикам отдать все остальные.
kreol. Честно говоря, то если бы меня дядя попросил бы решить такую задачу, то первым моим вопросом ему (ты ведь разрешил задавать вопросы дяде?) было бы "сколько аудиторий, и какой они вместимости? Список в студию, пжалста!". Дальше я бы поспрошал о распределении размера группы. Здесь под распределением я подразумеваю понятие из матстатистики. Ну, дядя, вряд ли заранее сможет мне точно сказать сколько групп и какого размера будет, но что-то об этом он сможет сказать всенепременно. А потом я бы я задумался возможности решения в срок методом тупого перебора вариантов. Пускай компьютера работает. Время программиста стоит больше процессорного. ;)
Я бы забил на спорт, на возможность существования лучшего алгоритма и прочую лабуду. Об этом стоит думать, если планируется программу заставлять работать много раз, или если даже на одно выполнение программы уйдёт столько времени, что к моменту её завершения полученное решение будет неактуальным.
|
|
|
|
|
RE: Задача на размещение - 2009-05-31 23:17:37.953333
|
|
|
Vary
Сообщений: 31
Оценки: 0
Присоединился: 2009-02-19 15:33:19.930000
|
штот вы мудрите. тут надо подходить просто - вот это дано, вотэто надо получить, как на олимпе по программированию. у нас есть инфа о кол-ве физиков и химиков, и не важно какими группами мы их рапихиваем по аудиториям и нужно ли их перемещать в процессе распределения. ограничений нет,важен результат, я так понимаю
quote:
ORIGINAL: kreol
Вопрос в том, как это математически обосновать?
ну это уже вопрос к математикам а не к кодерам))
|
|
|
|
|
RE: Задача на размещение - 2009-06-01 00:05:17.423333
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
ты добавил в задачу "неделимые группы" химиков и физиков, которых в условии не было, в результате действительно получил вариант задачи о рюкзаке (усложнённый запретом на смешанные аудитории). и что? можно было вместо этого добавить ещё "престижность аудитории" и "ЧСВ участников" и в результате решать вариант задачи о лабиринте
я по-прежнему считаю, что в данном изложении условия задача отсутствует. делать домыслы о недостающих ограничениях или данных можно сколько угодно
|
|
|
|
|
RE: Задача на размещение - 2009-06-01 00:06:59.233333
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: Vary
ну это уже вопрос к математикам а не к кодерам
complexity theory (теория сложности) является разделом computer science, так что аргумент не в тему
|
|
|
|
|
RE: Задача на размещение - 2009-06-01 01:15:02.200000
|
|
|
Vary
Сообщений: 31
Оценки: 0
Присоединился: 2009-02-19 15:33:19.930000
|
quote:
ORIGINAL: Denaturat
complexity theory (теория сложности) является разделом computer science, так что аргумент не в тему
да все это понятно что программист должен сечь в математике, знать теорию сложности, варить кофе, ходить по канату, вышивать крестиком итд…. я редложил решение, а к примеру ты чем мне претензии предъявлять обоснуй, если знаешь computer science лучше меня(я-то названия даже не знал^^)
|
|
|
|
|
RE: Задача на размещение - 2009-06-01 01:18:34.950000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Ок, поясняю. Регистрация производиться в динамическом режиме, положим, онлайн. Нам нужно при каждом обращении проверять, можем ли мы ещё принять нового участника, или ему следует отказать. Ответ нужен быстро, поэтому перебор не катит. Сколько именно групп придёт, нас тоже не волнует. Если пришли одни химики, заняли все аудитории, и после этого появился первый физик, то он в пролёте - конференция будет сугубо химическая. Массовая регистрация (чтобы были неделимые группы) запрещена. Сколько аудиторий - пока неизвестно (ну, или если не нравится такая формулировка, то программа должна быть приспособлена под разные конференции или даже разные институты). Как будут прибывать люди - тоже хз, во всяком случае на это нельзя полагаться.
Вы пока пообсуждайте, а я чуть позже оценю предложеные варианты с вашего позволения. А то приболел немного и сейчас с трудом могу оценить ответы, а тем более слелать по ним логические суждения без доли бреда.
|
|
|
|
|
RE: Задача на размещение - 2009-06-01 12:17:19.663333
|
|
|
gotoxardas
Сообщений: 842
Оценки: 0
Присоединился: 2007-05-25 08:15:21.840000
|
quote:
ORIGINAL: kreol
Ок, поясняю. Регистрация производиться в динамическом режиме, положим, онлайн. Нам нужно при каждом обращении проверять, можем ли мы ещё принять нового участника, или ему следует отказать. Ответ нужен быстро, поэтому перебор не катит. Сколько именно групп придёт, нас тоже не волнует. Если пришли одни химики, заняли все аудитории, и после этого появился первый физик, то он в пролёте - конференция будет сугубо химическая. Массовая регистрация (чтобы были неделимые группы) запрещена. Сколько аудиторий - пока неизвестно (ну, или если не нравится такая формулировка, то программа должна быть приспособлена под разные конференции или даже разные институты). Как будут прибывать люди - тоже хз, во всяком случае на это нельзя полагаться.
Вы пока пообсуждайте, а я чуть позже оценю предложеные варианты с вашего позволения. А то приболел немного и сейчас с трудом могу оценить ответы, а тем более слелать по ним логические суждения без доли бреда.
В таком варианте задача просто нерешаема эффективнее, чем тупо сортиронуть все аудитории по вмещаемости и брать две первых самых здоровых аудитории, и в одну посылать химиков, в другую физиков. По мере их заполнения брать следующую по вмещаемости аудиторию. Эффективнее варианта, при условии, что мы не знаем сколько и какими группами будут прибывать физики и химики, быть просто не может.
|
|
|
|
|
RE: Задача на размещение - 2009-06-02 02:31:13.606666
|
|
|
NightmareZz
Сообщений: 1087
Оценки: 0
Присоединился: 2006-10-15 11:16:16.833333
|
quote:
ORIGINAL: kreol
Ок, поясняю. Регистрация производиться в динамическом режиме, положим, онлайн. Нам нужно при каждом обращении проверять, можем ли мы ещё принять нового участника, или ему следует отказать. Ответ нужен быстро, поэтому перебор не катит. Сколько именно групп придёт, нас тоже не волнует. Если пришли одни химики, заняли все аудитории, и после этого появился первый физик, то он в пролёте - конференция будет сугубо химическая. Массовая регистрация (чтобы были неделимые группы) запрещена.
Что мешает перераспределять людей и группы по мере необходимости?
Который раз описываешь условия задачи и каждый раз получается УГ.
|
|
|
|
|
RE: Задача на размещение - 2009-06-02 04:35:27.710000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: NightmareZz
Что мешает перераспределять людей и группы по мере необходимости?
Который раз описываешь условия задачи и каждый раз получается УГ.
Перераспределять КАК? При достижении критической точки, когда все аудитории заняты хотя бы одним человеком, и в одной из групп происходит переполнение (все аудитории для данной группы заняты, и пытается зарегистрироваться ещё один человек из этой группы) нужно ответить, можем ли мы размесить нового участника и как для этого нужно перераспределить остальных. Например, есть аудитории с вместительностью 50, 30, 30 и 15 человек. Распределение такое:
50 - заполнена химиками на 40 человек
30, 30 и 15 заполнены физиками до конца
Приходит ещё один физик, места в "физических" аудиториях больше нет. Очевидно, что мы можем переместить всех химиков в одну аудиторию на 30 человек и в одну на 15, а 45 физиков оттуда переместить в "пятидесятку". Для человека это очевидно. А теперь запиши это в виде алгоритма для всех возможных входных данных и обоснуй математически.
Конечной точкой работы программы должно быть состояние системы (распределение по аудиториям), при котором мы первый раз пошлём регистрирующемуся сообщение "Извините, все места на конференцию этого типа заняты". Это функция программы, читай постановка задачи. Именно это я и написал в самом первом посте.
Пока что только Денатурант предложил вроде бы наилучший и вроде бы даже доказуемый алгоритм.
|
|
|
|
|
RE: Задача на размещение - 2009-06-02 10:27:34.880000
|
|
|
gotoxardas
Сообщений: 842
Оценки: 0
Присоединился: 2007-05-25 08:15:21.840000
|
В итоге, как я понял задачу после 24 постов. У нас есть физики и химики. Есть K - количество аудиторий, и массив A[1..k] - список вместимости аудиторий. Надо распределить максимальное из N+M людей по аудиториям, что бы в одной аудитории не встречались и физики, и химики. В ответе нам нужно получить максимально возможную сумму N+M, где N - конечное количество физиков, M - конечное количество химиков. Дополните, если что не так.
Задача с таким условием, предположительно, решается динамикой за O(N*M*K), с составлением двумерного массива mas[1..n,1..m] где ответом будет mas[n,m].
|
|
|
|
|
RE: Задача на размещение - 2009-06-02 14:42:19.733333
|
|
|
NightmareZz
Сообщений: 1087
Оценки: 0
Присоединился: 2006-10-15 11:16:16.833333
|
quote:
ORIGINAL: kreol
Перераспределять КАК?
Кверху каком. Например, перегнать народ из одной аудитории в другую, более просторную.
|
|
|
|
|
RE: Задача на размещение - 2009-06-03 03:40:50.313333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: NightmareZz
Кверху каком. Например, перегнать народ из одной аудитории в другую, более просторную.
Ооо дааа, это алгоритм решения. В какую более просторную? А если более просторная уже занята, куда девать людей из неё? По какому принципу? Или ты хочешь посадить оператора, который вручную будет прикидывать, как ещё можно перераспределить народ?
|
|
|
|
|
RE: Задача на размещение - 2009-06-03 03:47:54.830000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: gotoxardas
В итоге, как я понял задачу после 24 постов. У нас есть физики и химики. Есть K - количество аудиторий, и массив A[1..k] - список вместимости аудиторий. Надо распределить максимальное из N+M людей по аудиториям, что бы в одной аудитории не встречались и физики, и химики. В ответе нам нужно получить максимально возможную сумму N+M, где N - конечное количество физиков, M - конечное количество химиков. Дополните, если что не так.
Задача с таким условием, предположительно, решается динамикой за O(N*M*K), с составлением двумерного массива mas[1..n,1..m] где ответом будет mas[n,m].
Похоже, что задачу ты так и не понял, всё-таки. Нам нужно не разместить максимальное M + N - оно будет равно суммарной вместительности аудиторий - а максимально отдалить тот момент, когда регистрирующийся получит отказ из-за нехватки аудиторий. Например, аудитории по 50, 30, 30 и 15 человек. 50-ка заполнена на, положим, 48 человек химиками, все остальные забиты под завязку физиками (всего 75 человек), и пытается зарегистрироваться тоже физик. Ему будет отказано, потому что мы не можем больше никак переразместить людей с соблюдением разграничения физики/химики, чтобы вместить 76 физиков.
Что обозначают элементы массива mas я вообще не понял.
|
|
|
|
|
RE: Задача на размещение - 2009-06-03 04:13:32.800000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: Denaturat
если перемещать можно, то задача тривиальна - берёшь две самых вместительных аудитории, и набираешь их до окончания места в одной из них. далее сравниваешь вместительность, и либо меняешь местами их содержимое (если место осталось в большей), либо начинаешь отправлять людей в следующую по величине аудиторию. получишь оптимальное размещение в каждый фиксированный момент времени
Таки тоже нет. Например, те же самые аудитории на 50, 30, 30 и 15 человек. Сначала 50-ка заполняется на 31 химиками. Затем идёт очень длинная цепочка из физиков. Сначала они заполняют 30-ку. Когда приходит 31-й физик твой алгоритм говорит, что должен произойти обмен аудиториями. Как ты понимаешь, он в данном случае не только бессмысленен (количество физиков и химиков будет одинаковым), но и невозможным, потому что 31-ого химика из 50-ки в 30-ку мы не впихнём.
Итак, обмен не произведён. Далее, если продолжится сплошной поток физиков, то они заполнят все оставшиеся аудитории (обмен с пятидесяткой ни в одном месте так и не будет вызван). Получится 75 физиков. 76-й получит отказ, потому что физических аудиторий больше не осталось. Это при том, что в 50-ке, занятой химиками, ещё целых 19 мест.
Да и вообще понятие оптимального размещения в каждый фиксированный момент времени сомнительно. 40 человек лучше разместить в одну аудиторию на 50 человек или в две на 30? Почему? Суждения нельзя сделать пока мы не получим переполнение как минимум в одной аудитории. А переразмещения, судя по всему, бессмысленно делать пока не будут использованы все аудитории и в одной из групп не произойдёт переполнение.
|
|
|
|
|
RE: Задача на размещение - 2009-06-03 13:01:57.353333
|
|
|
NightmareZz
Сообщений: 1087
Оценки: 0
Присоединился: 2006-10-15 11:16:16.833333
|
quote:
ORIGINAL: kreol
quote:
ORIGINAL: NightmareZz
Кверху каком. Например, перегнать народ из одной аудитории в другую, более просторную.
Ооо дааа, это алгоритм решения. В какую более просторную? А если более просторная уже занята, куда девать людей из неё? По какому принципу? Или ты хочешь посадить оператора, который вручную будет прикидывать, как ещё можно перераспределить народ?
Не тупи. Я спрашиваю, такая операция допустима или нет?
|
|
|
|
|
RE: Задача на размещение - 2009-06-03 14:21:16.763333
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
тогда по первой нехватке места пробуй переразмещать людей динамикой. если улучшить нельзя - то опаньки, в противном случае продолжаем
|
|
|
|
|
RE: Задача на размещение - 2009-06-03 18:20:38.100000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: Denaturat
тогда по первой нехватке места пробуй переразмещать людей динамикой. если улучшить нельзя - то опаньки, в противном случае продолжаем
О(2^n), если я не ошибаюсь?
|
|
|
|
|
RE: Задача на размещение - 2009-06-04 10:48:08.656666
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
Хотите я урежу количество проблем до минимума? Может я ничего нового-то не скажу… Считайте это просто чёткой формулировкой того что уже сказано. Алгоритм такой:
1. Инициализация. Х (множество аудиторий химиков) <- пустое множество, Ф (множество аудиторий физиков) <- {все доступные аудитории}. х (количество зарегистрированных химиков) <- 0, ф (физиков) <- 0.
2. Берём следующего чела. Если это физик, то увеличиваем ф (ф <- ф + 1), и переходим к шагу 5. Если это химик, то увеличиваем х.
3. Если суммарная ёмкость аудиторий из Х > х, то переходим к 2.
4. Проблема тут. Переносим какую-то часть аудиторий из Ф в Х, и какую-то часть аудиторий из Х в Ф, получая новые множества аудиторий Ф1 и Х1. Причём переносим таким образом, чтобы а) суммарная вместимость аудиторий из Х1 была бы больше вместимости Х (давайте это обозначим так: |Х1| > |Х|) б) не существовало бы Ф' такого, что |Ф| < Ф' < |Ф1|.
5. чек. если |X1| > х и |Ф1| > ф, то Х <- Х1, Ф <- Ф1 и переходим к 2. Иначе алгоритм завершается: мы нашли того первого чела, которому не хватает места. Причём химикам надо выдать все аудитории из Х (и только их), физиков же каким-то образом можно рассадить по аудиториям из Ф (возможно часть этих аудиторий можно оставить свободными).
Насчёт алгоритма. Я уверен что можно доказать, что этот алгоритм действительно растолкает по аудиториям максимальное число народа. То есть я вижу это доказательство, но мне лень напрягать мозг и его формулировать, чтобы убедиться в том что это именно доказательство, а не просто так мысли. 8|
Проблема в 4-м шаге, я что-то не вижу как его выполнить без полного перебора всех вариантов. То есть взяли первое подмножество аудиторий из Х, сравнили его вместимость с вместимостями всех подмножеств аудиторий Ф. потом взяли второе подмножество из Х и сравнили со всеми из Ф. И тд, то тех по пока не переберём все вообще подмножества, задача же при этом найти пару подмножеств с минимальной разницей вместимости.
|
|
|
|
|
RE: Задача на размещение - 2009-06-05 05:51:38.083333
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Мне кажется, ты что-то мудришь Зачем нам делить множество аудиторий на какие-то подмножества и придумывать какие-то правила. Я исхожу из того, что:
1) пока не наступило переполнение в одной из аудиторий, нет смысла вообще что-то делать: пока есть свободные места в непустых аудиториях, можно отправлять народ туда, а как дальше будут чередоваться Ф и Х можно только угадывать, а это нам не катит;
2) пока не наступит критическая точка (когда произошло переполнение в одной из аудиторий, а свободных уже нет), нет смысла перемещать народ и искать оптимальный вариант. Примерно по тем же причинам, что и в п. 1;
3) при поиске оптимального варианта следует рассматривать всего три параметра: массив аудиторий, общее количество химиков и общее количество физиков. Это более гибко, чем оглядываться, кто в какой аудитории сидит и как их можно менять друг с другом. То есть мы избавляемся от одного мысленного ограничения.
Соответственно, алгоритм, который был у меня изначально, представлял из себя следующее
1) начинаем заполнять аудитории в произвольном порядке до достижения критической точки;
2) при достижении КТ забираем у всех все аудитории, получаем два числа и массив аудиторий. При этом для группы, в которую пытается зарегистрироваться новый участник, берём количество людей плюс один, то есть дальше мы будем пытаться разместить уже новую, пополненную группу;
3) сортируем массив по убывнию вместительности, выбираем большую группу и начинаем заполнять ей аудитории, а именно:
a) если количество людей в группе превышает либо равно размеру аудитории, то считаем эту аудиторию заполненной данной группой. Отнимаем вместительность аудитории от размера группы, переходим к следующей аудитории и повторяем этот шаг;
b) если размер группы меньше вместительности аудитории, то отдаём право занимать аудитории второй группе и повторяем уже для них шаг 3;
4) рано или поздно придём к моменту, когда ни одна из групп не может заполнить текущую аудитрию полностью. Мы точно знаем, что в тех аудиториях, которые уже заполнены, плотность максимальная, поэтому про них мы можем забыть и пытаться разместить остатки двух групп в остатках аудиторий. Тут мозможны варианты. Можно применить тот же перебор, т.к. количество аудитрий будет уже гораздо меньше и скорее всего сведётся к двум. Но можно сделать проще: берём бОльшую группу (вернее, остаток группы) и спокойно размещаем её в первой из оставшихся аудиторий (аудитория икс). То, что она туда влезет, гарантированно п. 3. Остаётся только вопрос, сможем ли мы вместить вторую группу в следующие за этой аудитории, и будет ли это оптимальным размещением, или это вторую группу нужно было отправить в аудиторию икс, а эту пытаться разместить в остальных. Но тут, как бе, тоже не проблема: если мы не можем разместить меньшую из оставшихся подгрупп после аудитории икс, то большую подгруппу мы там тем более не сможем разместить, а значит, стоп алгоритм, переразместить невозможно, новому регистрирующемуся отказать, вернуть прежнюю рассадку и выдать результат.
Порядок роста получается O(n) в отличие от решения через динамику, для которой я вижу алгоритм только с O(n^2) (или всё таки ошибаюсь?).
Что интересно, Vary с ходу предложил аналогичным моему, но гораздо более простой и красивым вариант. Ещё раз повторю его так, как понял сам:
1) при достижении критической точки отобрать все аудитории и получить, как и у меня, 2 числа и массив аудиторий;
2) брать большую из оставшихся (под)групп и размещать её в следующей аудитрии, опять же вычитая из размера (под)группы вместительность аудитории.
Собственно всё. Пока люди из большей подгруппы полностью заполняют аудиторию, получаем максимально плотное заполнение, когда доходит до неполного заполнения, действия в обоих алготимах одинаковы.
Я нигде не ошибся?
Есть более хороший вариант?
|
|
|
|
|
RE: Задача на размещение - 2009-06-05 10:23:13.403333
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: kreol
Мне кажется, ты что-то мудришь Зачем нам делить множество аудиторий на какие-то подмножества и придумывать какие-то правила.
Можно не делить. Но тогда нам придётся работать с тремя подмножествами – подмножествами аудиторий химиков, физиков и пустыми аудиториями.
quote:
ORIGINAL: kreol
Я исхожу из того, что:
1) пока не наступило переполнение в одной из аудиторий, нет смысла вообще что-то делать: пока есть свободные места в непустых аудиториях, можно отправлять народ туда, а как дальше будут чередоваться Ф и Х можно только угадывать, а это нам не катит;
2) пока не наступит критическая точка (когда произошло переполнение в одной из аудиторий, а свободных уже нет), нет смысла перемещать народ и искать оптимальный вариант. Примерно по тем же причинам, что и в п. 1;
Предложенный мною алгоритм и не делает ничего. Лишь считает сколько же народу прибыло. )
quote:
ORIGINAL: kreol
3) при поиске оптимального варианта следует рассматривать всего три параметра: массив аудиторий, общее количество химиков и общее количество физиков. Это более гибко, чем оглядываться, кто в какой аудитории сидит и как их можно менять друг с другом. То есть мы избавляемся от одного мысленного ограничения.
Это поначалу. Пока достаточно свободных аудиторий. Представь себе некое множество аудиторий. Допустим мы его произвольным образом разбиваем на два подмножества. Каждое из них имеет свою вместимость. Мы получаем пару чисел – вместимость первого подмножества и вместимость второго. Сколько таких разных пар чисел может быть? И каждая такая пара, между прочим соответствует одному из вариантов, который мы бы хотели получить при определённой последовательности входящих физиков/химиков.
quote:
ORIGINAL: kreol
Соответственно, алгоритм, который был у меня изначально, представлял из себя следующее
1) начинаем заполнять аудитории в произвольном порядке до достижения критической точки;
Покатит.
quote:
ORIGINAL: kreol
2) при достижении КТ забираем у всех все аудитории, получаем два числа и массив аудиторий. При этом для группы, в которую пытается зарегистрироваться новый участник, берём количество людей плюс один, то есть дальше мы будем пытаться разместить уже новую, пополненную группу;
А вот тут мне не нравится. если у нас есть пара чисел (х, ф) и мы умеем размещать такое количество химиков и физиков, то почему бы не плясать от этого умения, чтобы разместить (х+1, ф)?
quote:
ORIGINAL: kreol
3) сортируем массив по убывнию вместительности, выбираем большую группу и начинаем заполнять ей аудитории, а именно:
a) если количество людей в группе превышает либо равно размеру аудитории, то считаем эту аудиторию заполненной данной группой. Отнимаем вместительность аудитории от размера группы, переходим к следующей аудитории и повторяем этот шаг;
b) если размер группы меньше вместительности аудитории, то отдаём право занимать аудитории второй группе и повторяем уже для них шаг 3;
4) рано или поздно придём к моменту, когда ни одна из групп не может заполнить текущую аудитрию полностью. Мы точно знаем, что в тех аудиториях, которые уже заполнены, плотность максимальная, поэтому про них мы можем забыть и пытаться разместить остатки двух групп в остатках аудиторий.
Про "плотность максимальна" пожалуйста подробнее. :)
Какое нам дело до плотности уже заполненных аудиторий, если мы собираемся добавить ещё немного? Плотность изменится.
Например, если мы выделили физикам аудитории вместительностью 5 и 4. остался один неприкаянный физик. Но если у нас есть две аудитории на три рыла, то мы же можем дать физикам аудитории 3, 3 и 4, тогда они влезут все, и более того, ни одно место не будет пустовать.
Ты хочешь алгоритм, который будет искать какое-нибудь размещение, или алгоритм который заведомо разместит максимум? "Заведомо" – это типа математически доказуемо.
На самом деле, мне кажется, что мой алгоритм можно усложнить, слегка уменьшив время выполнения. (а может и не слегка: это уже проверить можно лишь статистически. а может и не уменьшив :)). Можно не стремиться на 4-м шаге искать лучшие подмножества для переноса туда-сюда. Можно искать подходящее (убрать оттуда условие, что не должно существовать Ф' : |Ф| < Ф' < |Ф1|). Просто в случае, когда физикам не хватает места, придётся не просто говорить, что алгоритм закончен, а выполнять нечто в стиле инвертированного четвёртого шага (то есть где ф заменено на х и наоборот). 4-й шаг станет проще, и пока свободных мест много он вообще будет тривиален.
ps. Кстати там очепятка в алгоритме. Во-втором шаге. Я исправил и выделил жирным исправление.
|
|
|
|
|
RE: Задача на размещение - 2009-06-06 00:41:16.710000
|
|
|
Vary
Сообщений: 31
Оценки: 0
Присоединился: 2009-02-19 15:33:19.930000
|
quote:
ORIGINAL: kreol
Что интересно, Vary с ходу предложил аналогичным моему, но гораздо более простой и красивым вариант.
в принципе да, с той лишь разницей что я считал кол-во людей заранее известным, собсно поэтому и простой). а если же размещать людей динамически, то можно вызывать мой алгоритм при каждом новопришедшем человеке, но это уже будет неспортивно, хоть и стопудово верно разместит максимальное кол-во людей
|
|
|
|
|
RE: Задача на размещение - 2009-06-06 21:41:04.056666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: rgo
А вот тут мне не нравится. если у нас есть пара чисел (х, ф) и мы умеем размещать такое количество химиков и физиков, то почему бы не плясать от этого умения, чтобы разместить (х+1, ф)?
Потому что возможно очень сильные перестановки, а это значит, что всё равно придётся перебирать кучу вариантов. Итого, всё опять же сводится к перебору.
quote:
Про "плотность максимальна" пожалуйста подробнее.
Какое нам дело до плотности уже заполненных аудиторий, если мы собираемся добавить ещё немного? Плотность изменится.
Если плотность в заполненных аудиториях максимальна, это значит, что в эти аудитории больше народа мы впихнуть уже не сможем. Согласен, теоретически возможны какие-то перестановки с уже заполненными аудиториями, которые позволили бы в целом вместить больше людей, поэтому я и говорю, что математического обоснования модели нет. Однако, учитывая, что у нас всего две группы и исходя из некоторых соображений я всё же считаю, что при максимальной заполненности всех предыдущих аудиторий можно задачу свести к поиску наилучшего варианта размещения остатков групп в остатках аудиторий на любой итерации алгортима.
quote:
Например, если мы выделили физикам аудитории вместительностью 5 и 4. остался один неприкаянный физик. Но если у нас есть две аудитории на три рыла, то мы же можем дать физикам аудитории 3, 3 и 4, тогда они влезут все, и более того, ни одно место не будет пустовать.
А какой смысл нам рассматривать физиков вне контекста химиков и вне критической точки? А если сразу после размещения в 3, 3 и 4 придут ещё ровно два физика и заполнят максимально аудитории 5, 4 и 3? То есть по сути мы можем делать о размещении всего один тип суждений: возможно разместить такое количество химиков и физиков, или уже невозможно. А для суждений на тему оптимальности я как-то не вижу почвы.
quote:
Ты хочешь алгоритм, который будет искать какое-нибудь размещение, или алгоритм который заведомо разместит максимум? "Заведомо" – это типа математически доказуемо.
Для реальных задача сойдёт и "какое-нибудь" довольно хорошее размещение, но хочется то всё равно лучшего, то есть "заведомо" максимум :)
quote:
Просто в случае, когда физикам не хватает места, придётся не просто говорить, что алгоритм закончен, а выполнять нечто в стиле инвертированного четвёртого шага (то есть где ф заменено на х и наоборот).
Ну здесь можно всё свести к вопросу об общей вместимости, конкретное размещение в случае неудачи можно просто запоминать на предыдущем шаге и сразу выдавать по окончании алгоритма.
|
|
|
|
|
RE: Задача на размещение - 2009-06-06 21:58:57.286666
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: Vary
а если же размещать людей динамически, то можно вызывать мой алгоритм при каждом новопришедшем человеке, но это уже будет неспортивно, хоть и стопудово верно разместит максимальное кол-во людей
Не разместит. Смотри:
quote:
- смотрим кого больше, потом берем самую большую аудиторию и пихаем их туда. Не поместившихся пишем в соответствующий kol. поюзанную аудиторию выбрасываем из поля зрения(метим нулем в маркировочном массиве);
Уже приведённый мною пример: аудитории размерами 5, 4, 3, 3. Десять физиков и пять химиков. Ты предлагаешь выдать физикам бОльшую аудиторию – 5. Потом ты уже не вместишь оставшихся. Тут единственный вариант – выдать физикам 4, 3, 3, а химикам 5, даже несмотря на то, что химиков меньше.
У меня крутиться в голове что-то на тему… Какую-то задачу близкую к теме я видел раньше. Что-то типа ответа на вопрос можно ли получить определённое число в виде суммы чисел из данного набора чисел (мне почему-то кажется что знание алгоритма решения этой задачи нефигово могло бы помочь). И вроде я с это задачей столкнулся при изучении высшей алгебры. Но я никак не вспомню к чему это было. А то можно было бы ознакомиться с тем, что умные люди думают по этому поводу.
|
|
|
|
|
RE: Задача на размещение - 2009-06-07 00:05:15.513333
|
|
|
Vary
Сообщений: 31
Оценки: 0
Присоединился: 2009-02-19 15:33:19.930000
|
rgo:
согласен. не продумал
|
|
|
|
|
|
