Уровни решения комбинаторных задач

1. Начальный уровень.

Задачи поиска хотя бы одного решения, хотя бы одного расположения объектов, обладающих заданным свойствами.

• — отыскание такого расположения десяти точек на пяти отрезках, при котором на каждом отрезке лежит по четыре точки;
• — такого расположения восьми ферзей на шахматной доске, при котором они не бьют друг друга.

Иногда удаётся доказать, что данная задача не имеет решения (например, нельзя расположить 10 шаров в 9 урнах так, чтобы в каждой урне было не более одного шара — хотя бы в одной урне окажется не менее двух шаров).

2. Второй уровень.

Если комбинаторная задача имеет несколько решений, то возникает вопрос о подсчете числа таких решений, описании всех решений данной задачи.

3. Третий уровень.

Решения данной комбинаторной задачи отличаются друг от друга некоторыми параметрами. В этом случае возникает вопрос отыскания оптимального варианта решения такой задачи.

Например:

Путешественник хочет выехать из города А, посетить города В, С, и D. После чего вернуться в город А.

На рис. изображена схема путей, связывающих эти города. Различные варианты путешествий отличаются друг от друга порядком посещения городов В, С, и.D. Существует шесть вариантов путешествия. В таблице указаны варианты и длин каждого пути: