Amnesty International представляет: ещё одна стратегия


Автор сообщения: Michael
Дата и время сообщения: 26 October 2004 at 04:03:51:

В ответ на сообщение: Re: Еще один алгоритм

Излагаю новую стратегию, которая является гибридом стандартного алгоритма и идеи Заметила-Просто. Стратегия должна дать улучшение для больших N, начиная с 15-20.

Начальное условие таково - у каждого бандита изначально есть одна условная лампочка (единица счёта). Зажигая лампочку в карцере, он "отдаёт" свою единицу, туша - забирает чужую. Когда у кого-то соберётся N условных "лампочек", он может звать адвоката.

Основная идея заключается в том, что в определённые промежутки времени лампочкой можно передавать не одну единицу счёта, а несколько. То есть, сначала несколько разбойников накопят у себя информацию о количестве "соседей", а потом "оптом" передадут её водиле.


Итак, у нас есть три этапа. На первом этапе фиксированной длиной L нет водилы. Цель - вместо N разбойников с одной "лампочкой" получить около N/2 с двумя. Бандит, попавший в карцер, зажигает лампочку и отдаёт свою единицу, следующий её забирает. Те, у кого 0 или 2 единицы, больше ничего не этом этапе не делают. Последний, L-й разбойник должен забрать себе "лампочку", если она горит. В идеале мы получим примерно N/2 разбойников с 2 "лампочками".

На втором этапе фиксированной длиной M выбранный заранее водила должен собирать эти "лампочки". Но теперь каждая зажжёная лампочка будет значить 2, а не 1 единицу! То есть, все бандиты передают водиле результат, собранный на первом этапе, по удвоенному каналу.

И, наконец, на третьем этапе водила подбирает оставшиеся лампочки - тех одиночек, которые не попали в L, и тех двоек, которые не успели в M. Этот этап уже идёт до победного конца.

По идее, для больших N все эти этапы вместе (если хорошо подобраны L и M) должны дать солидное улучшение алгоритма по сравнению со стандартным. Для очень больших N есть смысл не останавливатья на 2-ках, а группироваться по 4, и т.д.

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

Я знаю, что всё это изложено крайне путано, но посмотрите на часы. Вероятности у меня уже не считаются, если Roger не опередит, посчитаю завтра.

С уважением,
Michael
(вы как хотите, а я в карцер, спать. Только лампочку выключу).


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