Переборные алгоритмы на графах

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

1. Задача, решением которой является некоторая перестановка элементов полного множества. Примеры: проверка графов на изоморфизм, отыскание гамильтонова цикла и т. п. Решение такой задачи может быть сведено к генерации перестановок и проверке каждой перестановки, не является ли она решением. Альтернатива — генерация случайных перестановок до тех пор, пока решение не будет обнаружено или не закончится отведённое для этого время.

2. Задача, решением которой является подмножество. Здесь можно использовать генератор всех подмножеств.

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

Пример 1. Программа отыскания гамильтонова цикла. Она отлажена в оболочке Borland C++ 3.1 без использования объектов. Для разметки вершин исходного графа используется множество десятичных цифр. С клавиатуры для каждой вершины вводятся множества смежности.

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <string.h>

const int nmax = 100;

struct Node{ int d; Node * next; };

Node * LIST[ nmax ];

int NEW[ nmax ], L[ nmax ], X[ nmax ], n = 0, m = 0;

void GAM (int k)

{ Node * u;

if(k == n)

{ printf("<");

for (int i = 0; i < k; i++) printf("%2d", X[ i ]);

printf(">\n"); getch();

}

else

{ for (u = LIST[ X[ k-1 ] ]; u; u = u->next)

{ if (NEW[ u->d ])

{ NEW[ u->d ] = 0;

X[ k ] = u->d;

GAM(k+1);

NEW[ u->d ] = 1;

}

}

}

}

void main()

{ int i, j, f, G[ 10 ][ 10 ];

Node * v;

char s[20];

for(i = 0; i < 10; i++)

for(j = 0; j < 10; j++) G[ i ][ j ] = 0;

printf("\nGAM test ====================== (C)lgn, 16.10.03"

"\n Ввод списка смежности (строки цифр от 0 до 9)...\n");

do{

printf("v[%2d]=", n);

gets(s);

for (i = 0; i < strlen(s); i++)

{ j = s[ i ] – '0';

G[ n ][ j ] = G[ j ][ n ] = 1;

}

n++;

} while (strlen(s) && (n < 10));

//Формирование и вывод исходных данных

n = 0;

for (i = 0; i < 10; i++)

{ LIST[ i ] = 0;

G[ i ][ i ] = 0;

f = 0;

printf("\n%2d:", i);

for (j = 0; j < 10; j++)

if (G[ i ][ j ])

{ f++; v = new Node;

v->d = j; v->next = LIST[ i ]; LIST[ i ] = v;

printf(" %2d", j);

}

else printf(" –");

if (f) n++;

m += f;

}

printf("\n|V|=%2d, |E|=%2d", n, m/2);

//Тестирование функции GAM

for (i = 0; i < n; i++) NEW[ i ] = 1;

printf("\nГамильтонов путь: ");

X[0] = 0; NEW[0] = 0; GAM(1);

printf("\n ===== Конец =====\n"); getch();

}

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

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

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

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

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <time.h>

#include <iostream>

using namespace std;

const int N=10; //Количество вершин

int a[ N ][ N ], i, j, maxv = 0, k, st, ans[ N ], i1, num, K[ N+1 ], U[ N ];

void G(int k) //Перебор с возвратом

{ int i, i0;

if(k == 1) i0 = 0; else i0 = K[ k–2 ] + 1;

for(i = i0; i < N; i++)

if (U[ i ]) {

K[ k–1 ] = i; j = 0;

while ((j < k) && a[ K[ j ] ][ i ]) j++;

if (j+1 == k) { //Найдена клика...

if (k > maxv) {//больше предыдущей, зафиксировать решение

maxv = k;

for (i1 = 0; i1 < k; i1++)

ans[ i1 ] = K[ i1 ] + 1;

}

if (k == maxv) { //... и выдать

cout << ‘\n’ << " max=" << maxv << ": ";

for(i1 = 0; i1 < maxv; i1++)

cout << (K[i1] + 1) << " ";

_getch();

}

U[ i ] = 0; //Вершина (i) теперь занята

G(k+1); // Попробовать расширить решение

U[ i ] = 1; //Возврат: (i) снова свободна

}

}

}

void main(void)

{

setlocale(LC_ALL, "Russian");

srand(time(NULL));

//Генерация матрицы смежности неорграфа

for(i = 0; i < N; i++)

{ U[ i ] = 1;

for (j = i; j < N; j++)

if(j == i)

a[ i ][ j ] = 0;

else

a[ i ][ j ] = a[ j ][ i ] = rand() % 15 > 2;

}

if (N<21) { //Вывод на экран, если помещается

cout << ‘\n’ << "Матрица смежности";

cout << ‘\n’ << " 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20";

cout << ‘\n’ << "-----------------------------------------------------------------";

for (i = 0; i < N; i++)

{ cout << ‘\n’ << " "<< i+1 << " |";

for(j = 0; j < N; j++)

cout << " " << a[i][j] << " ";

}

}

//Эмпирический алгоритм - полиномиальной сложности

for (i = 0; i < N; i++)

{ K[0] = i;

for(st = i + 1; st < N; st++)

if(a[ i ][ st ])

{ k = 1;

for(j = st; j < N; j++)

{ num = 1;

while((a[ K[ num-1 ] ][ j ]) && (num <= k)) num++;

if ((num – 1) == k)

{ k++; K[ k–1 ] = j; }

}

if (k > maxv) //Зафиксировать решение

{ maxv = k;

for(i1 = 0; i1 < k; i1++) ans[ i1 ] = K[ i1 ] + 1;

}

if (k == maxv) { //... и выдать

cout << ‘\n’ << " max=" << maxv << ": ";

for (i1 = 0; i1 < maxv; i1++)

cout << (K[i1] + 1) << " ";

_getch();

}

}

}

cout << ‘\n’ << " Клика мощностью " << maxv <<" из вершин: ";

for(i = 0; i < maxv; i++)

cout << ans[i] << " ";

cout << ‘\n’ << " Контроль перебором";

maxv = 0;

G(1);

cout << ‘\n’ << "ИТОГ: мощность " << maxv <<", вершины: ";

for(i = 0; i < maxv; i++)

cout << ans[i] << " ";

_getch();

}

Результаты работы программы

Вариант 1. Граф из 9 вершин. Результаты работы двух алгоритмов совпадают.

Вариант 2. Количество вершин увеличено до 20. Эмпирический алгоритм начинает проигрывать.

Полный перебор нашёл целых 13 клик мощностью 9.

3.3.1. Практикум по теме

Выполнить курсовую работу по предложенному преподавателем индивидуальному заданию. Детальную постановку задачи взять из курса лекций и уточнить по рекомендованным литературным источникам. Реализовать алгоритм на языке С++.

Выбрать оптимальную структуру данных для представления графа в памяти ЭВМ. Реализовать граф как объект, а обработку — как метод для него. Результат обработки может быть или не быть частью объекта, способ его представления выбирается особо.

Для объекта должны быть объявлены все вспомогательные методы (методы по умолчанию) — конструкторы, деструктор и т. п. Использование ненужных методов блокируется на уровне компиляции или выполнения.

Стек и очередь (если нужны) реализуются как вспомогательные объекты. Рекомендуется использовать шаблоны классов.

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

Дополнительное требование: оценить возможный объём исходных данных для решения поставленной задачи для следующих ограничений:

— возможность вывода данных на экран;

— доступный объём памяти;

— получение решения за разумное время.

3.3.2. Содержание пояснительной записки к курсовой работе

1. Задание.

2. Выбор и обоснование способа представления данных.

3. Описание алгоритма и оценка его временной сложности.

4. Набор тестов и результаты проверки алгоритма на ЭВМ.

5. Выводы.

6. Список использованных источников.

7. Приложение: исходный текст программы для ЭВМ (на машинном носителе) с указанием, для какой программной оболочки текст подготовлен.