Сколько останется схем
Генетический алгоритм держит популяцию из n строк длины l из нулей и единиц, у строки i приспособленность fi. Новое поколение получается так, как в теореме о схемах: отбор пропорционально приспособленности, одноточечное скрещивание пар с вероятностью pc (место разреза — одно из l − 1), мутация каждого бита с вероятностью pm.
Исследователь хочет знать, какие схемы популяция наверняка не растеряет. Схема — строка длины l из символов 0, 1 и *; строка подходит под схему, если совпадает с ней во всех позициях, где в схеме не звёздочка. Для каждой схемы H посчитайте нижнюю оценку теоремы о схемах для среднего числа подходящих строк в следующем поколении:
Здесь m(H) — число подходящих строк, f(H) — их средняя приспособленность, f̄ — средняя приспособленность всей популяции, o(H) — число позиций схемы без звёздочки, δ(H) — расстояние между первой и последней такими позициями (0, если их меньше двух). Если подходящих строк нет, оценка равна 0. При l = 1 скрещивать негде, и множитель со скрещиванием равен 1.
Вход
В первой строке n, l, q (1 ≤ n ≤ 1000, 1 ≤ l ≤ 64, 1 ≤ q ≤ 1000). Во второй — pc и pm (от 0 до 1). Дальше n строк: строка популяции и её приспособленность — целое от 1 до 106. Дальше q схем, по одной в строке.
Выход
Для каждой схемы — оценку, каждую с новой строки. Ответ засчитывается, если погрешность не больше 10−6 (относительная — для чисел больше единицы).
Примеры
Пример 1
4 4 4 0.7 0.01 1010 5 1110 3 0011 2 1000 2 1**0 *11* **** 0***
0.980100000 0.751410000 4.000000000 0.660000000
Пример 2
3 1 3 0.5 0.1 1 4 0 1 1 2 1 0 *
2.314285714 0.385714286 3.000000000
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Заметьте, что m(H)·f(H) — это просто сумма приспособленностей подходящих строк, и делить на m(H), чтобы потом на него же умножить, не нужно. Остаётся быстро находить подходящие строки.
2Подсказка 2
Строка длины до 64 помещается в одно 64-битное число. Как одной операцией проверить, совпадает ли число с ним во всех позициях, где у схемы не звёздочка?
3Идея
Для схемы построим две маски: care — единицы там, где схема фиксирует бит, и want — сами фиксированные биты (на месте звёздочек нули). Строка x подходит, когда x & care == want: «И» с маской обнуляет позиции под звёздочками, а остальные должны совпасть. Оценка теоремы: сумма приспособленностей подходящих строк, делённая на среднюю приспособленность, умноженная на 1 − pc·δ/(l − 1) и на (1 − pm)o.
Почему в знаменателе l − 1, а не l: у строки длины l всего l − 1 мест между соседними битами, куда можно поставить разрез, и схема с крайними фиксированными позициями i < j разрушается разрезом в одном из j − i = δ промежутков между ними.
4Разбор
Переведите строки популяции в числа, сложите все приспособленности, для каждой схемы постройте маски, порядок и длину и пройдите по популяции. В четвёртом и пятом тестах популяция — настоящий прогон генетического алгоритма на «королевской дороге» из статьи после 30 и 120 поколений. Схемы там — блоки из восьми единиц и пары блоков. У пары далёких блоков длина δ почти 64, и скрещивание с вероятностью 0,7 почти наверняка её разрезает: оценка теоремы для неё мала, даже если строк с обоими блоками много. Это и есть то, о чём предупреждает теорема: длинные схемы скрещивание разрушает.
4+Решение
5Сложность
O(n·l) на чтение популяции и O(l + n) на каждую схему: всего O((n + q)·l + n·q). Посимвольное сравнение каждой строки с каждой схемой стоило бы O(n·q·l) — в 64 раза больше.
6Типичные ошибки
- l вместо l − 1 в доле разрушенных схем. На первом примере даёт 1,552 вместо 0,980 для схемы 1**0.
- Деление на ноль при l = 1. Разрезать строку из одного бита негде, множитель скрещивания равен 1 — это второй пример.
- (1 − pm·o) вместо (1 − pm)o. Это первые два члена разложения, а не сама вероятность; в седьмом тесте pm = 1, и разница огромна.
- Длина схемы из одной фиксированной позиции. Она равна нулю, а не единице: разрезать нечего.