Re: Вопрос Amnesty International


Автор сообщения: Michael
Дата и время сообщения: 26 October 2004 at 12:27:58:

В ответ на сообщение: Вопрос Amnesty International

Заметил-Просто,

прошу прощение за неясности, во-первых, когда я вчера писал, было уже довольно поздно, во-вторых, я хотел передать общую идею, не перегружая её частностями. Все ваши замечания абсолютно верны, это именно то, что я имел в виду, но упустил в объяснении. И вообще, Ваше объяснение чертовски хорошо.

Единственное, с чем я не согласен:

> И эти периоды повторяются по кругу до полного сбора урожая!

Периоды не повторяются. В их повторении нет смысла. Изначально L и М (длина периодов) выбираются так, чтобы было поймать всех "своих" клиентов с максимальной вероятностью. Вернее, так, что увеличивая их, Вы больше не уменьшаете матожидание по сравнению с тривиальным сбором по одному. Поэтому нет смысла их повторять.

Проблема в том, что у нас нет обратного сигнала от "водилы". Мы не знаем, насколько был удачен сбор, и ловим мы на последнем этапе существенное количество разбойников или тех одиночек, что оказались на хвосте распределения.

И ещё. Я думаю, нет смысла устраивать троичные, пятеричные и т.д. периоды. Периоды выбираются как 2n. По обычному методу мы получаем матожидание О(N). А таким образом мы переходим к чему-то O(ln N). На малых N overhead съедает всё. А на больших мы должны получить существенно лучше.


1811. Mihael'ю еще одна задачка! - Заметил-Просто 11:14 21.10.04 (61)
К списку тем на странице