Одно решение, много решений, ни одного
Исследовать число допустимых моделей · Создавать минимальный конфликт
В этом занятии
- Исследовать число допустимых моделей
- Создавать минимальный конфликт
- Проверять устойчивость вывода при удалении посылки
Пригодится: Рекомендуем сначала пройти «Хватит ли каждому своего места?».
Разберёмся перед практикой+
Одно решение, много решений, ни одного
Множество решений содержит все назначения, которые выполняют каждое требование одновременно. Новое требование пересекает это множество со своим множеством допустимых случаев. Поэтому добавление ограничения не может увеличить число решений: оно оставляет прежнее число или уменьшает его.
Если решений нет, полезно найти небольшой конфликтующий набор. Он минимален по удалению, если весь набор несовместим, но удаление любого его условия возвращает хотя бы одно решение. Минимальный здесь не обязательно означает самый маленький среди всех конфликтов: это разные утверждения.
Единственное решение делает некоторые сведения определёнными, но не доказывает истинность модели в реальности. Возможно, вы забыли допустимый вариант или неверно переписали требование. Надёжный вывод включает границы пространства: какие значения и какие связи разрешены в условии.
В мастерской сначала предложите одно решение вручную. Затем сравните его с полным списком и попробуйте удалить условие. Отдельно проверяйте, какая часть ответа остаётся одинаковой во всех моделях: порядок пары может быть определён даже при нескольких полных очередях.
Для трёх дел заданы А раньше Б, Б раньше В и В раньше А. Что произойдёт при удалении последнего требования?
- Три стрелки замыкают цикл, поэтому полного порядка нет.
- Удаляем В раньше А; остаётся цепочка А раньше Б раньше В.
- Теперь есть ровно одна очередь АБВ. Аналогично удаление любой стрелки разрывает этот цикл.
Загружаем интерактивную модель…
Попробуйте самостоятельно
Запишите рассуждения в черновик или сделайте построение на бумаге. Эти задания для самостоятельной работы: автоматической проверки и XP за них пока нет.
- В модели собери конфликт из трёх требований и проверь его минимальность удалением каждого.
- Составь два разных решения и найди утверждение, истинное в обоих.
Читайте и разбирайте пример в своём темпе. К практике можно перейти, когда будете готовы.