Часть 5. Алгоритмы на графах. 18.9. Анализ алгоритмов на графах

18.9. Анализ алгоритмов на графах

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

Как уже отмечалось в главе 2, мы стремимся - в идеальном случае - получить есте­ственные модели ввода данных, обладающие тремя важными свойствами:

■ Они с достаточной степенью точности отражают реальное положение вещей, что
делает возможным их применение для прогнозирования производительности.

■ Они достаточно просты, что делает возможным применение для их исследования
математического анализа.

■ Можно построить специальные генераторы экземпляров задач, которые можно
использовать для тестирования наших алгоритмов.

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

В таких областях, как сортировка и поиск, по указанным выше направлениям в час­тях 3 и 4 мы достигли определенных успехов. Мы можем анализировать алгоритмы, ге­нерировать случайные экземпляры задач и совершенствовать программные реализации с тем, чтобы получать высокоэффективные программы для использования в самых разно­образных практических ситуациях. В ряде других областей, которые мы также изучаем, могут возникнуть различные трудности. Например, математический анализ, который мы хотели бы применить на достаточно высоком уровне, остается для нас недоступным при решении многих геометрических задач, а разработка точной модели ввода все еще оста­ется трудной проблемой для многих алгоритмов обработки строк (в самом деле, на эту часть приходится существенная часть вычислений). Аналогично, алгоритмы на графах приводят нас к ситуации, когда во многих приложениях мы вынуждены ходить по тон­кому льду в попытках найти нужные решения с учетом всех трех свойств, которые толь­ко что были отмечены:

■ Возможности математического анализа ограничены, вследствие чего многие важ­
ные вопросы на стадии анализа остаются без ответа.

■ Существует большое разнообразие различных типов графов, и мы не в состоянии
адекватно проверить предложенные алгоритмы на всех типах графов.

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

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