Пять типичных задач

Задача устойчивых паросочетаний служит превосходным примером процесса проектирования алгоритма.

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

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

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

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

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

В контексте текущего обсуждения граф G достаточно рассматривать просто как способ представления попарных отношений в группе объектов. Таким образом, G состоит из пары множеств (V, E) — набора узлов V и набора ребер E, каждое из которых связывает два узла. Таким образом, ребро e Ѯ E представляет двухэлементное подмножество V: e = {u, v} для некоторых u, v Ѯ V; при этом u и v называются концами e.