Реализация алгоритма полного перебора

Любая найденная в программе ошибка – не последняя

Закон Мерфи

Цель работы – научиться реализовать алгоритм решения оптимизационной «задачи о камнях» методом полного перебора (4 час. на 1 студента, 2час. на бригаду из двух студентов, 1час. на бригаду из четырех и т.д.).

Постановка задачи.

Сущность любой оптимизационной задачи сводится к тому, что вы должны отыскать такое наилучшее (лысоголовые говорят «оптимальное») сочетание варьируемых параметров (т.е. тех, которые вы можете изменять), которое бы соответствовало наилучшему решению, т.е. экстремальному значению некоторой целевой функции. Вот живой пример из (студенческой) жизни. Вы иногородний, живете в общежитии или «на уголке» и у вас есть счастливая возможность один раз в неделю (в две недели, в месяц …) приехать домой к родителям и набрать рюкзак продуктов весом до 20 (10 или 30 или …) кг. Какие же продукты следует взять, если, конечно, у вас есть выбор? Если исходить только из энергетической ценности продуктов, то, например, выгоднее всего взять 20 кг сала, или шоколада или сала в шоколаде и т.д. Очевидно, чтобы, как говорится, «не слиплось», надо взять все-таки разные продукты: сало, картофель, те же огурцы и т.д. и др. вкусненькое и полезное. Так что же взять при наличии ограничения в весе рюкзака? Чтобы решить эту проблему, вы и должны составить (придумать, написать) так называемую целевую функцию (произносится как «хвункція»). Даже в данном съедобном случае она будет выглядеть достаточно сложной, так как вам предстоит для каждого из кандидатов на попадание в ваш рюкзак задать некоторые коэффициенты, обычно называемые «весовыми» теми же лысоголовыми:

§ количество удовольствия на кг веса;

§ степень обязательности наличия в рационе (хоть огурцы и не очень калорийны, но они ведь должны быть в рационе!);

§ энергетическая ценность в тех же ККал;

§ стоимость в грв. и т.д. и т.п.

Ну, в целом, вы и так понимаете сущность, сложность и, главное, ценность оптимального решения этой жизненно важной задачи.

Ну а при чем же здесь «задача о камнях», вопросит, как говорят писатели, «внимательный читатель»? А очень просто: у вас нет рюкзака, а есть две сумки и две (соответственно?), руки, и вам требуется распределить продукты по двум сумкам так, чтобы разность их веса была минимальной, так как в противном случае у вас будет искривление позвоночника (сколиоз по-научному). Если всего вам удалось добыть «у предков» 20 видов харчей и вы захотите путем прямого перебора на практике (т.е. путем загрузки сумок и их последующего взвешивания) найти наилучший вариант распределения снеди по двум сумкам, то вам придется в общем случае перебрать около 2²⁰ вариантов, а это примерно 1 млн. Успеете до отправления электрички, еще в этой жизни?

Замечание. Если вы и ваши родители живут в Харькове, то не думайте, что вам не надо выполнять эту лабу. Для того чтобы попасть в универ вовремя и с минимальными потерями денежных средств, времени и нервов (или чтобы еще и поспать во время поездки или, не приведи господи такому присниться, выполнить домашнее задание) вам предстоит из множества вариантов маршрутов городского транспорта с учетом стоимости проезда, времени в пути, интервалов движения, вероятности занять сидячее место и др. значимых для вас факторов выбрать оптимальный маршрут. Короче говоря – вы тоже должны делать эту лабу.

Дата добавления: 2014-12-26