Как доказать, что жадный алгоритм верен

29

У меня есть жадный алгоритм, который, я подозреваю, может быть правильным, но я не уверен. Как мне проверить, правильно ли это? Какие методы использовать для доказательства правильности жадного алгоритма? Существуют ли общие модели или методы?

Я надеюсь, что это станет справочным вопросом, на который можно указать новичкам; следовательно, его более широкий, чем обычно, объем. Пожалуйста, позаботьтесь о том, чтобы дать общие, дидактически представленные ответы, которые иллюстрируются хотя бы одним примером, но тем не менее охватывают многие ситуации. Благодарность!

DW
источник
Можем ли мы доказать, что жадный алгоритм корректен с помощью матроида или жадного алгоритма?
Здм

Ответы:

24

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

Случайное тестирование

В качестве первого шага я рекомендую использовать случайное тестирование для проверки вашего алгоритма. Удивительно, насколько это эффективно: по моему опыту, для жадных алгоритмов случайное тестирование кажется неоправданно эффективным. Потратьте 5 минут на написание своего алгоритма, и вы можете сэкономить час или два, пытаясь придумать доказательство.

Основная идея проста: реализовать свой алгоритм. Кроме того, реализуйте эталонный алгоритм, который, как вы знаете, является правильным (например, тот, который исчерпывающе пробует все возможности и выбирает лучшее). Хорошо, если ваш эталонный алгоритм асимптотически неэффективен, так как вы будете запускать его только на небольших проблемных экземплярах. Затем случайным образом сгенерируйте миллион маленьких проблемных экземпляров, запустите оба алгоритма для каждого и проверьте, дает ли алгоритм-кандидат правильный ответ в каждом случае.

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

Математические доказательства правильности

Итак, нам нужно доказать, что наш жадный алгоритм верен: он выводит оптимальное решение (или, если есть несколько оптимальных решений, которые одинаково хороши, он выводит одно из них).

Основной принцип интуитивно понятен:

Принцип: если вы никогда не сделаете плохой выбор, все будет хорошо.

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

Что считается хорошим выбором? Если есть единственное оптимальное решение, легко увидеть, что является хорошим выбором: любой выбор, идентичный тому, который сделан оптимальным решением. Другими словами, мы попытаемся доказать, что на любом этапе выполнения жадных алгоритмов последовательность выборов, сделанных алгоритмом, точно соответствует некоторому префиксу оптимального решения. Если существует несколько одинаково хороших оптимальных решений, хорошим выбором будет тот, который соответствует хотя бы одному из оптимумов. Другими словами, если последовательность выбора алгоритма до сих пор совпадает с префиксом одного из оптимальных решений, все в порядке (пока ничего не пошло не так).

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

Существует очень распространенный образец доказательства, который мы используем. Мы будем усердно работать, чтобы доказать следующее свойство алгоритма:

Утверждение: пусть будет решением, выводимым алгоритмом, и O будет оптимальным решением. Если S отличается от O , то мы можем подправить O , чтобы получить другое решение O * , который отличается от O и строго лучше , чем O .SOSOOOOO

Обратите внимание, почему это полезно. Если утверждение верно, значит, алгоритм верен. Это в основном доказательство от противного. Либо такое же , как O , или она отличается. Если оно отличается, то мы можем найти другое решение O ∗, которое строго лучше, чем O - но это противоречие, поскольку мы определили O как оптимальное решение, и не может быть никакого решения, которое лучше этого. Поэтому мы вынуждены сделать вывод, что S не может отличаться от O ; S всегда должно быть равно OSOOOOSOSOжадный алгоритм всегда выводит правильное решение. Если мы можем доказать утверждение выше, то мы доказали, что наш алгоритм правильный.

Хорошо. Так, как мы доказываем требование? Мы рассматриваем решение как вектор ( S 1 , , S n ), который соответствует последовательности n выборов, сделанных алгоритмом, и аналогичным образом мы рассматриваем оптимальное решение O как вектор ( O 1 , , о п ) , соответствующий последовательности вариантов , которые привели бы к O . Если S отличается от O , должен существовать некоторый индекс i, где S iS(S1,,Sn)nO(O1,,On)OSOi ; мы сосредоточимся на самых маленьких, таких как я . Затем мы настроим O ,немногоизменив O в i- й позиции, чтобы она соответствовала S i , т.е. мы настроим оптимальное решение O , изменив i- й вариант на выбор, выбранный жадным алгоритмом, и затем мы покажем, что это приводит к еще лучшему решению. В частности, мы определим O как что-то вродеSiOiiOOiSiOiO

O=(O1,O2,,Oi1,Si,Oi+1,Oi+2,,On),

за исключением того, что нам часто приходится слегка изменять части чтобы поддерживать глобальную согласованность. Часть стратегии доказательства включает в себя некоторый ум в правильном определении O . Тогда основной смысл доказательства состоит в том, чтобы как-то использовать факты об алгоритме и задачу показать, что O строго лучше OOi+1,Oi+2,,OnOOO; вот где вам понадобится понимание проблем. В какой-то момент вам нужно погрузиться в детали вашей конкретной проблемы. Но это дает вам представление о структуре типичного доказательства корректности жадного алгоритма.

Простой пример: подмножество с максимальной суммой

Это может быть легче понять, если детально проработать простой пример. Давайте рассмотрим следующую проблему:

Входные данные: набор целых чисел, целое число k Выходные данные: набор S U размера k , сумма которых максимально возможнаUk
SUk

Есть естественный жадный алгоритм для этой проблемы:

  1. Установите .S:=
  2. Для : i:=1,2,,k
    • Пусть будет наибольшим числом в U, которое еще не было выбрано (то есть, i- е наибольшее число в U ). Добавить е I в S .xiUiUxiS

Случайное тестирование показывает, что это всегда дает оптимальное решение, поэтому давайте формально докажем, что этот алгоритм правильный. Обратите внимание, что оптимальное решение уникально, поэтому нам не нужно беспокоиться о связях. Давайте докажем утверждение, изложенное выше:

SU,kOSOOO

SOixiOiSOS={x1,,xk}ix1,,xi1OOO={x1,x2,,xi1,xi,xi+1,,xn}x1,,xi1,xi,,xnx1,,xixi>xjjixi>xiO=O{xi}{xi}OiOxiOOxixixixi>0OO

OOOO

Oxixi

DW
источник
Это старый вопрос, но для меня это первый результат в Google. Линия then we can tweak O to get another solution O∗ that is different from O and strictly better than Oсмущает меня. Если существует несколько оптимальных решений, возможно, что они S != Oоба будут оптимальными; мы можем настроить O, чтобы быть «больше похожим» на S (создавая O ∗), и в то же время быть таким же хорошим, как (не strictly better than) O.
citelao
@citelao, мне жаль слышать, что это смутило тебя. Увы, я не уверен, как объяснить это более четко. Да, может быть несколько оптимальных решений с одинаковым значением. Это правильно. То, что вы написали, и то, что я написал, являются действительными; в этом нет противоречия. Разница в том, что то, что вы написали, не помогает доказать правильность жадного алгоритма; то, что я написал, делает. Я могу только предложить прочитать то, что я написал снова, и посмотреть, сможете ли вы выяснить, насколько полезно то, что я написал. Если это не поможет, возможно, найдите другую статью. Я понимаю, что это сложно и запутанно.
DW
1
Спасибо за быстрый ответ! Я упустил момент, когда вы сосредоточены на доказательстве алгоритма, если он есть a single, unique optimal solution. Поскольку этот вопрос касается проверки правильности любого жадного алгоритма, я хотел бы дать ответ для случаев, когда может существовать несколько оптимальных решений. Прошло много времени с тех пор, как я изучил все это, но разве этого недостаточно, чтобы доказать, что вы можете обменять каждый элемент O_i на любое оптимальное решение O, отличное от alg. решение S с S_i и до сих пор есть решение O ', которое не хуже, чем O?
citelao
@citelao, методика также применима к случаям, когда существует несколько оптимальных решений. Я предложил сосредоточиться на случае, когда оптимальное решение является уникальным только потому, что, когда вы впервые видите это, легче понять, как эти доказательства работают в такой ситуации. Но та же стратегия работает, даже если есть несколько оптимальных решений. Я предлагаю изучить это, убедившись, что вы понимаете, как это работает, когда существует единственное оптимальное решение, а затем применить его к общему случаю. Также я думаю, что это может помочь вам изучить несколько примеров доказательства жадных алгоритмов.
DW
Чтобы ответить на ваш последний вопрос, нет, этого недостаточно. Это не доказывает, что S является оптимальным. (Если вы только требуете, чтобы O 'был не хуже, чем O, есть случаи, когда S неоптимален, но возможно сделать такой обмен. Таким образом, доказательство того, что возможно достичь O', который не хуже, чем O, не ничего не докажу о том, является ли S оптимальным и не доказывает ли правильность жадного алгоритма. Предлагаю немного подробнее изучить метод, описанный в ответе. Это сложно. Доказательство от противоречия часто сложно понять.)
DW
14

Я буду использовать следующий простой алгоритм сортировки в качестве примера:

repeat:
  if there are adjacent items in the wrong order:
     pick one such pair and swap
  else
     break

Чтобы доказать правильность, я использую два шага.

  • Сначала я покажу, что алгоритм всегда завершается.
  • Затем я показываю, что решение, где оно заканчивается, - это то, которое я хочу.

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

AA[i]A[j]A[i]>A[j]i<j

A[i]A[i+1]A[i],A[i+1]

Это доказывает, что алгоритм в конечном итоге завершается.

Количество инверсий в отсортированном списке равно 0. Если все пойдет хорошо, алгоритм уменьшит количество инверсий до 0. Нам нужно только показать, что он не застревает в локальном минимуме.

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

A[i]A[j]i<jA[i]>A[j]iji+1<jA[i]<A[i+1]A[i+1]<A[j]A[i]<A[j]

Это доказывает, что алгоритм останавливается только после сортировки списка. И, следовательно, мы сделали.

adrianN
источник
Описанные методы настолько общие, что в них практически ничего не говорится о жадном алгоритме - теме этого вопроса.
Apass.Jack