![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Часть 5. Алгоритмы на графах. 18.9. Анализ алгоритмов на графах
Нам предстоит рассмотреть широкий набор задач обработки графов и методов их решения, в связи с чем мы не всегда сравниваем различные многочисленные алгоритмы решения одной и той же задачи. Тем не менее, всегда полезно набраться опыта работы с алгоритмами, проверяя их на реальных данных или на специально подготовленных и понятных нам данных, обладающих свойствами, которые мы можем обнаружить в фактических применениях. Как уже отмечалось в главе 2, мы стремимся - в идеальном случае - получить естественные модели ввода данных, обладающие тремя важными свойствами: ■ Они с достаточной степенью точности отражают реальное положение вещей, что ■ Они достаточно просты, что делает возможным применение для их исследования ■ Можно построить специальные генераторы экземпляров задач, которые можно Имея в своем распоряжении эти три компонента, мы можем приступать к реализации сценария со стадиями разработки, анализа, реализации и тестирования, который позволяет создавать эффективные алгоритмы решения практических задач. В таких областях, как сортировка и поиск, по указанным выше направлениям в частях 3 и 4 мы достигли определенных успехов. Мы можем анализировать алгоритмы, генерировать случайные экземпляры задач и совершенствовать программные реализации с тем, чтобы получать высокоэффективные программы для использования в самых разнообразных практических ситуациях. В ряде других областей, которые мы также изучаем, могут возникнуть различные трудности. Например, математический анализ, который мы хотели бы применить на достаточно высоком уровне, остается для нас недоступным при решении многих геометрических задач, а разработка точной модели ввода все еще остается трудной проблемой для многих алгоритмов обработки строк (в самом деле, на эту часть приходится существенная часть вычислений). Аналогично, алгоритмы на графах приводят нас к ситуации, когда во многих приложениях мы вынуждены ходить по тонкому льду в попытках найти нужные решения с учетом всех трех свойств, которые только что были отмечены: ■ Возможности математического анализа ограничены, вследствие чего многие важ ■ Существует большое разнообразие различных типов графов, и мы не в состоянии ■ Выявление отличительных признаков типов графов, которые появляются в прак Графы являются достаточно сложными структурами, и часто нам не удается в полной мере выявить основные свойства графов, с которыми нам приходится сталкиваться на практике, или искусственных графов, которые мы, возможно, можем строить и анализировать.
|