"Информатика (базовый и углублённый уровни) (в 2 частях)", Поляков К.Ю., Еремин Е.А.
Оптимизация — поиск наилучшего решения среди вариантов, которые удовлетворяют заданным условиям. Чтобы решить такую задачу, нужно определить переменные, задать критерий сравнения и записать ограничения. Затем находят допустимые решения и выбирают среди них лучшее: например, с наибольшей ценностью или наименьшей стоимостью. Полный перебор позволяет проверить все варианты, но перед его применением оценивают, сколько времени займёт проверка.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Оптимизационная задача — задача, в которой нужно найти наилучшее решение по заданному критерию. Например, можно искать самый дешёвый маршрут или набор с наибольшей ценностью. Это определение помогает отличить оптимизацию от задачи, где требуется просто найти любой подходящий вариант.
Целевая функция — величина, значение которой требуется максимизировать или минимизировать. Её записывают через переменные задачи: например, стоимость может зависеть от количества купленных товаров. Целевая функция нужна, чтобы выразить словами сформулированную цель в виде, по которому можно сравнивать решения.
Ограничения — условия, которым должны удовлетворять допустимые решения. Они могут задавать предел времени, вместимость, бюджет или связь между переменными. Без ограничений модель могла бы предлагать невозможные в реальной ситуации варианты, поэтому каждое существенное условие записывают явно.
Оптимальное решение — допустимое решение, при котором целевая функция достигает наилучшего значения. При максимизации оно даёт наибольшее значение, а при минимизации — наименьшее. Это понятие позволяет проверить не только выполнимость условий, но и то, что среди разрешённых вариантов выбран лучший.
Сначала практическую ситуацию переводят в формальную модель. Для этого выделяют переменные — неизвестные значения, которыми можно управлять, — и определяют, что именно нужно улучшить. Затем записывают целевую функцию через переменные и формулируют ограничения в виде равенств или неравенств. Такой порядок нужен, чтобы исходные слова не потеряли смысл: каждая переменная отвечает за конкретный выбор, а каждое условие отражает реальное требование.
После построения модели сначала находят множество допустимых вариантов, а уже потом сравнивают их. Причина в том, что значение цели само по себе не делает решение осуществимым: например, минимальная цена поездки не подходит, если поездка длится дольше разрешённого времени. Ограничения отделяют возможные варианты от невозможных. Критерий оптимальности применяют только к оставшимся, иначе можно ошибочно объявить лучшим заведомо непригодный ответ.
Полный перебор устроен просто: алгоритм по очереди рассматривает все допустимые варианты, вычисляет для каждого целевую функцию и запоминает лучший результат. При максимизации сохраняют вариант с наибольшим значением, при минимизации — с наименьшим. Такой способ надёжен, потому что каждый кандидат получает проверку, и никакой непроверенный вариант не может оказаться лучше найденного. Надёжность сохраняется лишь при условии, что список вариантов полный и вычисления верны.
Недостаток полного перебора — большое время работы, если вариантов очень много. Например, при выборе каждого из n предметов отдельно «взять или не взять» образуется 2ⁿ наборов, поэтому увеличение числа предметов резко увеличивает объём проверки. Оценка количества вариантов заранее показывает, реалистично ли дождаться результата. Если перебор слишком велик, ищут другой алгоритм или используют свойства задачи, позволяющие отбрасывать части вариантов.
Найденный ответ проверяют в два этапа. Сначала подставляют его в ограничения и убеждаются, что он допустим; затем выясняют, действительно ли его целевая функция не хуже значений у остальных допустимых решений. При полном переборе второй этап подтверждается тем, что проверены все варианты. Если используется другой метод, требуется обоснование, почему он не пропустил решение с лучшим значением.
Таблица показывает, из каких частей складывается модель и как различаются решение, допустимость и оптимальность. Пример в последнем столбце условный: в конкретной задаче значения переменных и сами ограничения задаются её условием. Используйте таблицу как проверочный список при составлении модели.
| Элемент | Что означает | Пример |
|---|---|---|
| Переменные задачи | Величины или выборы, которыми описывают решение | x и y — стороны прямоугольника |
| Целевая функция | Критерий, который нужно максимизировать или минимизировать | S = xy — площадь прямоугольника |
| Ограничения | Условия, которым должны удовлетворять переменные | 2x + 2y = P, где P — заданный периметр |
| Допустимое решение | Набор значений переменных, удовлетворяющий ограничениям | Стороны положительны, а периметр равен P |
| Оптимальное решение | Допустимый вариант с наилучшим значением цели | Допустимые стороны, дающие наибольшую площадь |
Задача 1. Прямоугольник заданного периметра. Требуется выбрать длину и ширину так, чтобы площадь была наибольшей. Обозначим стороны x и y, а заданный периметр — P. Так можно выразить обе части модели через одни переменные.
Ответ: стороны прямоугольника должны быть равны P/4, то есть он должен быть квадратом. Ограничение по периметру выполнено, а площадь максимальна при равных сторонах.
Задача 2. Выбор поездки. Из нескольких вариантов нужно выбрать самый дешёвый, но время в пути не должно превышать заданное. Для каждого варианта известны стоимость и длительность. Сравнивать нужно только те поездки, которые укладываются в ограничение времени.
Ответ: выбирают поездку с наименьшей стоимостью среди тех, что не превышают допустимое время. Если несколько вариантов имеют одинаковую минимальную цену, оптимальными будут все они.
Задача 3. Выбор предметов в груз. У каждого предмета известны масса и ценность, а вместимость ограничена. Нужно выбрать набор с наибольшей суммарной ценностью, не превысив грузоподъёмность. Этот пример показывает, как полный перебор сравнивает целые наборы, а не отдельные предметы.
Ответ: оптимален допустимый набор с наибольшей суммарной ценностью. Конкретный состав груза зависит от масс, ценностей и грузоподъёмности, указанных в условии.
Искать решение, не задав критерий оптимальности. Без целевой функции непонятно, что значит «лучше»: один вариант может быть дешевле, другой — быстрее. Такую ошибку допускают, когда сразу начинают выбирать на глаз. Проверьте себя: сформулируйте, какую именно величину и в какую сторону нужно улучшить.
Забывать ограничения или проверять их только после выбора. Тогда привлекательный по цели вариант может оказаться невозможным. Это происходит, если условие задачи сводят к одному критерию и теряют остальные требования. Подставьте кандидата во все ограничения до сравнения с другими.
Считать первый подходящий вариант оптимальным. Первый найденный вариант доказывает только то, что решение существует, но не то, что оно лучше остальных. Ошибка возникает, когда поиск останавливают сразу после выполнения условий. Проверьте оставшиеся варианты или используйте метод, который обосновывает их отбрасывание.
Запускать полный перебор, не оценивая число вариантов. Для небольшой задачи он удобен, но при быстром росте количества комбинаций вычисления могут затянуться. Часто объём недооценивают, считая только число объектов, а не число их сочетаний. Перед запуском оцените количество проверок и сопоставьте его с доступным временем.
Для оптимизации нужно уметь формализовать условие задачи: вводить переменные и переводить слова в логические условия, равенства и неравенства. Это связывает тему с математическими моделями и логикой. Полный перебор относится к алгоритмам перебора, а оценка количества вариантов — к анализу сложности алгоритмов. На практике оптимизационные модели помогают планировать затраты и распределять ограниченные ресурсы.
Чем оптимизационная задача отличается от обычной задачи на поиск решения?
В обычной задаче достаточно найти вариант, который удовлетворяет условию. В оптимизационной нужно выбрать лучший из допустимых вариантов по заданному критерию — например, самый дешёвый или наиболее ценный.
Можно ли иметь несколько оптимальных решений?
Да. Несколько допустимых вариантов могут давать одно и то же наилучшее значение целевой функции. Тогда каждый из них является оптимальным.
Как понять, что вариант решения допустимый?
Нужно подставить его значения в ограничения и проверить каждое условие. Если все условия выполнены, вариант допустим; если нарушено хотя бы одно, его нельзя выбирать.
Всегда ли для оптимизации нужно перебирать все варианты?
Нет. Полный перебор подходит, когда допустимых вариантов не слишком много. Для больших задач могут использовать более эффективные алгоритмы, а число вариантов оценивают заранее.
Как проверить, что найденное решение действительно оптимально?
Сначала проверяют, что решение допустимо, затем подтверждают, что его значение целевой функции не хуже значений у остальных допустимых вариантов. При полном переборе для этого нужно проверить все такие варианты.
§ 72. Оптимизация
