4575

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

Курсовая

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

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

Русский

2012-11-22

403.33 KB

81 чел.

Введение 

Родоначальником теории графов считается Леонард Эйлер. В 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 – Сообщение о ошибке заполнения



 

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

37434. Разработка замкнутой (бессбросной) системы производственного водообеспечения техногенного комплекса 1.13 MB
  Результатом выполнения курсового проекта является составление замкнутой схемы производственного водообеспечения техногенного комплекса. В этой схеме исключён сброс сточных вод в водный объект и значительно уменьшен расход воды, забираемой из источника водоснабжения.
37435. Організація обліку готової сільськогосподарської продукції 239.83 KB
  Визначити, класифікувати та описати порядок оцінки готової сільськогосподарської продукції; визначити основні завдання організації обліку готової сільськогосподарської продукції; визначити нормативно-правове регулювання обліку готової сільськогосподарської продукцції; визначити особливості документування господарсьих операцій повʼязаних з випуском готової сілльськогосподарської продукції...
37436. Управління пасажирським судном 233.5 KB
  Старший бортпровідник безпосередньо підкоряється помічникові капітана по пасажирській частині, керує роботою бортпровідників, днювальних, що обслуговують пасажирські приміщення, і забезпечує стан пасажирських приміщень у належному порядку.
37437. История России. Шпаргалка 228.68 KB
  Империя – это конгломерат народов, которые образуют экономическую, политическую и в зачатке культурную систему, где ведущая определяющая, объединяющая роль принадлежит одному или нескольким народам, в то время как остальные народы находятся в состоянии зависимости и подчинения, хотя и извлекают определенные выгоды из своего положения в рамках данного конгломерата.
37438. Икемділік ұғымы. Сұраныс пен ұсыныс икемділігі 154 KB
  Рыноктық экономика – бұл сұраныс пен ұсыныстың үздіксіз арақатынасы. Мұндай қарым-қатынасты қарапайым моделінің тууы, экономикалық ғылым тарихында үлкен маңызды дәуір болып саналады. Сол мезеттен бері екі ғасырдан астам уақыт өтсе де, рыноктық экономикамен теориялық танысу осыдан басталады. Өйткені осы модель арқылы барлық экономикалық процестер ашылып көрсетіледі.
37439. Финансовый мененджмент 212.87 KB
  Финансовый менеджмент– это управление финансово-хозяйственной деятельностью фирмы на основе использования современных методов. Основным лицом ответственным за достижение цели финансового менеджмента, является вице-президент по финансовым вопросам (заместитель директора по финансовым вопросам).
37440. Обеспечение единства измерений в стране. Государственный метрологический надзор. Цели надзора, сфера распространения. Виды метрологического надзора 19.86 KB
  Проверки проводят должностные лица Госстандарта России - главные государственные инспекторы и государственные инспекторы по обеспечению единства измерений, действующие на соответствующих территориях и аттестованные в установленном порядке.
37441. Виды и средства измерений. Виды эталонов. Стандартные образцы 19.55 KB
  Прямые измерения — это непосредственное сравнение физической величины с ее единицей. Например, при определении длины предмета с помощью линейки происходит сравнение искомой величины (количественного выражения значения длины) с мерой, т. е. единицей измерения.
37442. Факторы, сохраняющие качество товаров 16.91 KB
  Режим хранения - это совокупность условий, при которых товар сохраняет свое качество. Для каждого товара необходим определенный режим хранения, зависящий от его состава и свойств. При правильном режиме не только сохраняется качество, но и снижаются потери товаров.