?

Log in

No account? Create an account

Оптимизационная задачка - Общество дровосеков Бердичева по изучению Мишны

Jun. 13th, 2013

05:23 pm - Оптимизационная задачка

Previous Entry Share Next Entry



Уж как переложил на бытовые реалии, так переложил.

Имеется поликлиника, в которых работают специалисты N разных профилей. Приходящие пациенты встают в общую очередь. Сами они объяснить, какой врач им нужен, не могут, а в ответ на вопрос "К такому-то есть кто-нибудь?" из очереди выходит первый нуждающийся в этом враче, или никто не выходит, если таких на данный момент нет. Время, затрачиваемое регистратурой на один вопрос, в обоих случаях одинаково.

Тривиальный принцип работы регистратуры - называть всех специалистов по кругу, но при "эпидемии" это очевидным образом неэффективно.

Требуется придумать адаптивный алгоритм, стремящийся максимизировать пропускную способность регистратуры, в т.ч. и в условиях изменения характера "эпидемий", сохраняя справедливость: стоящий первым в очереди никогда не должен ждать дольше, чем M вопросов.



Начинаем с колоды из N карточек с номерами от 1 до N. Далее играем раунды так:

Выкликаем согласно номерам на карточках, и раскладываем карточки в N пар кучек, в каждой паре справа - успешные вызовы (Si), слева - неудачные (Fi).


Когда колода исчерпалась, смотрим: если во всех N парах было хотя бы по одному успешному вызову (все Si > 0), то набор Si более или менее неплохо моделирует соотношение частот клиентов врачей, а для уточнения соотношения на следующем круге составляем колоду из 2*Si карточек каждого типа, если это не больше, чем M, иначе по Si каждого типа.

Если же оказалось, что какие-то Si равны нулю, то это значит, что частота запросов для этих i меньше, чем 1/K, где K - размер колоды на только что закончившемся круге. Тогда составляем колоду из min(M, 2*K) карточек так, чтобы в них было по одной карточке для тех i, для которых Si было = 0, а остальные были в той же пропорции, что и ненулевые Si.

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

Споласкиваем, повторяем.

Comments:

[User Picture]
From:vgramagin
Date:June 14th, 2013 01:58 am (UTC)
(Link)
При M=N решение очевидно!
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 02:04 am (UTC)
(Link)
Скажем, M много больше N - в десятки раз.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:galkao
Date:June 14th, 2013 03:00 am (UTC)
(Link)
Называем специалиста 1. Если есть желающий к нему, то снова вызываем специалиста 1. Если есть желающий - снова, и так - до тех пор, пока количество вызовов не превышает M/N. Далее - специалист 2. Ну и по кругу.

Проще говоря, допустим, M/N=10, тогда 10 раз подряд называем каждого специалиста по очереди (либо, если в какой-то момент не оказалось желающего, переходим к следующему специалисту).
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 02:40 pm (UTC)
(Link)
При эпидемиях это будет неоптимально. Допустим, в очереди все к одному и тому же специалисту, тогда оптимально будет вызывать к нему вплоть до M-N+1 раз.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:morfizm
Date:June 14th, 2013 04:30 am (UTC)
(Link)
Пусть freshness(k) - сколько шагов назад назывался k-й врач.
Пусть popularity(k) - сколько пациентов к k-му врачу стоит в очереди (допустим какой-то оракул знает ответ).
Сортируем врачей по лексикографическому возрастанию тупла (max(M-a(i), N), -popularity(k)), и выбираем первого.

Этот алгоритм будет эффективно приоритезировать: самый популярный врач будет обслуживаться максимально, за исключением тех врачей, которых надо назвать для соблюдения справедливости. При одинаковой популярности, трафик будет делиться поровну между всеми одинаковыми.

Допустим, мы не знаем, чему равен popularity(k). Эту популярность надо *измерить*.

Измерять её можно по-разному. Вижу две крайности:

1. "Мочить" одного врача до упора, пока не кончатся его клиенты, или пока его не вытеснят ребята, которые по справедливости. Грубо говоря, popularity(k) = 1 если на предыдущем шаге был хотя бы один клиент, иначе 0. Кстати, в этом случае если к ребятам по справедливости кто-то пришёл, то в следующем раунде они уже будут соревноваться с первым и делить с ним трафик. Но те их них, которые "кончатся", отвалятся из соревнования. В этом случае у нас такой расклад: для лузеров, к которым никого нет, будет задан один вопрос на каждые M шагов. Для тех, к кому за M-шаговый цикл пришло 5 человек, будет 5 или 6 вопросов (в зависимости от того, люди исчерпались до или после обработки лузеров).

Можно делать какую-то адаптивную политику и учитывать историю, например, не присваивать единицу в популярность, а прибавлять единицу, а в случае неудачи не обнулять, а вычитать или делить. Если мы знаем паттерны эпидемий, можно подтюнить формулы так, чтобы было счастье.

2. Можно давать каждому врачу вплоть до M/N попыток и запоминать количество успешных. Круг может закончиться раньше, чем через M шагов, если к кому-то было менее M/N пациентов. На второму круге эти числа уже можно использовать как популярность. Время от времени делать тюнинг, заново пересчитывая. Или учитывая длины новых отрезков в формулу популярности. В случае одного доминирующего и остальных отдыхающих, его throughput будет заметно меньше, т.к. он будет получать не (M-N)/M, а (M/N)/(M/N + N). Зато будет некоторый QoS, честнее пропорция трафика и быстрее реакция на появление новых популярных врачей.

За неимением дополнительных знаний об эпидемиологических свойствах, я бы выкатил в продакшн п.1., ибо это максимизирует max throughput для лучшего, что есть нередко важнейшая метрика.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 02:47 pm (UTC)
(Link)
В отсутствие эпидемий алгоритм "мочить до упора" неоптимален, т.к. может быть вплоть до 50% бесполезных вопросов.
(Reply) (Parent) (Thread)
[User Picture]
From:yatur
Date:June 14th, 2013 04:40 am (UTC)
(Link)
А какая программистская ситуация соответствует такой схеме? Чтобы пациент мог ответить на вопрос "вы к окулисту?", но не мог бы ответить на вопрос "к какому вы врачу"? Ну, т.е., человек может забыть как называется глазной врач ("окулист" - пассивное слово), но с программами этого ведь обычно не происходит?
(Reply) (Thread)
[User Picture]
From:morfizm
Date:June 14th, 2013 04:45 am (UTC)
(Link)
Я думаю, для простоты модели можно считать, что "N разных профилей ~= N врачей с такими-то именами", т.к. несколько врачей одного профиля можно легко сгруппировать в "одного врача" (назвав его "группа окулистов", скажем), и свести задачу к предыдущей.
(Reply) (Parent) (Thread)
[User Picture]
From:morfizm
Date:June 14th, 2013 04:41 am (UTC)
(Link)
Ещё - интуитивно кажется, что для реальных задач может хорошо подойти алгоритм на основе вышеуказанного, но в котором есть следующие дополнения:
1. У каждого врача есть лимит на количество вопросов подряд, вначале limit(k) = 2.
2. В случае упирания в limit после цепочки из q вопросов, происходит следующее: если все q были обработаны, то limit := limit * 2 (по сути он будет 2q), а popularity := q. Если же цепочка закончилась в результате облома, и на последний вопрос никто не откликнулся, сбрасываем в начало: limit := 2, popularity := 0.

Получаем ситуацию, в которой у врача-лузера есть шанс постепенно "разогнаться" и потом делить канал почти поровну с предыдущим победителем, пока один из них не исчерпает спрос.
(Reply) (Thread)
[User Picture]
From:morfizm
Date:June 14th, 2013 05:11 am (UTC)
(Link)
О... понятно, сортировку надо подтюнить - вместо max(M-a(i), N) делать что-то вроде max(M-N-a(i), N). Чтобы в случае когда осталось M-2*N шагов, уже начинать сортировать оставшихся, т.к. каждому лузеру полагается до 2 попыток.

P.S. Я там где-то мог не учесть +1 или -1, это в юнит тестах отлаживается :)
(Reply) (Parent) (Thread)
[User Picture]
From:vymenets
Date:June 14th, 2013 06:09 am (UTC)
(Link)
Такое чувство, что условие неполное. Время приёма специалиста больше нуля? Больше или меньше времени на вопрос регистратуры? Может ли регистратура узнать, что конкретный специалист освободился?
(Reply) (Thread)
[User Picture]
From:morfizm
Date:June 14th, 2013 11:14 am (UTC)
(Link)
Пусть автор меня поправит, но я думаю, что здесь имеется в виду, что время приёма у специалиста равно (или: не больше) времени вопроса. Скажем, регистратура задаёт вопрос раз в минуту, и этой минуты хватает, чтобы обслужить. Можно представить себе, что под именем специалиста скрывается целая группа похожих специалистов, которые позволяют такое быстрое обслуживание. Соответственно, перед каждым следующим вопросом все специалисты свободны, а работает только один из них одновременно. Но "оплата" идёт только за вопросы регистратуры. Каждый вопрос, даже если он вхолостую (никого из очереди к этому специалисту не оказалось), стоит минуту времени.

Второй вариант (изоморфный) после направления к специалисту пациент переходит в другую очередь (конкретно к этому специалисту), в которой время уже никак не учитывается и обслуживание идёт в порядке очереди.
(Reply) (Parent) (Thread) (Expand)
[User Picture]
From:dvv
Date:June 14th, 2013 01:24 pm (UTC)
(Link)
Ну чо, веса́ накидывать на используемых специалистов (с time decay). Логарифмически or something. Обычное дело…
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 14th, 2013 03:10 pm (UTC)
(Link)
Именно что or something. Эргодичности никто не обещал.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:June 14th, 2013 03:44 pm (UTC)
(Link)
Что-то тут не так. "Сами они объяснить, какой врач им нужен, не могут" не вяжется со способностью ответить на вопрос "К такому-то есть кто-нибудь?". Получается, что кто-то (регистратура?) должен им это объяснить перед тем, как поставить в очередь.

Решение - регистратура самообслуживания. Чтоб каждый пациент самостоятельно классифицировал, к какому врачу ему надо.

То есть, переходя на кнопкодавские реалии, вызывал функцию, назначающаю врача, в контексте своего собственного треда.
(Reply) (Thread)