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 – Сообщение о ошибке заполнения



 

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

34697. Общие, средние и предельные издержки фирмы 17.64 KB
  Общие средние и предельные издержки фирмы. Экономисты различают общие средние и предельные издержки. Общие издержки ТC это издержки всего выпуска продукта фирмы. Общие издержки делятся на постоянные и переменные издержки.
34698. Типы экономических систем. Традиционная экономическая система 19.1 KB
  Традиционная экономическая система. Экономическая наука выделяет четыре основных типа экономических систем: традиционная командная или административноплановая рыночная смешанная. Самой древней из экономических систем является традиционная система. Традиционная экономическая система способ организации экономической жизни при котором земля и капитал находятся в общем владении племени а ограниченные ресурсы распределяются в соответствии с длительно существующими традициями.
34699. Административно-плановая (командная) экономическая система 23.83 KB
  Административноплановая командная экономическая система существовала в СССР. Это объяснялось тем что в городах практически отсутствовало жилье для вновь прибывших и тем что в соответствии с законом СССР было очень сложно получить постоянную прописку в данном городе. Высшим плановым органом являлся Госплан СССР. Госплан СССР определял плановые задания республиканским и местным плановым органам а также плановым отделам министерств и ведомств которые давали плановые задания государственным предприятиям то есть указывали им...
34700. Монополия. Монопольная власть. Условия максимизации прибыли при монополии. Ценовая дискриминация 17.8 KB
  Монополия. Монополия тип рыночной системы в котором существует только один продавец контролирующий всю отрасль производства определенного товара не имеющего близкого заменителя. Закрытая монополия. Естественная монополия отрасль в которой долгосрочные средние издержки минимальны только тогда когда одна фирма обслуживает весь рынок целиком.
34701. Экономическая рента 16.61 KB
  Рассмотрим понятие экономической ренты на примере рынка труда где экономическая рента равна разности между фактической ценой труда и тем ее уровнем который достаточно для того чтобы привлечь работника трудиться по данной профессии рисунок1 Ставка зарплаты в час W1 Е S А D L1 Колво чел.L 0 1 2 3 4 5 Допустим что...
34702. Коммерческие банки. Центральный банк 17.35 KB
  Поэтому все частные банки называют коммерческими банками в отличие от Центрального банка. Операции любого банка подразделяются на пассивные и активные. Создание коммерческого банка начинается с того что его владелец акционерное общество должен инвестировать сложить собственные деньги в кассу банка деньги в строительство здания в оборудование сейфы и др. Чем выше процентная ставка по вкладу тем больше вкладчиков у банка.
34703. Бухгалтерские издержки и прибыль 20.08 KB
  Бухгалтерские издержки и прибыль. Экономические издержки и прибыль. Издержки производства поразному определяются бухгалтером и экономистом. Бухгалтер определяет издержки чтобы установить во что обошлось фирме производство продукции.
34704. Рынок и его функции. Виды рынков. Рыночная экономическая система 22.68 KB
  Рынок и его функции. Для домашней хозяйки рынок это городской базар или магазин. Поэтому рынок это форма контактов между продавцами и покупателями товаров и услуг недвижимости ценных бумаг и валюты. Таким образом рынок выполняет информационную функцию то есть через постоянно меняющиеся цены рынок сообщает производителям где и какой продукции не хватает где и какая продукция произведена с избытком.
34705. Смешанная экономическая система 16.52 KB
  СМЕШАННАЯ ЭКОНОМИКА это рыночная система основанная на частной собственности и свободном предпринимательстве регулируемая государством. В смешанной экономике активную роль играет государство. Государство вырабатывает правила игры создает законы которые должны обеспечить всем участникам хозяйственной деятельности равные права: государство ведет борьбу с недобросовестной конкуренцией контролирует деятельность фирм с целью недопущения незаконных финансовых операций и нарушения прав потребителей защищает от злоупотребления крупными...