§ 7. Сложность задач теории графов. Задача синтеза управляющих систем

На конечном графе почти всегда можно построить объект определенной конфигурации. Чтобы выбрать наилучшую, достаточно перебрать все возможные варианты ( построить все имеющиеся конструкции ) и выбрать наилучшее в том или ином смысле решение. Однако в большинстве случаев “переборный” способ решения задач такого рода не осуществим за любое реально мыслимое время, даже если использовать самые современные вычислительные машины. Поэтому составление алгоритмов с “разумным” временем их работы является актуальным. Иногда постановка задачи изменяется, и исследуются объекты, близкие к изучаемым первоначально. Часто задача об отыскании оптимального решения заменяется другой – найти решение, близкое к оптимальному. Иногда даже удается оценить, насколько полученное решение отличается от оптимального.

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

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

Алгоритм, трудоемкость которого ограничена полиномом от характерного размера задачи, называется эффективным.

Если трудоемкость ограничена более быстро растущей функцией, например, экспонентой, то соответствующий алгоритм – неэффективный.

Если не удается найти эффективного алгоритма, то остается возможность решить задачу методом полного перебора всех вариантов. При решении переборных задач большое значение имеет способ организации перебора. Наиболее употребительным является способ организации перебора, основанный на поиске в глубину с возвращениями (бэктрекинг – от англ. backtracking). Идея бэктрекинга состоит в следующем: имеется исходная ситуация, ее следует изменить для определения решения. Если изменение не привело к успеху, то выполняется возврат в исходную ситуацию, которая затем изменяется другим образом. Процесс продолжается до тех пор, пока не будут исчерпаны все возможности.

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

Для задачи коммивояжера метод полного перебора заключается в составлении п! всех возможных перестановок из п вершин графа (число городов), подсчете для каждой перестановки длины маршрута и выбора кратчайшего. Сложность при этом подходе определяется как О (п!). Известно, что п! растет быстрее, чем полином п или 2^п . Таким образом, решение задачи коммивояжера методом полного перебора является неэффективным.

Сложность алгоритма Краскала построения экстремального остова лучше определять как функцию числа ребер, а не числа вершин. Она, в свою очередь, зависит от того, насколько экономно удается организовать сортировку ребер, т.е. выполнить его первый этап. Алгоритм Краскала относится к типу “жадных” . Установлено, что в результате такого процесса будут эффективно рассортированы только r ребер и при этом будут выполнены операций, остальные m – r ребер не потребуется, где т – количество ребер в исходном графе. Для построения экстремального остова существует также алгоритм ближайшего соседа, сложность которого определяется как суммарное число сравнений весов всех ребер: , где т – число вершин в исходном графе; с – некоторая постоянная. Очевидно, сложность этого алгоритма есть величина порядка О (т³ ).

Таким образом, “жадный” алгоритм оказался эффективным, а полный перебор – нет.