Я читаю "Введение в алгоритм" от CLRS. В главе 2 авторы упоминают «петлевые инварианты». Что такое инвариант цикла?
268
Я читаю "Введение в алгоритм" от CLRS. В главе 2 авторы упоминают «петлевые инварианты». Что такое инвариант цикла?
Ответы:
Проще говоря, инвариант цикла - это некоторый предикат (условие), который выполняется для каждой итерации цикла. Например, давайте посмотрим на простой
for
цикл, который выглядит следующим образом:В этом примере это верно (для каждой итерации), что
i + j == 9
. Более слабый инвариант, который также верен, таковi >= 0 && i <= 10
.источник
Мне нравится это очень простое определение: ( источник )
Сам по себе инвариант цикла мало что делает. Однако, учитывая соответствующий инвариант, он может быть использован, чтобы помочь доказать правильность алгоритма. Простой пример в CLRS, вероятно, связан с сортировкой. Например, пусть ваш инвариант цикла будет выглядеть примерно так: в начале цикла первый
i
сортируются записи этого массива. Если вы можете доказать, что это действительно инвариант цикла (т. Е. Что он выполняется до и после каждой итерации цикла), вы можете использовать это, чтобы доказать правильность алгоритма сортировки: при завершении цикла инвариант цикла все еще выполняется , а счетчикi
- длина массива. Следовательно, первыеi
записи отсортированы, что означает, что весь массив отсортирован.Еще более простой пример: инварианты циклов, корректность и вывод программ .
Я понимаю, что инвариант цикла является систематическим, формальным инструментом для рассуждения о программах. Мы делаем единственное утверждение, которое сосредотачиваемся на доказательстве истинности, и называем это циклическим инвариантом. Это организует нашу логику. В то же время мы можем неформально спорить о правильности какого-либо алгоритма, но использование инварианта цикла заставляет нас очень тщательно мыслить и гарантирует, что наши рассуждения будут герметичными.
источник
Есть одна вещь, которую многие люди не осознают сразу, имея дело с циклами и инвариантами. Они путаются между инвариантом цикла и условным циклом (условием, контролирующим завершение цикла).
Как указывают люди, инвариант цикла должен быть истинным
(хотя это может временно быть ложным во время тела цикла). С другой стороны, условное условие цикла должно быть ложным после завершения цикла, иначе цикл никогда не завершится.
Таким образом, инвариант цикла и условие цикла должны быть разными условиями.
Хорошим примером инварианта сложного цикла является бинарный поиск.
Таким образом, условный цикл кажется довольно простым - когда начало> конец цикла завершается. Но почему цикл правильный? Что такое инвариант цикла, который доказывает его правильность?
Инвариант - это логическое утверждение:
Это утверждение является логической тавтологией - оно всегда верно в контексте конкретного цикла / алгоритма, который мы пытаемся доказать . И он предоставляет полезную информацию о правильности цикла после его завершения.
Если мы вернемся, потому что мы нашли элемент в массиве, то утверждение явно верно, так как если
A[mid] == a
тогдаa
находится в массиве иmid
должно находиться между началом и концом. И если Завершает цикл , посколькуstart > end
тогда не может быть числа, чтоstart <= mid
иmid <= end
поэтому мы знаем , что заявлениеA[mid] == a
должно быть ложным. Однако в результате все логическое утверждение все еще верно в нулевом смысле. (В логике утверждение if (false) затем (что-то) всегда верно.)А как насчет того, что я сказал об условном цикле, который обязательно должен быть ложным, когда цикл завершается? Похоже, когда элемент найден в массиве, тогда условие цикла истина, когда цикл завершается !? На самом деле это не так, потому что подразумеваемый цикл действительно
while ( A[mid] != a && start <= end )
но мы сокращаем реальный тест, поскольку подразумевается первая часть. Это условие явно ложно после цикла независимо от того, как цикл завершается.источник
a
присутствует вA
. Неформально было бы, «если ключa
присутствует в массиве, он должен быть междуstart
иend
включительно». Из этого следует, что еслиA[start..end]
пусто, этогоa
нет в A.Предыдущие ответы очень хорошо определили инвариант цикла.
Ниже показано, как авторы CLRS использовали инвариант цикла для доказательства правильности сортировки .
Алгоритм сортировки вставкой (как указано в книге):
Инвариант цикла в этом случае: под-массив [от 1 до j-1] всегда сортируется.
Теперь давайте проверим это и докажем, что алгоритм корректен.
инициализация : до первой итерации j = 2. Таким образом, под-массив [1: 1] является массивом для тестирования. Поскольку у него есть только один элемент, он сортируется. Таким образом, инвариант выполняется.
Обслуживание : это можно легко проверить, проверяя инвариант после каждой итерации. В этом случае это выполняется.
Прекращение : это шаг, на котором мы докажем правильность алгоритма.
Когда цикл заканчивается, значение j = n + 1. Снова цикл-инвариант выполняется. Это означает, что под-массив [от 1 до n] должен быть отсортирован.
Это то, что мы хотим сделать с нашим алгоритмом. Таким образом, наш алгоритм правильный.
источник
Помимо всех хороших ответов, я полагаю, замечательный пример Джеффа Эдмондса из книги « Как думать об алгоритмах» может очень хорошо проиллюстрировать эту концепцию:
источник
Следует отметить, что инвариант цикла может помочь в разработке итерационных алгоритмов, если рассматривать утверждение, которое выражает важные отношения между переменными, которые должны быть истинными в начале каждой итерации и когда цикл завершается. Если это имеет место, вычисления находятся на пути к эффективности. Если false, алгоритм потерпел неудачу.
источник
Инвариант в этом случае означает условие, которое должно быть истинным в определенной точке каждой итерации цикла.
В контрактном программировании инвариант - это условие, которое должно быть истинным (по контракту) до и после вызова любого открытого метода.
источник
Значение инварианта никогда не меняется
Здесь инвариант цикла означает, что «изменение, которое происходит с переменной в цикле (увеличение или уменьшение), не изменяет условие цикла, т.е. условие удовлетворяет», так что концепция инварианта цикла пришла
источник
Свойство инварианта цикла - это условие, которое выполняется для каждого шага выполнения цикла (т. Е. Для циклов, циклов и т. Д.)
Это важно для циклического инвариантного доказательства, где можно показать, что алгоритм выполняется правильно, если на каждом этапе его выполнения выполняется свойство инвариантного цикла.
Чтобы алгоритм был корректным, инвариант цикла должен содержать:
Инициализация (начало)
Техническое обслуживание (каждый шаг после)
Прекращение (когда это закончено)
Это используется для оценки множества вещей, но лучший пример - жадные алгоритмы для взвешенного обхода графа. Чтобы жадный алгоритм давал оптимальное решение (путь через график), он должен достигать соединения всех узлов на пути с наименьшим возможным весом.
Таким образом, свойство инварианта цикла состоит в том, что выбранный путь имеет наименьший вес. В начале мы не добавляли ребер, поэтому это свойство имеет значение true (в данном случае это не false). На каждом шаге мы следуем по краю наименьшего веса (жадный шаг), поэтому мы снова выбираем путь с наименьшим весом. В конце мы нашли путь с наименьшим весом, поэтому наше свойство также верно.
Если алгоритм этого не делает, мы можем доказать, что он не оптимален.
источник
Трудно следить за тем, что происходит с петлями. Циклы, которые не заканчиваются или не заканчиваются без достижения их целевого поведения, являются распространенной проблемой в компьютерном программировании. Инварианты петли помогают. Инвариант цикла - это формальное утверждение о связи между переменными в вашей программе, которое сохраняется как раз перед тем, как цикл запускается (установление инварианта), и снова становится истинным в нижней части цикла, каждый раз в цикле (поддерживая инвариант ). Вот общая схема использования инвариантов цикла в вашем коде:
... // Здесь инвариант цикла должен быть истинным, в
то время как (TEST CONDITION) {
// верхняя часть цикла
...
// нижняя часть цикла
// Здесь инвариант Loop должен быть истинным
}
// Termination + Loop Invariant = Цель
...
Между верхом и низом петли, по-видимому, делается шаг к достижению цели петли. Это может нарушить (сделать ложным) инвариант. Суть инвариантов цикла - это обещание, что инвариант будет восстановлен перед повторением тела цикла каждый раз. В этом есть два преимущества:
Работа не переносится на следующий этап сложными, зависящими от данных способами. Каждый проход по циклу не зависит от всех остальных, а инвариант служит для связывания проходов в рабочее целое. Рассуждение о том, что ваш цикл работает, сводится к рассуждению о том, что инвариант цикла восстанавливается при каждом прохождении цикла. Это разбивает сложное общее поведение цикла на маленькие простые шаги, каждый из которых может рассматриваться отдельно. Условие проверки цикла не является частью инварианта. Это то, что заставляет цикл завершаться. Вы рассматриваете отдельно две вещи: почему цикл должен когда-либо завершаться, и почему цикл достигает своей цели, когда завершается. Цикл завершится, если каждый раз, проходя через цикл, вы приближаетесь к выполнению условия завершения. Это часто легко гарантировать: например, пошаговое изменение переменной счетчика до тех пор, пока она не достигнет фиксированного верхнего предела. Иногда обоснование прекращения является более сложным.
Инвариант цикла должен быть создан таким образом, чтобы при достижении условия завершения и инварианта «истина» цель достигалась:
invariant + termination => target
Требуется практика для создания простых и взаимосвязанных инвариантов, которые охватывают все достижения цели, кроме завершения. Лучше всего использовать математические символы для выражения инвариантов цикла, но когда это приводит к слишком сложным ситуациям, мы полагаемся на ясную прозу и здравый смысл.
источник
Извините, у меня нет разрешения на комментарии.
@ Томас Петричек, как вы упомянули
Как это инвариант цикла?
Я надеюсь, что я не ошибаюсь, насколько я понимаю [1] , инвариант цикла будет истинным в начале цикла (инициализация), он будет истинным до и после каждой итерации (обслуживание), а также будет истинным после Завершение цикла (Завершение) . Но после последней итерации i становится равным 10. Итак, условие i> = 0 && i <10 становится ложным и завершает цикл. Это нарушает третье свойство (Завершение) цикла инварианта.
[1] http://www.win.tue.nl/~kbuchin/teaching/JBP030/notebooks/loop-invariants.html
источник
Инвариант цикла - это математическая формула, такая как
(x=y+1)
. В этом примереx
иy
представляют две переменные в цикле. С учетом меняющегося поведения этих переменными на протяжении исполнения кода, практически невозможно проверить все возможностиx
иy
ценности и посмотреть , если они производят какую - либо ошибку. Допустим,x
это целое число. Целое число может содержать 32-битное пространство в памяти. Если это число превышает, происходит переполнение буфера. Поэтому мы должны быть уверены, что на протяжении всего выполнения кода он никогда не превышает это пространство. для этого нам нужно понять общую формулу, которая показывает связь между переменными. Ведь мы просто пытаемся понять поведение программы.источник
Проще говоря, это условие LOOP, которое выполняется в каждой итерации цикла:
В этом мы можем сказать, что состояние я
i<10 and i>=0
источник
Инвариант цикла - это утверждение, которое верно до и после выполнения цикла.
источник
В линейном поиске (согласно упражнению, приведенному в книге) нам нужно найти значение V в данном массиве.
Это просто, как сканирование массива от 0 <= k <length и сравнение каждого элемента. Если V найдено, или если сканирование достигает длины массива, просто завершите цикл.
Согласно моему пониманию в вышеупомянутой проблеме
Инварианты цикла (инициализация): V не найден в k - 1 итерации. Самая первая итерация, это будет -1, поэтому мы можем сказать, что V не найден в позиции -1
Обслуживание: В следующей итерации V не найден в k-1
Завершение: Если V находится в позиции k или k достигает длины массива, завершите цикл.
источник