4575

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

Курсовая

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

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

Русский

2012-11-22

403.33 KB

73 чел.

Введение 

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



 

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

54174. Система дидактичних умов пізнавальної діяльності учнів на уроках математики 119.5 KB
  Система дидактичних розумів розвитку пізнавальної діяльності учнів на уроках математики. Розвиток пізнавального інтересу учнів. Прийоми активізації пізнавальної діяльності учнів на уроках математики. Інтерактивні технології навчання – спосіб створення умов залучення учнів до пізнавальної діяльності.
54175. Первісна. Інтеграл. Застосування інтегралу при розвязуванні задач економічного змісту 690.5 KB
  Група студентів ділиться на чотири команди. На першому етапі заняття проводиться узагальнення та систематизація знань учнів з теми, розглядаються учнівські презентації про виникнення інтегралу та його використання. На другому етапі – пояснення нового матеріалу, потім його закріплення в вигляді створення проектів кожною підгрупою.
54176. Развитие культуры в условиях нижнего и среднего палеолита 33 KB
  Одним из важнейших способов выживания человека в первобытную эпоху стал беспрерывный процесс познания окружающего мира. На раннем этапе жизни человека предметом познания и осмысления является природа, от которой напрямую зависит жизнь человеческого общества.
54177. Новые информационные технологии в профильном обучении математики на примере темы „Многогранники” в 11 классе 827.5 KB
  Рассмотрение различных случаев взаимного расположения диагоналей ребер и граней многогранника использование для этого моделей и готовых чертежей способствует развитию пространственных представлений учащихся их интуиции Рис. Особо подчеркиваются характеристические свойства призмы.
54178. Видатні вчені на уроках математики 165 KB
  Задача 2 Вирішивши поділити всі свої заощадження між усіма синами хтось склав такий заповіт: Старший з моїх синів повинен отримати 1000 франків і 1 8 частину остачі; наступний 2000 франків і 1 8 нової остачі; третій син – 3000 франків і 1 8 частини третьої остачі і т. Так як усі сини отримали порівну то 1 8 частина кожної нової остачі була на 1000 франків менше 1 8 частини попередньої остачі тобто уся нова остача була на 8000 франків менше попередньої. Так як за умовою усі гроші були розділені повністю то коли молодший син отримав по...
54179. Видатні вчені на уроках математики: Евклід, Б.В.Гнеденко, Карл Фрідріх Гаусс 110 KB
  Евклід (бл.365 – бл.300 до н. е.) – старогрецький математик визнаний основоположник математики. Родом з Афін, учень Платона. Автор найдавніших трактатів з математики. Основна праця «Начала» (латинізована назва «Елементи») включає в себе 15 книжок, у яких міститься систематизований вклад геометрії, а також деяких питань теорії чисел.
54180. Метод розмірностей 342 KB
  Однак виявляється що метод розмірностей може бути використаний не тільки і не скільки для перевірки правильності розв’язку поставленої задачі але й для виведення з точністю до константи невідомих співвідношень між фізичними величинами. 1 Основним фундаментальним підходом методу розмірностей є те що будьяку таку функцію ми можемо представити у вигляді наступного виразу y = C x1α x2β x3γ xnω 2 де C – безрозмірна константа;...
54181. Як вчити школярів V-V1 класів розв’язувати задачі 101.5 KB
  Звичайно мова йде не про вправи тренувального характеру а про нестандартні завдання пошук рішення яких складає важливий компонент доступної дітям математичної творчості. Перш за все слід врахувати що навчитися вирішувати завдання школярі зможуть лише вирішуючи їх. Якщо ви хочете навчитися плавати то сміливо входите в воду а якщо хочете навчитися вирішувати завдання то вирішуйте їх пише Д. Рішення будьякого досить складного завдання вимагає від учня напруженої праці волі й наполегливості які найбільш сильно проявляються тоді...
54182. Становление элементов культуры в эпоху верхнего палеолита 37 KB
  Координаты вектора Чтобы найти координаты вектора нужно из координат конца вычесть соответственные координаты начала. Абсолютная величина вектора модуль вектора длина вектора Длина вектора равна корню квадратному из суммы квадратов его координат. Равные вектора Векторы равны если равны их соответственные координаты и наоборот. б Условие коллинеарности векторов Если два вектора коллинеарны то их соответственные координаты пропорциональны и наоборот.