Вопросы для самоконтроля

1. В чем состоит идея алгоритма Робертса–Флореса?

2. Опишите последовательность построения гамильтонова цикла в графе с помощью алгоритма Робертса–Флореса.

3. Какова сложность алгоритма Робертса─Флореса?

4. В чем состоит идея алгебраического метода?

5. Опишите последовательность построения гамильтонова цикла в графе с помощью алгебраического метода.

6. Какова сложность алгебраического метода при построении одного гамильтонова цикла?

7. Какова сложность алгебраического метода при построении всех гамильтоновых циклов в графе?

8. В чем заключается отличие стратегии работы алгоритмов Робертса–Флореса и алгебраического?

9. Для решения каких задач следует применять алгоритм Робертса–Флореса?

10. В каких случаях применение алгебраического метода является эффективным?

Задания для самостоятельной работы

1. Для произвольного графа постройте, используя алгоритм Робертса–Флореса, гамильтонов цикл.

2. Запишите структурную схему алгоритма Робертса–Флореса для построения гамильтонова цикла.

3. Приведите словесное описание метода Робертса–Флореса.

4. Для произвольного графа постройте гамильтонов цикл, используя алгебраический метод.

5. Запишите структурную схему алгебраического метода для построения гамильтонова цикла.

6. Приведите словесное описание алгебраического метода.

7. Задайте граф на 7 вершин и постройте все гамильтоновы циклы методом Робертса–Флореса.

8. Задайте граф на 7 вершин и постройте все гамильтоновы циклы алгебраическим методом.

9. Запишите псевдокод алгоритма Робертса–Флореса.

10. Запишите псевдокод алгебраического метода.

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

16.3. Задача о коммивояжере и алгоритмы ее решения

16.3.1. Алгоритм Хелда и Карпа

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

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

Идея алгоритма Хелда – Карпа состоит в следующем. Сначала определяются все кратчайшие пути, соединяющие вершину x₁ с остальными вершинами. Затем определяются кратчайшие пути от вершины x₁ до всех остальных вершин графа, через одну промежуточную вершину, после этого через две и т.д., до n – 1 шага. Затем к полученным результатам добавляется длина пути для возвращения в вершину x₁. Из всех полученных вариантов пути выбирается тот, которому соответствует наименьшая сумма весов ребер. Основным недостатком данного метода является необходимость выполнить полный перебор всех возможных вариантов, что для задач большой размерности практически невозможно.