3. Сравнение методов поиска гамильтоновых циклов

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

На рис. 10.6 показана зависимость требуемого алгоритмом Робертса и Флореса времени вычисления от числа вершин графа; степени вершин лежат в пределах 3 - 5. Ввиду сильных вариаций требуемого времени для графов одинаковых размеров приводятся три кривые, характеризующие среднее, максимальное и минимальное время, полученное для различных графов с одинаковым числом вершин. Следует заметить, что на рис. 10.6 применен полулогарифмический масштаб, что говорит об экспоненциальном характере зависимости. Формула, дающая приближенную зависимость времени Т от числа вершин п графа со степенями вершин в пределах 3 - 5, такова:

Г = 0,85.10~10* (секунд на CDC 6600).

Улучшенный вариант алгоритма Робертса и Флореса не намного лучше первоначального алгоритма. Необходимое время вычисления в нем все еще зависит (более или менее) экспоненциально от п. Зависимость отношения времен вычисления при использовании этих двух алгоритмов для неориентированных графов со степенями вершин 3 - 5 приведена на рис. 10.7. Из этого рисунка видно, что улучшенный вариант действительно хуже для графов малых размеров, хотя для больших графов (с более чем 20 вершинами) он позволяет сэкономить более 50% времени вычисления.

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

Напротив, метод Робертса и Флореса (или его улучшенный вариант) для достижения того же результата требует очень длительного поиска, так как в нем существенно перебираются все цепи, начинающиеся с 1, 6, 8, ... , прежде чем произойдет возвращение к 1, 6,. . . . Очевидно, что затрачиваемая работа зависит как от размера графа, так и от степеней вершин.

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

1,5 1,0 0,6 ОД

> 0.1 I

Г 0,05

: 0,025 : X

QOIO 0,005

Степени вершин в пределах 3-5

Максимальное необходи-змое время

i Среднее .чеооходимое время 3 Минимальное необходимое время

15 20

Число вершин

Рис. 10.6. Вычислительная реализация алгоритма Робертса и Флореса.

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

) Отсюда не следует делать вывод, что алгоритм гарантированно заканчивается за время, пропорциональное при некотором Л> 0. На самом деле можно подобрать примеры, которые.требуют намного большего времени, чем это показано на рис. 10.8. Такие контрпримеры строятся с помощью графов, не содержащих гамильтоновых циклов.

О 5 10 15 20 25 30 35 40 Число вершин

Рис. 10.7. Реализация улучшенного алгоритма Робертса и Флореса. - время вычисления для первоначального метода, - время вычисления для улучшенного метода.

§ 10

15 20 25 50 Число вершин

35 40

Рис. 10.8. Вычислительная реализация мультицепного алгоритма.