4575

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

Курсовая

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

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

Русский

2012-11-22

403.33 KB

79 чел.

Введение 

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



 

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

50517. Реализация диалогового интерфейса в СУБД FoxPro. Язык запросов SQL 212 KB
  Форму можно создать с помощью мастера формы Form Wizrd Мастер формы. Создать структуру файла БД в соответствии с вариантом См. Создать форму с помощью мастера. Создать форму с помощью конструктора см.
50518. Безопасность жизнедеятельности. Лабораторный практикум 244.5 KB
  Оптимальные и допустимые величины показателей микроклимата устанавливаются в зависимости от: 1 периода года; холодный период года характеризуется среднесуточной температурой наружного воздуха 10оС и ниже теплый выше 10оС; 2 категории работ по уровню энергозатрат организма.54896 устанавливает что при температуре воздуха на рабочих местах 25 оС и выше...
50519. Закрытый склад. Расчет деревянной конструкции 373.77 KB
  В курсовом проекте произведен расчет деревянных конструкций гнутоклееной рамы. Определены расчетные и нормативные нагрузки на перекрытие и поперечную раму здания. Подобрано сечение элементов поперечника. Выбраны конструктивные решения. Осуществлены расчеты узлов поперечника.
50520. Исследование процессов во влажном воздухе 138.5 KB
  Изучение процессов изменения состояния влажного воздуха приобретение навыков измерения влажности с помощью аспирационного психрометра и Id диаграммы. Смесь сухого воздуха с водяным паром называется влажным воздухом. Соответственно этому влажный воздух бывает: насыщенным влажным воздухом – смесь сухого воздуха с насыщенным водяным паром; ненасыщенным влажным воздухом – смесь сухого воздуха с перегретым водяным паром. При дальнейшем охлаждении влажного воздуха происходит конденсация пара.
50521. Определение настроек BIOS персонального компьютера 62 KB
  Раздел Power Параметр CPI PIC support установлен в положение Enbled разрешено. Возможные значения: Enbled Disbled. Следует оставить данный параметр без изменений Enbled поскольку данным процессором используется технология HyperTreding в противном случае можно нарушить нормальное функционирование системы либо снизить ее производительность. Параметр Microcode Updtion установлен в положение Enbled.
50523. ДОСЛІДЖЕННЯ ПРИНЦИПІВ РОБОТИ ВИМІРЮВАЛЬНИХ КАНАЛІВ ТЕМПЕРАТУРИ НА БАЗІ МІКРОПРОЦЕСОРНОГО ВИМІРЮВАЧА-РЕГУЛЯТОРА ТРМ1 869.5 KB
  Ознайомлення з методами вимірювання температури. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ Методи вимірювання температури і температурні шкали Виміряти температуру якогонебудь тіла безпосередньо тобто так як вимірюють інші фізичні величини наприклад довжину масу обєм або час не представляється можливим тому що в природі не існує еталона або зразка одиниці цієї величини. Тому визначення температури речовини роблять за допомогою спостереження за зміною фізичних властивостей іншої так званої термометричної речовини яка при зіткненні з нагрітим...
50525. Склад сыпучих материалов. Расчет деревянных конструкций поперечника 276.98 KB
  В данном курсовом проекте подобрано наиболее рациональное кон-структивное решение проектируемого здания, сконструированы и рассчитаны основные несущие и ограждающие конструкции, узловые соединения, выбраны мероприятия по защите элементов здания от гниения и возгорания. Все принятые конструктивные решения и расчетные алгоритмы соответствуют требованиям действующих нормативных документов