Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 17. Свойства и типы графов. Задача почтальона.На заданном графе необходимо найти цикл с минимальным числом ребер, в котором каждое ребро графа используется
|
|
Задача почтальона. На заданном графе необходимо найти цикл с минимальным числом ребер, в котором каждое ребро графа используется, по меньшей мере, раз (при этом разрешается использовать ребра многократно). Эта задача намного сложнее, чем задача поиска эйлерова пути, в то же время она намного легче, чем задача поиска гамильтонова пути.
Этап перехода от убеждения в том, что задача имеет решение, до того, как будет получено программное обеспечение, позволяющее решать эту задач на практике, может оказаться весьма продолжительным. С одной стороны, доказав, что задача допускает реализацию, исследователи не могут устоять перед соблазном не останавливаться подробно на многочисленных деталях, с которыми приходится иметь дело при разработке реализации; с другой стороны, они должны уделить внимание различным возможным ситуациям, которые в практических условиях не обязательно могут возникать. Этот разрыв между теорией и практикой ощущается особенно остро, когда исследования касаются алгоритмов на графах, что можно объяснить тем, что математические исследования заполнены глубокими результатами, описывающими ошеломляющее разнообразие структурных свойств, которые мы должны учитывать при обработке графов, а также тем, что связь между полученными результатами и свойствами графа, возникающая на практике, мало понятна. Разработка общих схем, таких как, например, сетевой симплексный алгоритм, представляет собой исключительно эффективный подход к решению подобного рода задач.
Задача обработки графов, неподдающаяся решению (intractable), — это задача, для которой не известен алгоритм, гарантирующий ее решение за приемлемый промежуток времени. Для многих таких задач характерно то, что для ее решения мы можем использовать метод решения " в лоб", в рамках которого можно попытаться воспользоваться любыми возможностями, чтобы найти решение путем вычислений, а неподдающимися решению мы их считаем в силу того факта, что таких возможностей слишком много. Это очень широкий класс задач, он включает в себя многие из важных задач, решение которых мы хотели бы знать. Для описания задач этого класса применяется термин NP-mpyд-ный (NP-hard, NP - non-linear polynomial - класс комбинаторных задач с нелинейной полиномиальной оценкой числа итераций). Многие специалисты убеждены в том, что эффективных алгоритмов решения этих задач не существует. В части 8 мы более подробно рассмотрим, что послужило причиной для такого рода убеждений и что стало основой для употребления этого термина. Задача поиска гамильтонова цикла, которую мы рассматривали в разделе 17.7, представляет собой прекрасный пример NP-трудной задачи обработки графа, равно как и указанные в приводимом ниже списке.
Самый длинный путь. Какой путь, соединяющий две заданных вершины графа, является самым длинным? Несмотря на все сходство этой задачи с задачей поиска кратчайшего пути, эта задача, тем не менее, есть версия задачи поиска гамильтонова пути, и посему, NP-трудная.
Задача окраски. Существует ли такой способ закрашивания каждой вершины графа одним из к цветов, чтобы ни одно ребро не соединяло вершин одного и того же цвета? Эта классическая задача легко решается для к = 2 (см. раздел 18.4), но она относится к числу NP-трудных задач уже при к = 3.
Часть 5. Алгоритмы на графах
Множество независимых вершин. Каким будут размеры наибольшего подмножества вершин графа, обладающих тем свойством, что никакие две из них не соединены ребром? Точно так же, как и в случае сопоставления задач нахождения эйлерова и гамильтонова путей, мы убеждаемся, что несмотря на кажущееся подобие проблеме сочетаний, которая решается за полиномиальное время, эта задача принадлежит к числу NP-трудных задач.
Клика. Каков размер максимальной клики (полного подграфа) в заданном графе? Эта задача обобщает часть задачи планарности, ибо если наибольшая клика состоит из более четырех узлов, граф не может быть планарным.
Эти задачи сформулированы как задачи существования - мы должны определить, существует или не существует подграф конкретного типа. Целью ряда других задач является определение размера наибольшего подграфа конкретного типа, что мы можем сделать, сводя задачу существования к проверке существования подграфа размера к, который обладает интересующим нас свойством, затем используем метод двоичного поиска для выявления наибольшего из них. На практике, однако, мы, по существу, часто стремимся отыскать полное решение, которое в общем случае найти гораздо труднее. Например, известная теорема четырех красок (four color theorem) утверждает, что можно воспользоваться четырьмя цветами для раскраски всех вершин планарного графа таким образом, что ни одно ребро не будет соединять две вершины одного и того же цвета. Однако теорема ничего не говорит нам о том, как это сделать для конкретного плоского графа: наше знание о том, что такая раскраска существует, ничем не может нам помочь в поиске полного решения этой задачи. Другой известный пример — это задача коммивояжера (traveling salesperson), по условиям которой требуется определить минимальный путь обхода вершин взвешенного графа. Эта задача относится к тому же классу задач, что и задача поиска гамильтонова цикла, при этом она нисколько не легче: если мы не можем найти эффективного решения задачи поиска гамильтонова пути, мы не можем рассчитывать на то, что найдем решение задачи коммивояжера. Как правило, сталкиваясь с трудными задачами, мы работаем с простейшими ее версиями, которые в состоянии решить. Задачи существования по духу соответствуют этому правилу, но они играют важную роль в теории, как мы убедимся, изучив материал части 8.
Перечисленные выше задачи — это всего лишь небольшая часть из нескольких тысяч NP-трудных задач, которые были выявлены. Они возникают во всех типах вычислительных приложений, как мы узнаем из части 8. Особенно много таких задач возникает при обработке графов, так что мы должны учитывать их существование на протяжении всей книги.
Обратите внимание, что мы настаиваем на том, чтобы предлагаемые нами алгоритмы гарантировали эффективность для худшего случая. Возможно, вместо этого мы должны ориентироваться на алгоритмы, которые эффективно работают на типовых входных данных (не обязательно для худшего случая). Аналогично, многие задачи требуют оптимизации. Возможно, мы должны преследовать цель найти длинный путь (не обязательно самый длинный) или большую клику (но не обязательно максимальную). С точки зрения обработки графов, может быть, легко найти хороший ответ для графов, которые встречаются на практике, и нас, скорее всего, не интересует алгоритм, который может найти оптимальное решение на некотором выдуманном графе, с которым никогда не доведется