Полуинвариант
Полуинвариант — это величина, которая при каждом шаге процесса не изменяется или меняется только в одном направлении. Его используют, чтобы доказать завершение алгоритма, ограничить число ходов или исследовать позиции в игре.
Полуинвариант может сохранять значение на нескольких шагах, поэтому он слабее строгого моноварианта. Если на каждом шаге значение обязательно меняется хотя бы на единицу, полуинвариант помогает получить точную оценку числа шагов. Если оно иногда остаётся прежним, для доказательства завершения обычно выделяют несколько последовательных шагов или используют дополнительную величину.
Основное условие
Здесь \(s_i\) — состояние после \(i\)-го шага. Аналогично можно рассматривать неубывающий полуинвариант, ограниченный сверху. Важно проверять условие для каждого допустимого перехода, а не только для одного выбранного варианта.
На доске лежит \(n\) камней. За ход можно убрать один или два камня. Число камней \(F=n\) после каждого хода не возрастает, а при каждом ходе уменьшается хотя бы на единицу. Значит, \(F\) — полуинвариант, и игра завершится не более чем через \(n\) ходов.
Инвариант сохраняет одно и то же значение: \(F_{i+1}=F_i\). Полуинвариант допускает изменение, но только в одном направлении: например, \(F_{i+1}\le F_i\). Стратегия в игре может использовать полуинвариант, но сама по себе полуинвариантом не является.
Какое условие описывает неубывающий полуинвариант?
Главное
- Полуинвариант не обязан сохраняться: он только не возрастает или не убывает.
- Для доказательства завершения нужны направление изменения и ограничение величины.
- Полуинвариант слабее моноварианта, потому что может оставаться неизменным.