Сегодня "придумал" задачку. Станция метро. Начало месяца. Две кассы работают. Соответственно имеются две очереди. Одна короче, другая длиннее. В какую очередь следует встать, чтобы побыстрее купить билет, если остальные (те, кто образуют эти очереди) действовали по такому же алгоритму? Встав в одну очередь, в другую перейти нельзя. Ломиться вне очереди тоже нельзя — очереди огромные — прибьют.
Здравствуйте, RS, Вы писали:
RS>Сегодня "придумал" задачку. Станция метро. Начало месяца. Две кассы работают. Соответственно имеются две очереди. Одна короче, другая длиннее. В какую очередь следует встать, чтобы побыстрее купить билет, если остальные (те, кто образуют эти очереди) действовали по такому же алгоритму? Встав в одну очередь, в другую перейти нельзя. Ломиться вне очереди тоже нельзя — очереди огромные — прибьют.
RS>З.Ы. Обобщить на случай N очередей.
Если скорость обслуживания одинаковая — однозначно надо становиться в ту, которая короче.
Здравствуйте, RS, Вы писали:
RS>Сегодня "придумал" задачку. Станция метро. Начало месяца. Две кассы работают. Соответственно имеются две очереди. Одна короче, другая длиннее. В какую очередь следует встать, чтобы побыстрее купить билет, если остальные (те, кто образуют эти очереди) действовали по такому же алгоритму? Встав в одну очередь, в другую перейти нельзя. Ломиться вне очереди тоже нельзя — очереди огромные — прибьют.
RS>З.Ы. Обобщить на случай N очередей.
Очевидно, что если люди становятся в более длинную очередь, то она движется быстрее короткой. Весь вопрос в том, насколько быстрее? Не зная этого мы не можем сказать, куда нам следует становиться. Однако если мы учтем тот факт, что все остальные люди правильно выбирали необходимую очередь, то все очереди должны быть примерно одинаковой длины (по времени) +/- 1 человек, и следовательно нам все равно в какую очередь становиться, т.к. к кассе все они подойдут одновременно.
Здравствуйте, RS, Вы писали:
RS>Соответственно имеются две очереди. Одна короче, другая длиннее. В какую очередь следует встать, чтобы побыстрее купить билет, если остальные (те, кто образуют эти очереди) действовали по такому же алгоритму?
Вставать надо в короткую очередь, потому что все встают в короткую. Поэтому, если она все же короткая, значит она идет быстрее!
Здравствуйте, Frostbitten, Вы писали:
F>Вставать надо в короткую очередь, потому что все встают в короткую. Поэтому, если она все же короткая, значит она идет быстрее!
А если она короткая, потому что в нее никто не встает? А не встают, потому что она медленно идет. И встать в длинную — гораздо выгоднее?
Здравствуйте, RS, Вы писали:
F>>Вставать надо в короткую очередь, потому что все встают в короткую. Поэтому, если она все же короткая, значит она идет быстрее!
RS>А если она короткая, потому что в нее никто не встает? А не встают, потому что она медленно идет. И встать в длинную — гораздо выгоднее?
Так как по условиям задачи все действуют по такому же алгоритму, то можно предположить, что они все-таки встают именно в короткую очередь.
Другое дело, если короткая очередь (SQ) сильно короче длинной (LQ), т.е. SQ.size() < < LQ.size(). В таком случает люди боятся (по каким-либо причинам вставать в SQ), и в этом случае надо бесстрашно вступить в SQ.
Здравствуйте, RS, Вы писали:
RS>Здравствуйте, Frostbitten, Вы писали:
F>>Вставать надо в короткую очередь, потому что все встают в короткую. Поэтому, если она все же короткая, значит она идет быстрее!
RS>А если она короткая, потому что в нее никто не встает? А не встают, потому что она медленно идет. И встать в длинную — гораздо выгоднее?
Эти забавные противоречия могут возникнуть из-за незнания некоторых вещей.
А именно, надо:
— знать, что все придерживаются оптимальной стратегии.
— знать, что все тоже знают, что все придерживаются оптимальной стратегии.
— знать, что все тоже знают, что все тоже знают, что все придерживаются оптимальной стратегии.
— знать, что все тоже знают, что все тоже знают, что все тоже знают, что все придерживаются оптимальной стратегии.
— знать, что все тоже знают, что все тоже знают, что все тоже знают, что все тоже знают, что все придерживаются оптимальной стратегии.
...
Поэтому — оптимальная стратегия — перед тем, как выбрать очередь, постоять и понаблюдать за скоростью её движения.
(Правда, надо чтобы все так поступали, и знали, что все придерживаются этой стратегии .)
<Шутка, повторенная дважды, становится истиной. Шутка, повторенная дважды, становится истиной. Шутка, повторенная дважды, становится истиной.> Евгений
Выбор очереди можно сделать, лишь зная скорости обслуживания кассиров. Для этого нужно некоторое время постоять всторонке, прикинуть, какая очередь идет быстрее, в нее и встать. Так как это не указано в задаче (зашли в метро и встали в очередь), то заведомо встать в "лучшую" очередь нельзя.
Остается только встать в короткую. Если она действительно так хороша, нам повезло. Если нет, после того, как мы (и некоторые другие) в нее встали, она уже не будет короткой, короткой станет как раз та, которая движется быстрее. Таким образом всегда будет поддерживаться баланс длин очередей.
Разница длин очередей может быть вызвана неточностью измерения (в начале месяца очереди длинные, извиваются, имеют неравномерное распределение количества человек на длину — от 1 чел/м до 3-3.5 чел/м), а также тем, что одна из касс только что открылась, или сейчас закроется.
Здравствуйте, RS, Вы писали:
RS>Сегодня "придумал" задачку. Станция метро. Начало месяца. Две кассы работают. Соответственно имеются две очереди. Одна короче, другая длиннее. В какую очередь следует встать, чтобы побыстрее купить билет, если остальные (те, кто образуют эти очереди) действовали по такому же алгоритму? Встав в одну очередь, в другую перейти нельзя. Ломиться вне очереди тоже нельзя — очереди огромные — прибьют.
RS>З.Ы. Обобщить на случай N очередей.
Стоим в сторонке и по 2м точкам составляем линейную функцию время_ожидания(количество_человек) для обоих очередей...
Затем подставляем значения...
в общем, примерно также, как мы делаем на глаз — оцениваем скорость и всё
.)
