Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

“ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ НЕФТЕГАЗОВЫЙ УНИВЕРСИТЕТ”

КАФЕДРА ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

КУРСОВАЯ РАБОТА

По дисциплине “Дискретная математика”

Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов. Выполнил

Студент группы

АСОиУзс-07-01

Быстров Евгений М.

Шифр: 742301020016500

Проверил

Гапанович И. В..

Тюмень 2008

Содержание.

1. Введение. Постановка задачи.3
2. Назначение и область применения.3
3. Описание алгоритма решения задачи.3
4. Ручной просчет.4
5. Описание программы.6
6. Тестирование программы.7
7. Литература.9
8. Приложение 1. Листинг программы.10

1. Введение. Постановка задачи.

Задание на курсовую работу по дисциплине “Дискретная математика”.

Студент группы АСОиУзс-07-01 Быстров Евгений М.

Специальность “Автоматизированные системы обработки информации и управления”

Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов.

ЗАДАНИЕ 13 . Построить гамильтонову цепь в графе, используя алгоритм с возвратом.

Определения.

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

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

Граф G называется связным, если для любых двух его вершин существует маршрут, их соединяющий, то есть любая вершина достижима из любой вершины.

Матрица смежности графа – квадратная матрица, показывающая взаимосвязь вершин и ребер.

2. Назначение и область применения.

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

3. Описание алгоритма решения задачи.

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

Для того, что сократить число шагов в предложенном методе, рассмотрим следующий алгоритм. Предположим, что решение имеет вид последовательности v1…vi. Идея метода состоит в следующем: решение строится последовательно, начиная с пустой последовательности (длины 0). Далее, имея частичное решение ищем такое допустимое значение vi+1, которое еще не было использовано, добавляем его к пройденному частичному решению и продолжаем процесс для нового частичного решения v1…vi+1. В противном случае, если такого значения vi+1 не существует, возвращаемся к предыдущему частичному решению v1…vi-1 и продолжаем процесс, пытаясь определить новое, еще не использованное допустимое значение vk. Такие алгоритмы носят название “алгоритмы с возвратом”. Процесс поиска с возращением будет продемонстрирован в разделе “Ручной просчет” и “Тестирование программы” на примерах, показывающих как работает программа.

Алгоритм работы программы:

Создается пустая последовательность цепи длиной v (количество вершин). Создается динамический массив для таблицы смежности графа, который заполняется из файла или прямо из программы. Начинается поиск цепи с первой вершины (нулевая для матрицы). Поочередно просматривается матрица смежности циклом for(где i – строка, j – столбец). Если от вершины идет ребро, то проверяем была ли уже такая вершина. Если такая вершина уже есть в пути, то выходим из цикла и ищем следующую вершину. Если такой вершины не было, то записываем вершину в путь и продолжаем поиск с найденной вершины. Здесь же проверяем: если это последняя j-тая вершина, а ребер больше нет, то проверяем готова ли цепь, если последняя вершина пути не пуста, то цепь найдена. Если цепь не готова, записываем частичное решение сначала в переменную временной цепи (tempput), затем сравниваем это значение пути с уже имеющимися, если найдено совпадение, то возвращаемся на предыдущую вершину, а если такого пути не было, то записываем неполный путь в список временных путей.

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

Когда гамильтонова цепь найдена, она выводится в окно “Результат”. Список частичных решений выводится в окно “Ход поиска цепи”.

4. Ручной просчет.

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

Возьмем для примера следующий граф:

0, 1, 2, 3 – вершины графа;

Ребра графа;

Гамильтонова цепь в графе.

Рис. 1 Граф.

Теперь покажем дерево данного графа:

0312 – гамильтонова цепь

Рис. 2 Дерево графа.

Составим матрицу смежности для данного графа:

V0123
00101
11011
20100
31100

0 – если между вершинами нет ребра

1 – если между вершинами есть ребро (или петля)

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

Расчет происходит так: сначала программа создает пустую цепь длиной 4 символа. Создается массив куда заносятся элементы матрицы. Берет первый элементы пути и присваивает ему 0. То есть начинает поиск с нулевой вершины. Просматривает в матрице строку 0, находит значение 1 (есть ребро), проверяет номер столбца “1” и записывает номер столбца в путь, если такого там нет. Записывает неполный путь “01” в список временных путей. Далее поиск ведется в строке “1”, находит 1 на пересечении строки “1” и столбца “0” и проверяет была ли такая вершина в пути, была, пропускает, ищет дальше, находит 1 на пересечении строки “1” и столбца “2”. Проверка, такой вершины не было, записывает в маршрут (он теперь “012”), записывает неполный маршрут в список временных путей, ищет далее в строке “2”. Смотрим: “2” “0” – значение 0 , “2” “1” – значение 1 было, “2” “2” – значение 0, “2” “3” – значение 0. Теперь получается что это последняя j-тая вершина (столбец), а ребер больше нет, программа проверяет готова ли цепь. Так как цепь не готова, записывает частичное решение в список временных путей. Делает шаг назад, запоминает последнюю вершину, затем стирает ее, и начинает поиск с предыдущей, пропуская текущую. Теперь маршрут снова “01”, программа ищет дальше в строке “1”, пропуская столбец “2” и находит 1 в следующем столбце “3”. Проверяет, такой не было, записывает в путь, записывает неполный путь в список путей. Ищет в строке “3”, не находит ничего подходящего, делает шаг назад, и начинает снова поиск со строки “1” столбца “0”. Доходит до столбца “2”, тут проверка показывает, что в списке неполных путей такой путь уже был. Не записывая повтор, делает шаг назад в пути “01”, стирает единицу, запомнив ее, и продолжает поиск в строке “0”, пропустив столбец “1”. Находит 1 в столбце “3” (путь “03”), затем “031”, и наконец завершает гамильтонову цепь, найдя “2”. Цепь готова: “0312”.

5. Описание программы.

Описание программы.

Программа состоит из одного главного окна (рис. 3)

Рис. 3 Главное окно программы.

Как видно из рисунка, программа состоит из трех блоков:

Входная информация. Здесь можно создать новый граф, указав количество вершин и его имя или загрузить готовые графы, которые записаны в папку с программой в текстовые файлы. Тоже входная информация, а также основной цикл поиска гамильтоновой цепи (кнопка “Построить гамильтонову цепь”). Если создается новый граф, то для него вручную вводятся значения наличия или отсутствия (1 или 0 соответственно) ребер между вершинами. Если выбирается готовый, то эти значения подставляются автоматически. Выходная информация. Здесь выводится весь список временных вершин, а также результат: гамильтонова цепь. Также здесь можно сохранить набранный во втором блоке граф в текстовый файл.

Ограничения программы.

Программа предусматривает действительное наличие гамильтоновой цепи в заданном графе. В случае, если цепи в графе не существует, то программа этого определить не сможет и либо произойдет зависание программы из-за того что основной поисковый цикл войдет в бесконечное цикл, либо программа выдаст ошибочный результат. В блоке 2 при ручном вводе значений, допускается ввод только 0 или 1. Другие значения, а также пустая ячейка матрицы смежности приведет либо к ошибке программы, либо к ее зависанию.

6. Тестирование программы.

Первый тест уже подробно продемонстрирован на рис. 1, 2, 3.

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

Рис. 4 Граф с 6-ю вершинами.

Рис. 5 Тест № 1. Расчет гамильтоновой цепи.

Рис. 6 Другой граф с 6-ю вершинами

Рис. 7 Тест № 2

Литература.

В. С. Гапанович, И. В. Гапанович “Дискретная математика”, уч. пособие для студентов ИВТ, ТГНГУ, Тюмень, 2002. http://programmersclub. ru/ http://www. realcoding. net/article/rubric/CCplus

Приложение 1. Листинг программы.

//—————————————————————————

#include <vcl. h>

#pragma hdrstop

#include <fstream. h>

#include “Unit1.h”

//—————————————————————————

#pragma package(smart_init)

#pragma resource “*.dfm”

TFA *FA;

Int v, i, j, y;

AnsiString namegraf;

Int **g = new int *[v]; //массив указателей на строки

//—————————————————————————

__fastcall TFA::TFA(TComponent* Owner)

: TForm(Owner)

{

}

//—————————————————————————

Void __fastcall TFA::BnewgrafClick(TObject *Sender)

{

For (int s=0; s<StringGrid1->RowCount; s++)

{

StringGrid1->Rows[s]->Clear();

}

Memo1->Lines->Clear();

Eput->Clear();

V=StrToInt(Ev->Text);

Namegraf=Enamegraf->Text;

Namegraf=namegraf+”.txt”;

StringGrid1->RowCount=v+1;

StringGrid1->ColCount=v+1;

For (int i=1; i<v+1; i++)

{

StringGrid1->Cells[0][i]=IntToStr(i-1);

StringGrid1->Cells[i][0]=IntToStr(i-1);

}

StringGrid1->Cells[0][0]=””;

}

//—————————————————————————

Void __fastcall TFA::FileListBox1Click(TObject *Sender)

{

For (int s=0; s<StringGrid1->RowCount; s++)

{

StringGrid1->Rows[s]->Clear();

}

Memo1->Lines->Clear();

Eput->Clear();

Ifstream f(FileListBox1->FileName. c_str());

F>>v;

StringGrid1->RowCount=v+1;

StringGrid1->ColCount=v+1;

For (int i=1; i<v+1; i++)

{

StringGrid1->Cells[0][i]=IntToStr(i-1);

StringGrid1->Cells[i][0]=IntToStr(i-1);

}

StringGrid1->Cells[0][0]=””;

//создаем динамический массив для таблицы смежности графа

Int **g = new int *[v]; //массив указателей на строки

For (int i=0; i<v; i++) //выделение памяти под каждую строку

G[i] = new int [v];

//заполняем его из файла

For (int i=0; i<v; i++)

For (int j=0; j<v; j++)

F>>g[i][j];

F. close(); //закрываем файл

//заполняем StringGrid1

For (int i=0; i<v; i++)

For (int j=0; j<v; j++)

StringGrid1->Cells[i+1][j+1] = g[i][j];

//создаем массив маршрута гамильтоновой цепи

Int *p = new int [v];

For (int i=0; i<v; i++) //обнуляеммассивпути

{p[i]=-1;};

}

//—————————————————————————

Void __fastcall TFA::BstartClick(TObject *Sender)

{

//создаем динамический массив для таблицы смежности графа

Int **g = new int *[v]; //массив указателей на строки

For (int i=0; i<v; i++) //выделение памяти под каждую строку

G[i] = new int [v];

//заполняемегоиз SrtingGrid1

For (int i=0; i<v; i++)

For (int j=0; j<v; j++)

G[i][j]=StrToInt(StringGrid1->Cells[i+1][j+1]);

//создаем массив маршрута гамильтоновой цепи

Int *p = new int [v];

For (int i=0; i<v; i++) //обнуляеммассивпути

{p[i]=-1;};

Memo1->Lines->Append(“0”);

//поиск гамильтоновой цепи

AnsiString put;

Int s=0,t=0; //счетчики

Int temp=0;

AnsiString tempput; //временныйпуть

Int y=0;

For (int k=0; k<v; k++) //для K-той вершины пути

{

If (p[0]==-1)

{

P[0]=0; //начнем поиск с первой вершины (нулевая для матрицы)

}

If (p[k]<0) //если К-тая вершина пути пуста, то ищем эту вершину

{

For (i=p[k-1]; i<v; i++) //присвоить i последнюювершинупути

For (j=temp; j<v; j++) //i – строка, j – столбец

Switch (y=g[i][j])

{

Case 1: //если от вершины идет ребро, то

For (int x=0; x<v; x++) //проверяем была ли уже такая вершина

{

If (p[x]==j) //если да

{

S++; //фиксируем это счетчиком

}

}

If (s>0) //если счетчик изменится, значит

{ //такая вершина уже есть в пути

S=0;

Break; //обнуляем счетчик и выходим из цикла

}

If (s==0) //если счетчик не изменился, то

{ //записываем вершину в путь

P[k]=j; //продолжаем поиск с найденной вершины

If (j+1==v) //если это последняя j-тая вершина,

{ //а ребер больше нет, то

If (p[v-1]!=-1) //проверяем готова ли цепь

{ //если последняя вершина пути не пуста

For (int x=0; x<v; x++)

{

Put=put+IntToStr(p[x]);

}

Eput->Text=put;

Return;

}

}

If (p[v-1]<0) //еслицепьнеготова

{ //записать ее в tempput

For (int x=0; x<v; x++)

{ //убрав -1

If (IntToStr(p[x])!=-1)

{

Tempput=tempput+IntToStr(p[x]);

}

}

//сравнить это значение пути с уже имеющимися в memo1

For (int str=0; str<memo1->Lines->Count; str++)

{

If (StrToInt(tempput)==StrToInt(memo1->Lines->Strings[str]))

{ //если найдено совпадение

T++; //фиксируем это счетчиком

}

}

If (t==0) //если счетчик не изменится

{

Memo1->Lines->Append(tempput); //записатьнеполныйпутьв memo1

Temp=0;

}

Else if (t>0) //если счетчик изменится, т. е. совпадение есть

{

T=0;

Temp=p[k-1]; //вернуться на предыдущую вершину

If (temp<v-1)

{

Temp++;

}

Else if (temp==v-1) //контроль temp чтобы не вышел за границы

{ //возможного кол-ва вершин

Temp=0;

}

If (temp>v-1)

{

Temp=0;

P[0]=0;

}

For (int x=0; x<v; x++) //стираем все вершины до той,

{ //с которой нужно вести поиск

If (x>=k-1)

{

P[x]=-1;

}

}

K=k-2;

}

Tempput=””;

J=v-1;

I=v-1;

}

}

Break;

Case 0: //если идет не ребро

If (j+1==v) //если это последняя j-тая вершина,

{ //а ребер больше нет, то

If (p[v-1]!=-1) //проверяем готова ли цепь

{ //если последняя вершина пути не пуста

For (int x=0; x<v; x++)

{

Put=put+IntToStr(p[x]);

}

Eput->Text=put;

Return;

}

If (p[v-1]<0) //еслицепьнеготова

{ //записать ее в tempput

For (int x=0; x<v; x++)

{ //убрав -1

If (IntToStr(p[x])!=-1)

{

Tempput=tempput+IntToStr(p[x]);

}

}

//сравнить это значение пути с уже имеющимися в memo1

For (int str=0; str<memo1->Lines->Count; str++)

{

If (StrToInt(tempput)==StrToInt(memo1->Lines->Strings[str]))

{ //если найдено совпадение

T++; //фиксируем это счетчиком

}

}

If (t==0) //если счетчик не изменится

{

Memo1->Lines->Append(tempput); //записать неполный путь в memo1

}

Else if (t>0) //если счетчик изменится, т. е. совпадение есть

{

T=0;

}

Temp=p[k-1]; //вернуться на предыдущую вершину

If (temp<v-1)

{

Temp++;

P[k-1]=-1;

}

Else if (temp==v-1) //контроль temp чтобы не вышел за границы

{ //возможного кол-ва вершин

Temp=0;

For (int x=0; x<v; x++) //стираем все вершины до той,

{ //с которой нужно вести поиск

If (x>=k-1)

{

P[x]=-1;

}

}

}

If (temp>v-1)

{

Temp=0;

P[0]=0;

}

K=k-2;

Tempput=””;

J=v-1;

I=v-1;

}

}

Break;

}

}

}

;

}

//—————————————————————————

Void __fastcall TFA::BsavegrafClick(TObject *Sender)

{

//создаем динамический массив для таблицы смежности графа

Int **g = new int *[v]; //массив указателей на строки

For (int i=0; i<v; i++) //выделение памяти под каждую строку

G[i] = new int [v];

//заполняемегоиз StringGrid1

For (int i=0; i<v; i++)

For (int j=0; j<v; j++)

G[i][j]=StrToInt(StringGrid1->Cells[i+1][j+1]);

Ofstream f(namegraf. c_str());

F<<v<<endl;

//заполняем файл графом g

For (int i=0; i<v; i++)

For (int j=0; j<v; j++)

F<<g[i][j]<<” “;

F. close(); //закрываем файл

FileListBox1->Update();

}

//—————————————————————————

Void __fastcall TFA::BdelgrafClick(TObject *Sender)

{

DeleteFileA(FileListBox1->FileName);

FileListBox1->Update();

}

//—————————————————————————

Void __fastcall TFA::N3Click(TObject *Sender)

{

ShowMessage(“Курсовая работа по дискретной математике. Выполнил студент гр. АСОиУзс-07-01 Быстров Евгений, вариант №13”);

}

//—————————————————————————


Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов