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

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

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

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

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

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

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

(кликните для просмотра скана)

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

Вычислительные результаты, показанные на рис. 10.6 — 10.8, относятся к поиску одного гамильтонова цикла в графе. Небезынтересно сказать несколько слов о вычислениях с тремя алгоритмами, когда искались все гамильтоновы циклы. Так, для неориентированного графа с 20 вершинами со степенями вершин 3 —5 потребовалось чтобы найти все гамильтоновы циклы, следуя алгоритму Робертса и Флореса (этих циклов оказалось 18). Улучшенный вариант того же алгоритма потребовал 1,2 с, а мультицепной алгоритм — 0,07 с. Вычисления проводились на ЭВМ CDC 6600.