4575

Раскраска графа способом разработки программного продукта

Курсовая

Информатика, кибернетика и программирование

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

Русский

2012-11-22

403.33 KB

82 чел.

Введение 

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Впервые о хроматических многочленах было упомянуто в книге  Бирхофа, Г. Д. и Левиса, Д. С. «Chromatic Polynomials» 1946 года.

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

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

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

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

2 Технические характеристики

2.1 Постановка задачи

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

2.2 Описание функционирования программы

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

Режим внесения данных предполагает процесс ввода данных пользователем. В данном режиме происходит занесение введенных данных в память компьютера.

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

2.3 Обоснование выбора входных и выходных данных

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

- неориентированный граф;

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

5 Описание алгоритмов, используемых при разработке программного средства

5.1 Концепция раскраски графов

Раскраска графа – это очень хорошо изученная задача. Известно, что это NP-полная задача для произвольных графов, так что (предполагая, что P != NP) можно не стремится находить эффективный алгоритм для раскрашивания произвольного графа. Для любого графа предполагается, что каждый узел может иметь любой цвет, однако должен отличаться от соседнего, затем идет назначение каждому узлу цвета и проверка правильности решения если решение не найдено, то происходит возврат в начальное положение системы и следующая попытка. Это, по сути, алгоритм перебора с возвратами (“backtracking” algorithm). Если ни одно предположение не оправдывается, тогда либо задача не решаема или предыдущее предположение неверно, так что нужно возвращаться на один шаг ранее. Алгоритм продолжает выполнение до тех, пока не перепробует все возможные варианты.

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

5.2 Обобщённый алгоритм

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

  1. Если имеется один возможный цвет для каждого узла графа, то работа алгоритма успешно завершена!
  2. Если есть хотя бы один узел, которому не подходит ни один цвет, то работа алгоритма завершилась неудачно!
  3. В противном случае,  должен быть узел, как минимум с двумя возможными цветами.
  4. У некоторых узлов может быть только один возможный цвет, тогда этот цвет нужно удалить из списка возможных цветов его соседних узлов.
  5. Эта операция может привести к тому, что у соседей может остаться только один единственный цвет. Если это так, то нужно удалить эти цвета из возможных цветов соседних узлов.
  6. И так далее; нужно продолжать уменьшать количество возможных вариантов до тех, пока это будет возможно.
  7. Если количество возможных цветов уменьшено, то либо получено решение, либо его вообще нет. Возврат к шагу 1.
  8. В противном случае количество возможных вариантов не уменьшено и есть узел с двумя или более возможными цветами. Выберем один возможный цвет для этого узла.
  9. Применяем рекурсию; если следующая итерация рекурсии приводит к успеху, то решение найдено. Если следующая итерация приводит к неудаче, тогда гипотетическое предположение не сработало.
  10. Если есть еще неопробованный гипотетический цвет для этого узла, возврат к шагу 8 и выбирается другой цвет.
  11. В противном случае ни один из вариантов для этого «неопределенного» узла не подходит; алгоритм завершился неудачно.

5.3 Этапы решения задачи при помощи раскраски графов

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

1. Представить  задачу  в  виде  набора узлов неориентированного графа

2. Определить значения известных узлов

3. Определить соседние узлы или подгруппу узлов

4. Определить алгоритм раскраски, когда строим решение

5.4 Применение раскраски графов для задачи судоку

Задача формулируется так, игровое поле представляет собой квадрат размером 9x9, разделённый на меньшие квадраты со стороной в 3 клетки. Таким образом, всё игровое поле состоит из 81 клетки. В них уже в начале игры стоят некоторые числа (от 1 до 9. В зависимости от того, сколько клеток уже заполнены, конкретную судоку можно отнести к лёгким или сложным. В судоку есть всего одно правило. Необходимо заполнить свободные клетки цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3x3 каждая цифра встречалась бы только один раз.

От того, сколько клеток уже заполнено, зависит сложность. Правильно составленная головоломка имеет только одно решение. Моделирование раскраски графов связано с раскраской 81 вершины 9 разными цветами(номерами) или 27 подмножеств.

Раскраска графа для задачи судоку в псевдокоде:

  1.  Ввод матрицы вершин
  2.  Сохранение начального варианта
  3.  Проверка решаемости матрицы
  4.  Цикл пока не будет найдено решение
  5.  Цикл по одному варианту раскраски пока не будут раскрашены все вершины
  6.      Раскрасить все вершины в возможные варианты
  7.  Конец цикла по вариантам
  8.    Если решение не достигнуто вернуться на пункт 5
  9.    В случае если решение найдено перейти на пункт 10
  10.  Конец цикла
  11.  Возврат результата

Заключение

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

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


Приложение В

Блок-схема обобщённой алгоритм раскраски графа

Нет

Конец

Решение найдено?

Да

Дополнительные действия

Выбор случайных значений

Поиск решений

Начальное положение

Начало

Рисунок В.1 - Обобщенный алгоритм раскраски графа


Приложение Г

(обязательное)

Руководство пользователя

Г.1 Введение

Г.1.1 Область применения

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

Г.1.2 Краткое описание возможностей

Программа позволяет решить судоку, используя алгоритм раскраски графа. Параметры алгоритма задаются пользователем. Реализована возможность визуализации игрового поля.

Г.1.3 Уровень подготовки пользователя

Пользоваться системой должен человек с уровнем знания ПК на уровне «Пользователь», умеющий работать с Windows-приложениями.

Г.1.4 Перечень эксплуатационной документации

В перечень эксплуатационной документации, с которой необходимо ознакомиться, входят «Руководство пользователя», «Руководство программиста».

Г.2 Назначение и условия применения

Г.2.1 Виды деятельности, функции

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

Г.2.2 Программные и аппаратные требования к системе

Для использования программного продукта необходим компьютер, на котором установлена операционная система MS Windows XP / Vista / 7.

Достаточная комплектация:

  1. процессор Intel Pentium IV;
  2. объем ОЗУ 128 МБайт;
  3. объем дискового пространства 30 Mb для исполняемого файла;
  4. монитор;
  5. устройства ввода информации и управления (мышь, клавиатура);
  6.  CD-ROM или USB-разъем.

Г.3 Подготовка к работе

Г.3.1 Комплект установки

Для установки достаточно иметь папку с запускаемым файлом, которая прилагается на диске

Г.3.2 Запуск системы

Для работы с программой необходимо переместить директорию программы с CD-диска с программой на жесткий диск компьютера. Для запуска приложения «SudkouSolver» откройте папку, в которую была скопирована программа, и запустите файл «SS.exe».

Г.3.3 Проверка работоспособности системы 

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

Рисунок Г.1 – Окно приложения «SudkouSolver»

Г.4 Описание операций

Г.4.1 Наименование операций

Раскраска графа.

Г.4.2 Условия выполнения операции

Приложение запущено, успешно функционирует, введены все данные для выполнения операции.

Г.4.3 Подготовительные действия

Ввод данных, заполнение начального состояния игрового поля.

Г.4.4 Основные действия

Необходимо заполнить игровое поле, если оно не было загружено из файла. Для решения задачи нужно нажать на кнопку «Результат» (рисунок Г.2).

Рисунок Г.2 – «Результат»

Г.4.5 Заключительные действия

Нажать на кнопку «Сброс» (рисунок Г.3).

Рисунок Г.3 – «Сброс»

Г.4.6 Ресурсы, расходуемые на операцию

Отсутствуют.

Г.5 Аварийные операции, восстановление 

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

При сбое в работе аппаратуры восстановление нормальной работы программы должно наступить после перезагрузки операционной системы и запуска исполняемого файла «SS.exe»

Г.6 Рекомендации по освоению

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

Ниже рассмотрен пример работы с программой, начиная с ее запуска и заканчивая завершением ее работы. Решим судоку:

  1. Запустите программу (откройте исполняемый файл «SS.exe»). После запуска появляется главное окно приложения (рисунок Г.4).

Рисунок Г.4 – Запуск программы


  1. Задайте необходимые значения как показано на рисунке Г.5

Рисунок Г.5 – Создание вершин графа

  1. Нажмите на кнопку «Результат».
  2. При решение выводиться окно в котором нам сообщается сколько было затрачено шагов и времени на решение. (рисунок Г.6).

Рисунок Г.6 – Информационное окно

В итоге можно наблюдать результат (рисунок Г.7)

Рисунок Г.7 – Результат

 

          Приложение Д

(обязательное)

Руководство программиста

Д.1 Назначение и условия применения программы

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

Для использования программного продукта необходим компьютер, на котором установлена операционная система MS Windows XP / Vista / 7.

Достаточная комплектация:

  1. процессор Intel Pentium IV;
  2. объем ОЗУ 128 МБайт;
  3. объем дискового пространства 30 Mb для исполняемого файла;
  4. монитор;
  5. устройства ввода информации и управления (мышь, клавиатура);
  6.  CD-ROM или USB-разъем.

Д.2 Характеристика программы

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

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

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

Д.3 Обращение к программе

Основные модули и компоненты программы представлены в таблице Д.1.

Таблица Д.1 – Основные модули программы

Имя модуля

Назначение

Основные процедуры и функции

lib.php

Основная библиотека функции.

  1.  Function solve($sudoku);

Функция решения судоку.

  1.  Function is_valid($sudoku);

Проверка валидности введённого задания.

  1.  Function is_solved_sudoku($sudoku);

Проверка решена ли система

  1.  Function print_sudoku($sudoku);

Вывод решения в пользовательский интерфейс

  1.  Function scan_sudoku_for_unique($sudoku);

Поиск возможных значений для всех вершин.

  1.  Function determine_possible_values($x, $sudoku);

Определение возможных значений для конкретной вершины.

  1.  Function next_random();

Выбор вершины которая будет окрашена(нумерована)


Таблица Д.1 (продолжение)

Имя модуля

Назначение

Основные процедуры и функции

.

  1.  Function determine_random_possible_value($next_move, $what_to_try);

Случайное число из ряда возможных

  1.  Function remove_attempt($attempt_array, $number);

Удаление из возможных использованных цветов

Form1.dfm

Модуль окна загрузки программы.

  1.  Form1 :: event onCreate($self);

Начальное заполнение полей нюлями


Д.4 Входные и выходные данные

Входные данные:

  1. Неориентированный граф с количеством вершин 81. Представлен в виде массива типа integer;

Выходные данные:

  1. массив, содержащий вершины (тип integer);

Д.5 Сообщения

При попытке создания запуска алгоритма на выполнение с некорректным заполненными полями, пользователю выдаётся сообщение о ошибке заполнения:

Рисунок Д.5.1 – Сообщение о ошибке заполнения



 

А также другие работы, которые могут Вас заинтересовать

30541. Единые критерии (ГОСТ Р ИСО 15408). Профиль защиты. Задание по безопасности 29.73 KB
  Задание по безопасности.Положение по разработке профилей защиты и заданий по безопасности Гостехкомиссия России 2003 год Выступление: Профиль защиты это нормативный документ предназначенный для изложения проблемы безопасности определенной совокупности продуктов и систем ИТ и формулирования требований безопасности для решении данной проблемы. ПЗ не регламентирует каким образом данные требования будут выполнены обеспечивая таким образом независимое от реализации описание требований безопасности. Профиль защиты разрабатывается для...
30542. Криптографические протоколы – основные виды и типы, область применения. Идентификация и аутентификация 43.95 KB
  Под протоколом понимается распределенный алгоритм с двумя и более участниками. Протокол является криптографическим если он решает по крайней мере одну из трех задач криптографии обеспечение конфиденциальности целостности неотслеживаемости. Компонентами к протокола являются участники протокола каналы связи между участниками а также либо алгоритмы используемые участниками либо постановка той задачи которую протокол призван решать.
30543. Идентификация и аутентификация. Криптографические протоколы – основные виды и типы, область применения 19.83 KB
  Криптографические протоколы основные виды и типы область применения. Ответ: Все эти типы можно условно разделить на две группы: прикладные протоколы и примитивные. Примитивные же протоколы используются как своеобразные строительные блоки при разработке прикладных протоколов. Мы в данном учебном пособии будем рассматривать только примитивные криптографические протоколы которые при некоторой адаптации к реальным системам связи могут использоваться на практике.
30546. Блочные шифры. Ключевая система блочных шифров. Российский стандарт на блочный шифр ГОСТ 28147-89 492.5 KB
  Представляют собой семейство обратимых преобразований блоков частей фиксированной длины исходного текста. Если для шифрования исходного текста используется подсистема π из Π ∈ SYM то получающуюся в результате систему подстановок Π называют системой блочных шифров или системой блочных подстановок. Если информация исходного текста не может быть представлена Nразрядными блоками как в случае стандартного алфавитноцифрового текста то первое что нужно сделать это перекодировать исходный текст именно в этот формат причем с...
30547. Схема ЭЦП построенная на симметричной криптосистеме, схема ЭЦП построенная на асимметричной криптосистеме. Доверие к открытому ключу и цифровые сертификаты (основные определения, стандарт X.509, сравнение версий сертификатов стандарта X.509, классы сертиф 67.22 KB
  Доверие к открытому ключу и цифровые сертификаты основные определения стандарт X. Доверие к открытому ключу и цифровые сертификатыЦентральным вопросом схемы открытого распределения ключей является вопрос доверия к полученному открытому ключу партнера который в процессе передачи или хранения может быть модифицирован или подменен.В системах где отсутствует возможность предварительного личного контакта партнеров необходимо использовать цифровые сертификаты выданные и заверенные ЭЦП доверенного посредника удостоверяющего или...
30548. Криптографической системы с открытым ключом 25.48 KB
  Основные компоненты PKI Удостоверяющий центр Сертификат открытого ключа Регистрационный центр Репозиторий Архив сертификатов Конечные пользователи Основные задачи Основные задачи системы информационной безопасности которые решает инфраструктура управления открытыми ключами: обеспечение конфиденциальности информации; обеспечение целостности информации; обеспечение аутентификации пользователей и ресурсов к которым обращаются пользователи; обеспечение возможности подтверждения совершенных пользователями действий с...
30549. Сетевая модель доверительных отношений 189.15 KB
  Вышестоящий центр может передать подчиненному C часть своих функций по выпуску сертификатов. Оконечный центр C предназначен для выдачи сертификатов пользователям PKI в то время как промежуточный C рекомендуется использовать только для выдачи сертификатов подчиненным ему центрам C. В модели P2P существует два метода установления доверительных отношений: с помощью списков сертификатов заслуживающих доверия Сertificte Trust List CTL и кросссертификатов.inf можно устанавливать параметры регулируемых доверительных отношений для сертификатов C...