Моновариант
Моновариант — это величина, которая после каждого хода изменяется только в одну сторону: строго возрастает или строго убывает. Если она ограничена с другой стороны, процесс не может продолжаться бесконечно, поэтому моновариант помогает доказать завершение алгоритма или игры.
Как работает моновариант
Чтобы применить метод, нужно выбрать величину, зависящую от текущего состояния, и проверить два условия: после каждого допустимого хода она строго изменяется в одном направлении; её значения ограничены. Например, если натуральная величина уменьшается, она не может уменьшаться бесконечно: после конечного числа шагов достигнет нуля или минимально возможного значения.
Моновариант часто используют в задачах раздела продвинутых алгоритмов и вычислений. В игровых задачах он доказывает, что последовательность ходов закончится, а в алгоритмах — что цикл не является бесконечным.
На доске лежат 25 камней. За ход можно убрать 1, 2 или 3 камня. Возьмём моновариант \(M\) — число оставшихся камней. После каждого хода \(M\) строго уменьшается, а \(M \ge 0\). Поэтому бесконечная последовательность ходов невозможна: игра завершится не более чем за 25 ходов.
Моновариант изменяется строго в одном направлении после каждого хода. Полуинвариант может не изменяться на отдельных шагах, но не меняется в выбранную сторону в целом или после серии ходов. Поэтому для полуинварианта требуется более аккуратная проверка.
Какую величину удобно выбрать моновариантом, если на каждом шаге из очереди удаляют один элемент?
Главное
- Моновариант строго возрастает или строго убывает после каждого хода.
- Для доказательства завершения нужна граница: например, неотрицательная величина не может убывать бесконечно.
- Ищите число оставшихся объектов, нерешённых подзадач или возможных ходов.