Пояснительная записка к курсовой работе по дисциплине «Основы Кибернетики» icon

Пояснительная записка к курсовой работе по дисциплине «Основы Кибернетики»






Скачать 109.6 Kb.
НазваниеПояснительная записка к курсовой работе по дисциплине «Основы Кибернетики»
В.С. Ирицян
Дата конвертации06.08.2013
Размер109.6 Kb.
ТипПояснительная записка
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Факультет Информационной Безопасности


Пояснительная записка к курсовой работе по дисциплине
«Основы Кибернетики»:
«Программа построения гамильтонова цикла в графе, используя алгоритм с возвратом»


Выполнил: ______________ В.С. Ирицян
(подпись) ст. группы И-11


Проверил: ______________ В.М. Федоров
(подпись) преп. каф. БИТ

Содержание


Введение ...…….……………………………………………..…......... 3

  1. Теоретическая часть...…………………………………………….….……… 4

  2. Описание алгоритма работы. Блок-схема………..………………….…….. 8

  3. Примеры решения задач…...………………………………………............. 10

Список используемой литературы.……………………………………..….. 14


Введение

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

Название «гамильтонов цикл» произошло от задачи «Кругосветное путешествие» предложенной ирландским математиком Вильямом Гамильтоном в 1859 году. Нужно было, выйдя из исходной вершины графа, обойти все его вершины и вернуться в исходную точку. Граф представлял собой укладку додекаэдра, каждой из 20 вершин графа было приписано название крупного города мира.


1.Теоритическая часть

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

Любой граф G можно превратить в гамильтонов граф, добавив достаточное количество вершин. Для этого, например, достаточно к вершинам v1,…,vp графа G добавить вершины u1,…,up и множество ребер {(vi,ui)} {(ui,vi+1)}. Степенью вершины v называется число ребер d(v), инцидентных ей, при этом петля учитывается дважды. В случае ориентированного графа различают степень do(v) по выходящим дугам и di(v)- по входящим.

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

https://sites.google.com/a/labore.ru/teoria-grafov-i-ee-primenenie/_/rsrc/1297439752169/vvedenie-v-teoriu/gamiltonov-cikl-i-gamiltonov-graf/5_2.gif

Простой (гамильтонов) цикл выделен сплошной линией (1, 2), (2, 3), (3, 4), (4, 5), (5, 1). Заметим, что если граф имеет один гамильтонов цикл, то он может иметь и другие гамильтоновы циклы.

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

https://sites.google.com/a/labore.ru/teoria-grafov-i-ee-primenenie/_/rsrc/1297439854184/vvedenie-v-teoriu/gamiltonov-cikl-i-gamiltonov-graf/5_3.gif

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

https://sites.google.com/a/labore.ru/teoria-grafov-i-ee-primenenie/_/rsrc/1297607766108/vvedenie-v-teoriu/gamiltonov-cikl-i-gamiltonov-graf/5_4.gif

Теорема (Дирак, 1952) 1. Если в простом графе с n > 3 вершинами p(v) > n/2 для любой вершины v, то граф G является гамильтоновым. 

Замечание. Существует несколько доказательств этой широко известной теоремы, здесь мы приводим доказательство Д. Дж. Ньюмана.

Доказательство. Добавим к нашему графу k новых вершин, соединяя каждую из них с каждой вершиной из G. Будем предполагать, что k -- наименьшее число вершин, необходимых для того, чтобы полученный граф G стал гамильтоновым. Затем, считая, что k > 0, придем к противоречию.

Пусть v>p>w>…>v гамильтонов цикл в графе G, где v, w-- вершины из G, а p-- одна из новых вершин. Тогда w не является смежной с v, так как в противном случае мы могли бы не использовать вершину p, что противоречит минимальности k. Более того, вершина, скажем, w, смежная вершине w, не может непосредственно следовать за вершиной v, смежной вершине v, потому что тогда мы могли бы заменить v>p>w>…>v> w>v на v>v>…>w>w>…>v, перевернув часть цикла, заключенную между w и v. Отсюда следует, что число вершин графа G, не являющихся смежными с w, не меньше числа вершин, смежных с v (то есть равно, по меньшей мере, n/2 + k); с другой стороны, очевидно, что число вершин графа G, смежных с w, тоже равно, по меньшей мере, n/2 + k. А так как ни одна вершина графа G не может быть одновременно смежной и не смежной вершине w, то общее число вершин графа G, равное n + k, не меньше, чем n + 2k. Это и есть искомое противоречие.


Теорема (Оре) 2. Если число вершин графа G(V, E) n > 3 и для любых двух несмежных вершин u и v выполняется неравенство: d(u)+d(v)>n и (u,v)E, то граф G - гамильтонов. Граф G имеет гамильтонов цикл если выполняется одно из следующих условий:

1. Условие Бонди: из d(vi)>i и d(vk)>k=>d(vi)+d(vk)>n(ki)

2. Условие Хватала: из d(vk)>k>n/2=>d(vn-k)>nk.

Далее, известно, что почти все графы гамильтоновы, то есть где H(p) - множество гамильтоновых графов с p вершинами, а G(p) -- множество всех графов с p вершинами. Задача отыскания гамильтонова цикла или эквивалентная задача коммивояжера являются практически востребованными, но для нее неизвестен (и, скорее всего не существует) эффективный алгоритм решения.

Есть такие задачи, для решения которых приходится организовывать полный перебор возможных вариантов. Перебор с возвратом (backtracking) –это общий метод упорядоченного перебора. Перебор с возвратом особенно удобен для решения задач, требующих проверки потенциально большого, но конечного числа решений. В самом общем случае мы полагаем, что решение можно записать как вектор (массив переменной длины) B = (b1,b2,…,bn), удовлетворяющий заданным условиям и ограничениям, или как множество таких векторов. При этом в одних задачах размерность решения (число n) может быть известна заранее, а в других заранее не определена.

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

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

  • Находятся недопустимые значения переменных и проверяется, не стали ли некоторые ограничения противоречивыми. Если такие ограничения есть, то текущая подзадача решений не имеет

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

  • Выполняется цикл, в котором

    1. Перебираются допустимые значения текущей переменной

    2. Для каждого значения переменной производится вызов процедуры решения задачи

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




2. Описание алгоритма работы. Блок-схема


1) Введем 3 массива: для учёта посещенных вершин, для сохранения текущего пути, и для запоминания индекса вершины, на которой произошёл переход на очередную ветку маршрута.


2) Флаги посещения устанавливаем в false. Индексы в массиве переходов устанавливаем в -1. Некоторую вершину выбираем текущей.


3) Для каждой смежной с текущей вершины (не учитывая предыдущие пути), если мы ее не посещали, сохраняем ее индекс в массиве переходов («на чём остановились»), текущей делаем найденную вершину и запоминаем ее в массиве пути.


4) Если вершин, смежных с текущей вершиной, на которых мы ещё не были, нет, то в массиве «на чём остановились» для текущей вершины записываем -1, помечаем данную вершину как непосещенную, делаем «откат» на 1 вершину в пути назад, соответственно текущей становится предыдущая вершина.


5) Работа функции прекращается с результатом true, если заполнен массив пути и если существует путь между последней найденной вершиной и первой. Если путь не найден и «откат» невозможен, то возвращаем false.


6) Переходим к шагу 2.

  1. 3. Пример решения задачи


Задача 1

Ручной счет



Рис.1


Тест программы



Рис.2


Задача 2

Ручной счет



Рис.3

Гамильтоновы циклы: 1,2,3,4,0,1; 1,3,2,0,4,1; 1,2,0,4,3,1; 1,0,2,3,4,1; 1,4,3,2,0,1; 1,4,0,2,3,1; 1,3,4,0,2,1;


Тест программы



Рис.4


Задача 3



Рис.5

Гамильтоновы циклы: 1,2,3,4,0,1; 1,0,4,3,2,1;


Тест программы



Рис.6


Заключение


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

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

В работе использовались биполярные транзисторы типа n-p-n ГТ122Б, резисторы ряда E24. Параметры всех элементов были указаны в ходе проведения расчётов, а также ниже, в разделе «Приложения».

Список используемой литературы


1. Дж. Макконнелл. Основы современных алгоритмов. 2-е дополнительное издание.

2. Ж. Трамбле, П. Соренсон – Введение в структуры данных. 1982г.

3. В.А. Евстигнеев, В.Н. Касьянов – Графы в программировании: обработка, визуализация и применение.

4. В.Л. Бурковский, Л.В. Холопкина, Н.Л. Райхель, О.Я. Кравец – Методы моделирования и анализа вычислительных систем. Учебное пособие. 1996г.

5. В. Липский – Комбинаторика для программистов. 1988г.

6. Ф. Харари – Теория графов. 1973г.

Приложения


Приложение 1.

Код программы:

#include "stdafx.h"

#include

#define n 10

bool boo[n];

int way[n], r[n];

int a[n][n]=

{

0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0,

0,0,0,0,0,0,0,0,0,0

};

bool gamilton(int start)

{

int cur = start; int next = 0; way[next++] = cur; bool found;

while (true)

{

found = false;

boo[cur] = true;

for (int i = r[cur] + 1; i < n; i++)

if (i != cur && (a[i][cur] || a[cur][i]) && !boo[i])

{

found = true;

r[cur] = i;

way[next++] = cur = i;

break;

}

if (!found)

{

if (next == 1) return false;

r[cur] = -1;

boo[cur] = false;

cur = way[--next - 1];

}

else

if (next == n && (a[cur][start] || a[start][cur])) return true;

}

}


int _tmain(int argc, _TCHAR* argv[])

{

int i;

printf("Solution:\n");

for (i = 0; i < n; i++) { boo[i] = false; r[i] = -1; }

if (gamilton(1))

{

for (i = 0; i < n; i++) printf("%d ", way[i]);

printf("%d\n", way[0]);

}

else

printf("Solution Not Found!\n");

getchar();

}



Таганрог, 2013 г.

Ваша оценка этого документа будет первой.
Ваша оценка:

Похожие:

Пояснительная записка к курсовой работе по дисциплине «Основы Кибернетики» iconПояснительная записка к курсовой работе по дисциплине “Основы аналитической теории анализа и синтеза сау “ Формирующие фильтры и конечные автоматы (синтез и анализ)
457.5kb.  
Пояснительная записка к курсовой работе по дисциплине «Основы Кибернетики» iconПояснительная записка (релиз).docx
510.8kb.   Пояснительная записка к курсовой работе по дисциплине «теория электрической связи»
Пояснительная записка к курсовой работе по дисциплине «Основы Кибернетики» iconПояснительная записка к курсовой работе по курсу “ Основы расчета теплообменных процессов и устройств ”
312.8kb.  
Пояснительная записка к курсовой работе по дисциплине «Основы Кибернетики» iconПояснительная записка к курсовой работе по дисциплине Организация ЭВМ
209.1kb.  
Пояснительная записка к курсовой работе по дисциплине «Основы Кибернетики» iconПояснительная записка к курсовой работе По дисциплине «Методы оптимизации»
146.5kb.  
Пояснительная записка к курсовой работе по дисциплине «Основы Кибернетики» iconПояснительная записка к Курсовой работе по дисциплине «Функциональное и логическое программирование»
98.1kb.  
Пояснительная записка к курсовой работе по дисциплине «Основы Кибернетики» iconПояснительная записка к курсовой работе по дисциплине Теория вычислительных процессов
20.5kb.  
Пояснительная записка к курсовой работе по дисциплине «Основы Кибернетики» iconПояснительная записка к курсовой работе по дисциплине «Объектно-ориентированное программирование»
236.6kb.  
Пояснительная записка к курсовой работе по дисциплине «Основы Кибернетики» iconПояснительная записка к курсовой работе По дисциплине «Конструкторское и технологическое обеспечение производства эвм»
461.2kb.   Тема курсовой работы: «Разработка конструкторской документации на сигнализацию пантера»
Пояснительная записка к курсовой работе по дисциплине «Основы Кибернетики» iconПояснительная записка к курсовой работе по дисциплине «Теория вероятностей и математическая статистика»
197.3kb.  
Разместите кнопку на своём сайте:
Рефераты


База данных защищена авторским правом ©CoolReferat 2000-2018
обратиться к администрации | правообладателям | пользователям
Основная база рефератов
Рефераты