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

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

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

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

Наконец, пятая задача дает представление о классе задач, которые считаются еще более сложными.

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

Графы обычно изображаются так, как показано на рис. 1.3; узлы изображаются маленькими кружками, а ребра — отрезками, соединяющими два конца.

Перейдем к обсуждению пяти типичных задач.

a



Рис. 1.3. Примеры графов с четырьмя узлами


<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Пять типичных задач:

  1. ПЯТЬ СЛОВ
  2. ПОРТРЕТЫ ТИПИЧНЫХ «НЕСЧАСТНЫХ»
  3. Глава 3 ПЯТЬ ТОНКИХ ТЕЛ
  4. Статья 630. Типичные условия договора
  5. 5.9. ТИПИЧНЫЙ СЮРПРИЗ
  6. Микростратегии и пять чувств
  7. Типичная игра
  8. 2. Типичная игра
  9. ПОРТРЕТ ТИПИЧНОГО АЛКОГОЛИКА
  10. Пять переменных У. Мичела.
  11. 3.10. ТИПИЧНЫЙ ПОТОК ОБРАЗОВ
  12. ПОРТРЕТ ТИПИЧНОГО АГРЕССОРА
  13. Некоторые типичные сценарии
  14. Некоторые типичные сценарии
  15. ПЯТЬ УРОВНЕЙ ВЕРХНЕГО МИРА
  16. ПЯТЬ УРОВНЕЙ ВЕРХНЕГО МИРА