Глава 1. История формулировки задачи

Введение

Теория вычислительной сложности.

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

При появлении первых вычислительных машин, все находились в состоянии «эйфории» и предполагали, что все сделает машина. И действительно, для некоторых задач такой подход проходил, без каких-либо вопросов. Но чем больше ЭВМ эксплуатировалась, тем чаще стали замечать, что некоторые задачи решаются хорошо, а некоторые плохо. Сначала все сваливалось на пишущего программу, что якобы он не смог придумать хорошую программу, которая позволит решить исходную задачу. Позднее люди стали понимать, что никто ничего не может сделать, а значит что-то тут не так и дело не в людях.

В конце 60-х годов начала появляться теория вычислительной сложности, которая помогала сравнивать быстродействие алгоритмов и описывать время их исполнения, необходимый объем памяти, в зависимости от исходных данных.

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

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

Будем говорить, что f(n) =O(g(n)), если существует такая константа с, что f(n)≤c*g(n) для любого n≥0.

Полиномиальный алгоритм это алгоритм сложности O(p(n)), где p(n)-некоторая полиномиальная функция, а n-длина входных данных.

Класс NP-полных задач.

В классе NP-полных задач все задачи полиномиально сводимы друг к другу.

Началом теории NP-полных задач послужила работа С. Кука опубликованная в 1971 г. В своей работе он подчеркнул несколько важных аспектов данной теории.

Во-первых, он подчеркнул важность понятия “сводимость за полиномиальное время”, т.е. сводимость с помощью алгоритма полиномиальной сложности. Если одна задача сводится к другой, за полиномиальное время, то любой полиномиальный алгоритм решения второй задачи может быть превращен в алгоритм решения первой задачи.

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

В-третьих, С. Кук доказал, что одна конкретная задача из NP, называемая задачей о SAT, обладает теми же свойствами, что и любая другая задача из класса NP и может быть сведена к ней за полиномиальное время. Таким образом, получаем, что если задача о SAT может быть решена за полиномиальное время, то и всякая другая задача из класса NP полиномиально разрешима, а если какая-либо задача из класса NP труднорешаема, то и задача о SAT так же труднорешаема. Таким образом, «задача SAT» - самая трудная в классе NP.

Наконец С. Кук предположил, что и другие задачи из класса NP могут быть самыми трудными в этом классе, аналогично задаче о выполнимости.

Вслед за Куком Р. Карп предположил, что многие хорошо известные задачи из комбинаторики, сформулированные в виде задачи о распознавании, так же трудны, как и задача о выполнимости.

Вопреки тому, как считают многие специалисты, что NP-полные задачи труднорешаемы, прогресс в отношении опровержения или подтверждения данного предположения весьма незначителен. Однако, несмотря на отсутствие доказательства того, что из NP-полноты следует труднорешаемость, NP-полнота задачи означает, что для решения ее за полиномиальное время требуется крупное открытие.

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

Примеры NP-полных задач

· SAT

Условие:

Дан набор C={c₁,c₂,…,c_m}дизъюнкций на конечном множестве переменных U, таких, что |c_i| = 3, 1≤i≤m.

Вопрос:

Существует ли на Uнабор таких значений истинности, при котором выполняются все дизъюнкции из C?

· Вершинное покрытие (ВП)

Условие:

Дан граф G=(V, E) и положительное целое число K, K≤|V|.

Вопрос:

Имеется ли в графе G вершинное покрытие не более чем из K элементов, т.е. такое подмножество V' ⊆ V, что |V'|≤Kи для каждого ребра {u,v} ∈E хотя бы одна из вершин u или принадлежит V' .

· Гамильтонов цикл (ГЦ)

Условие:

Дан граф G=(V, E).

Вопрос:

Верно ли, что граф G содержит гамильтонов цикл, т.е. такую последовательность<v₁…v_n> вершин графа G, что n=|V|, {v_n,v₁}∈Eи{v_i,v_i+1}∈Eдля всех i, 1≤i≤n.

Для изучения нам нет смысла брать хитрые задачи, а достаточно рассмотреть одну из наиболее популярных задач-представителей данного класса – «задачу о коммивояжере».

Глава 1. История формулировки задачи

Есть nгородов. В одном из них живет коммивояжер. Будем считать этот город первым. Коммивояжеру надо объехать n-1 город и вернуться в первый. Каким образом ему надо проложить свой маршрут, чтобы проехать минимальное расстояние?

Эта проблема была сформулирована в 1934 году Гаслером Уитни. В то время еще не было приемлемых вычислительных методов и мало математических результатов относительно задачи.

В 1859 г. Гамильтон придумал игру «Кругосветное путешествие», в которой требовалось обойти 20 городов, расположенных в различных частях земного шара. Каждый город соединялся дорогами с тремя соседними так, что дорожная сеть образовывала 30 ребер додекаэдра, в вершинах которого находились города. Обязательными условиями являлись требования посетить каждую вершину однократно и вернуться в исходную вершину. Данная задача получила название «Гамильтоновы циклы».

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

Задача коммивояжера тесно связана с задачей о назначении и отличается от нее только тем, что в задаче о назначении не требуется цикличности.

Задача о назначениях состоит в том, чтобы обеспечить n работников n вакансиями, наиболее выгодным способом.

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

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

В 1950-е и 1960-е годы задача коммивояжера привлекла внимание ученых из США и Европы. Важный вклад в исследовании задачи принадлежит Джорджу Данцигу, Делберту Рею Фаркерсону и Селмеру Джонсону, которые в 1954 году в институте RAND Corporation сформулировали задачу в виде задачи дискретной оптимизации и разработали метод деления плоскостью для ее решения. Используя новый метод, они вычислили путь для отдельного набора узлов с 49 городами и доказали, что не существует более короткого пути. В 1960-е и 1970-е годы многочисленные группы исследователей изучали задачу с точки зрения математики и ее применения, например, в информатике, экономике, химии и биологии.

Ричард Карл в 1972 году доказал NP-полноту задачи поиска гамильтоновых путей, из чего, благодаря полиномиальной сводимости, вытекала NP-полнота задачи коммивояжера. На основе этих свойств им было приведено теоретическое обоснование сложности поиска решений на практике.

Больших успехов удалось достичь в конце 1970-х и1980-х годов, когда Мартин Грётчел, Манфред Падберг, Джованни Ринальди и другие, с применением новых методов деления плоскостью, ветвей и границ, вычислили решение для отдельного случая задачи с 2393 городами.

В 1990-е годы Дэвид Аплгейт, Роберт Биксби, Вашека Шватал и Уильям Кук установили рекорды по программе Конкорд. Герхард Райнельт создал TSPLIB-набор стандартизованных экземпляров задачи коммивояжера различной степени сложности для сравнения результатов работы различных групп исследователей. В марте 2005 года задача с 33810 узлами была решена программой Конкорд: был вычислен путь длиной 66048945 и доказано отсутствие более коротких путей. В апреле 2006 года было найдено решение для экземпляра с 85900 узлами. Используя методы декомпозиции, можно вычислить решения для случаев задачи с миллионами узлов, длина которых менее чем на 1% больше оптимальной.

Формулировка задачи.

Задача коммивояжера состоит в том, чтобы отыскать перестановку P={1, i2, i3 ….,n} из целых чисел от 1 до n, которая будет минимизировать сумму a_{1 i2} + a_{i2 i3}+…+a_{in 1}, где a_{j k} – расстояние между городами j и k. Поскольку у нас (n-1)! вариант возможной перестановки, то проблема заключается в нахождении оптимального метода нахождение нужной нам перестановки.