Дальнейший анализ: поиск хорошего присваивания

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

' в '

Простейшее решение заключается в генерировании случайных логических при- .. ^ .... 7. ..

спаивании до тех пор, пока одно из них не выполнит по крайней мере - к условии.

&

Из (13.15) известно, что такое присваивание существует; но сколько времени по- требуется для того, чтобы найти его методом случайных испытаний?

Здесь будет естественно применить границу времени ожидания, полученную в (13.7). Если мы сможем показать, что вероятность того, что случайное присваи- вание удовлетворяет по крайней мере — к условий, не менее р, то ожидаемое ко-

&

личество испытаний, выполняемых алгоритмом, составляет 1/p. Итак, нам хотелось бы показать, что величинаp по крайней мере не более чем обратно-полиномиальна по n и k.

Для j = 0, 1, 2, ..., k пусть p обозначает вероятность того, что случайное при- сваивание выполняет ровно j условий. Следовательно, ожидаемое количество


шествующего анализа оно равно —к .
Нас интересует величина

Как использовать нижнюю границу ожидаемого количества для получения ниж- ней границы этой величины?


Начнем с равенства

Обозначим к' наибольшее натуральное число, строго меньшее — к . Если за-

8


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

7 7 1

Отсюда кр>-к-к'. Но -к-к'> — , так как к’ — натуральное число, строго


меньшее — другого натурального числа, а следовательно,

Мы получили желаемое — нижнюю границу для p. С учетом границы времени ожидания (13.7) мы видим, что ожидаемое число испытаний, необходимых для нахождения выполняющего присваивания, не превышает 8k.

(13.16) Существует рандомизированный алгоритм с полиномиальным ожида- нием времени выполнения, который гарантированно выдает логическое присваи-

„ „ 7 „

ванне, выполняющее по крайней мере — всех условии.

13.5.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Дальнейший анализ: поиск хорошего присваивания:

  1. Чтобы хорошо говорить, учитесь хорошо писать
  2. Поиск смысла жизни – это поиск бессмертия!
  3. То, что хорошо для одного, не всегда хорошо для другого.
  4. РАБОТА С ДАЛЬНИМИ СИГНАЛАМИ. ПВБ
  5. Е) ДАЛЬНЕЙШЕЕ ДВИЖЕНИЕ К ОРИГИНАЛЬНОМУ МЫШЛЕНИЮ
  6. Тема 18. Правовые системы стран Дальнего Востока
  7. Глава четырнадцатая. Дальнейшие рекомендации по духовному очищению
  8. 3.3. Дальнейшая реализация проекта
  9. II. 2. 7. Тетрады и дальнейшее разбиение множеств.
  10. 1.2. Изменения законодательства и дальнейшие планы
  11. Глава 10 Поощряйте его на дальнейшую учебу
  12. Дальнейшее развитие структуры средств массовой информации
  13. Тема 18. Правовые системы стран Дальнего Востока
  14. Зарубка на носу Дальнейшие указания в области наказания
  15. Тема восстановления и дальнейшего подъема народного хозяйства в советской прессе
  16. Статья 235. Несоблюдение лицом обязательных условий по приватизации государственного, коммунального имущества или предприятий и их дальнейшему использованию
  17. ХОРОШИЕ ИГРЫ