Глава что такое комбинаторика. Основные проблемы изучения комбинаторики

Головоломка «15». Предполагается, что все ее видели и, вероятно, решали. Требуется восстановить нарушенный порядок квадратиков, причем желательно за минимальное число ходов. К тому же типу принадлежит более новая и сложная головоломка «кубик Рубика».
Это типичная задача с нефиксированной размерностью, поскольку элементами плана будут ходы, а их число заранее неизвестно. Если ставить задачу оптимизации, то в роли целевой функции будет число ходов.
Интересно, что если жульнически поменять местами два соседних квадратика, то задача не решается (научно говоря, множество допустимых планов пусто). Из этого следует, что в алгоритме решения должны быть какие-то средства определения, имеется ли решение для конкретной исходной конфигурации.
Шахматы. В сущности, шахматную игру (и многие другие игры) можно рассматривать как комбинаторную задачу выбора наилучших ходов. Можно рассматривать ее как задачу оптимизации, если считать, что целевая функция равна 1 при выигрыше белых, 0 – при ничьей и –1 – при выигрыше черных. Конечность каждой партии гарантируется «правилом 50 ходов», по которому в некоторых ситуациях затянувшаяся партия объявляется ничьей.
ГЛАВА 2. АЛГОРИТМ РЕШЕНИЯ КОМБИНАТОРНОЙ ЗАДАЧИ
2.1. Жадный алгоритм
Для многих оптимизационных задач есть более простые и быстрые алгоритмы, чем динамическое программирование. Многие задачи можно решать с помощью т.н. жадных алгоритмов. Такой алгоритм делает на каждом шаге локально оптимальный выбор, — в надежде, что итоговое решение также окажется оптимальным. Это не всегда так — но для многих задач такие алгоритмы действительно дают оптимум.

Задача о выборе заявок

Пусть даны заявок на проведение занятий в одной и той же аудитории. Два разных занятия не могут перекрываться по времени. В каждой заявке указаны начало и конец занятия ( и  для  -ой заявки). Разные заявки могут пересекаться, и тогда можно удовлетворить только одну из них. Мы отождествляем каждую заявку с промежутком  , так что конец одного занятия может совпадать с началом другого, и это не считается пересечением.
Формально говоря, заявки с номерами совместны, если интервалы  и  не пересекаются (иными словами, если  / или  ). Задача о выборе заявок состоит в том, чтобы набрать максимальное количество совместных друг с другом заявок.
Жадный алгоритм работает следующим образом. Мы предполагаем, что заявки упорядочены в порядке возрастания времени окончания:  . Если это не так, то можно отсортировать их за время  . Заявки с одинаковым временем конца располагаем в произвольном порядке.
Тогда алгоритм выглядит так:
1 
2 
3 
4 for  to n
5 do if 
6 then 
7 
Множество  состоит из номеров выбранных заявок,  — номер последней из них; при этом  , поскольку заявки отсортированы по возрастанию времени окончания. Вначале содержит заявку номер 1, и  (строки 2-3). Далее (строки 4-7) ищется заявка, начинающаяся не раньше окончания заявки номер . Если таковая найдена, она включается в множество и переменной присваивается её номер (строки 6-7).
Алгоритм требует всего лишь  шагов (не считая предварительной сортировки). Как и подобает жадному алгоритму, на каждом шаге он делает выбор так, чтобы остающееся свободным время было максимально.