Введение понятие комбинаторики

Задача о 8 ферзях. На шахматной доске размером 88 требуется расставить 8 ферзей так, чтобы они не били друг друга (т.е. никакие два ферзя не должны находиться на одной горизонтали, вертикали или диагонали).
Это задача поиска, если требуется найти хотя бы одну расстановку, либо задача перечисления, если нужно найти все возможные расстановки. В отличие от всех предыдущих примеров, задача не имеет никаких параметров. Это не семейство задач, а одна конкретная задача. Разумеется, она давно решена, число различных расстановок равно 92.
При желании можно параметризовать задачу, рассмотрев расстановку k ферзей на прямоугольной доске nm.
Головоломка «15». Предполагается, что все ее видели и, вероятно, решали. Требуется восстановить нарушенный порядок квадратиков, причем желательно за минимальное число ходов. К тому же типу принадлежит более новая и сложная головоломка «кубик Рубика».
Это типичная задача с нефиксированной размерностью, поскольку элементами плана будут ходы, а их число заранее неизвестно. Если ставить задачу оптимизации, то в роли целевой функции будет число ходов.
Интересно, что если жульнически поменять местами два соседних квадратика, то задача не решается (научно говоря, множество допустимых планов пусто). Из этого следует, что в алгоритме решения должны быть какие-то средства определения, имеется ли решение для конкретной исходной конфигурации.
Шахматы. В сущности, шахматную игру (и многие другие игры) можно рассматривать как комбинаторную задачу выбора наилучших ходов. Можно рассматривать ее как задачу оптимизации, если считать, что целевая функция равна 1 при выигрыше белых, 0 – при ничьей и –1 – при выигрыше черных. Конечность каждой партии гарантируется «правилом 50 ходов», по которому в некоторых ситуациях затянувшаяся партия объявляется ничьей.
3. Жадный алгоритм
Для многих оптимизационных задач есть более простые и быстрые алгоритмы, чем динамическое программирование. Многие задачи можно решать с помощью т.н. жадных алгоритмов. Такой алгоритм делает на каждом шаге локально оптимальный выбор, — в надежде, что итоговое решение также окажется оптимальным. Это не всегда так — но для многих задач такие алгоритмы действительно дают оптимум.