Максимизация вероятности рандомизированного алгоритма

Question

Я студент по информатике, и я просто учусь в финале.Я столкнулся с проблемой, которая была немного неуместна с различными проблемами типа динамического программирования.Я резюмирую это так:

Мне дан эффективный рандомизированный алгоритм A, который возвращает независимый набор.Этот алгоритм возвращает максимальное независимое множество с вероятностью не менее 1 / (n ^ 3), где n - количество вершин в графе.Предложите другой алгоритм, использующий A, который возвращает максимальный набор с вероятностью не менее 1/2.

Я изучал рандомизированные алгоритмы, но это просто кажется простым примером реализации.Если бы я должен был запустить A n ^ 3 раза, вероятность того, что максимальный независимый набор близок к 1. Могу ли я тогда сказать, что запуск его n ^ 3/2 раза даст желаемый эффект?Я просто пытаюсь сделать это сложнее?Любая помощь приветствуется.

Answer 1

Близко, но не точно, вероятность того, что один из прогонов вернет правильный ответ, составляет не менее 1 / n ^ 3.Это означает, что вероятность получения неправильного ответа за один прогон составляет (1-1 / n ^ 3), что означает, что вероятность получения правильного ответа после прогонов M составляет 1- (1-1 / n ^ 3) ^ M.

Теперь напомним формулу для e (ссылка на Википедию) , если вы запустили n ^ 3 раза, вероятность составляет 1-1 / e, что больше 1/2 (хотя и неочень близко к 1), это также тривиально, чтобы получить точное количество прогонов, чтобы получить точно 1/2 - (n ^ 3) * ln (2).

Answer 2

Я не изучал максимальный независимый набор, поэтому не могу оказать вам слишком большую помощь. Однако сначала вы должны записать алгоритм, прежде чем указывать количество времени работы.

Если вы запустите алгоритм A для n ^ 3, вы получите n ^ 3 максимального независимого набора. Однако вам необходимо вернуть только ОДИН максимальный набор. Как вы находите правильный в этих n ^ 3? Здесь вам может потребоваться алгоритм проверки, который отсутствует в вашем вопросе.

В зависимости от самой проблемы (максимальный независимый набор) у вас может быть достаточно информации, чтобы найти правильный максимальный независимый набор, для которого требуется количество прогонов, значительно меньшее O (n ^ 3).