Концептуальное модельное представление задачи как системы

Курсовой проект

 

 

Тема: «Модель интеллектуальной рекурсивной машины – генератора вспомогательных концептуальных моделей задач – базовой исходной концептуальной модели»

Дисциплина: Моделирование систем

 

 

Студент: Соловьев А.Н.

Группа: ИТС-3-07

Руководитель: Нечаев В.В.

 

МОСКВА 2010

Оглавление

Введение. 3

Концептуальное модельное представление задачи как системы.. 4

Программная реализация представления концептуальной модели задачи. 8

Решение задач посредством прямого расчёта. 8

Судоку. 13

Решение судоку. 14

Разрешение концептуальных моделей. 14

Метод полного перебора. 17

Логические методы решения. 19

Составление судоку. 25

Составление открытием.. 25

Решение вычёркиванием.. 26

Переносимость и интегрируемость. 27

Литература. 28

Приложение 1. Программный код. 29

Решатель математических моделей. 29

Решатель судоку методом полного перебора. 35

Решатель судоку аналитическими методами. 35

Генератор судоку методом открытий. 43

 

 

Введение

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

В ходе данной работы будет рассмотрено представление концептуальной модели задачи (КМЗ) на основе триады «Задача – Данные – Решатель» и работа одного из компонентов подобной системы – генератора вспомогательных концептуальных моделей.

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

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

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

 

Программная реализация представления концептуальной модели задачи

Судоку

Судоку (яп. 数独 су:доку) — популярная головоломка-пазл с числами. В переводе с японского «су» — «цифра», «доку» — «стоящая отдельно». Иногда судоку называют «магическим квадратом», что в общем-то не верно, так как судоку является латинским квадратом 9-го порядка. Судоку активно публикуют газеты и журналы разных стран мира, сборники судоку издаются большими тиражами. Решение судоку — популярный вид досуга.

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

Существует несколько методов решения судоку. Условно их можно разделить на две категории – логические и вычислительные. К вычислительным методам относится метод полного перебора (BruteForce). Логические – метод одиночного квадрата, закрытого кандидата, голой и скрытой пары, крыло, slicing and dicing и методы предположений различного уровня.

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

Исходный вид разработанной программы при решении судоку такой:

Решение судоку

Метод полного перебора

Метод полного перебора действует следующим образом:

1. Ведётся поиск первого вхождения 0 (то есть пустой клетки)

2. Если вхождений нет, значит мы получили решение

3. Определяются цифры, которые могут входить в данную клетку (с учётом столбца, строки и малого квадрата). Определение осуществляется функцией:

c = [s[j] for j in range(81)

if not ((i-j)%9 * (i//9^j//9) * (i//27^j//27 | (i%9//3^j%9//3)))]

1. (i-j)%9 – вхождение в столбец

2. (i//9^j//9) – вхождение в строку

3. (i//27^j//27 | (i%9//3^j%9//3)) – блок из трёх строк

4. В случае вхождения получается 0

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

5. Если нет чисел, которые мы можем вставить в данную клетку, значит метод зашёл в тупик и следует выход из рекурсии на шаг выше.

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

Но существуют задачи, которые алгоритм полного перебора будет решать очень долго. Возьмём для примера судоку под названием «Star Burst Leo»

Было оценено, что для решения данного судоку потребуется 641 580 331 итерация, причём в данном случае в итерации не входит процесс поиска цифр, которые можно внести в данную клетку.

На рисунке 16 показано распределение числа заполненных клеток (ось ординат) от уровня рекурсии (ось абсцисс). Таким образом можно оценить, что процесс перебора доходит до 72 заполненных клеток, а затем встречает несоответствие и ему приходится возвращаться, причём мы видим чёткие полосы в районе 33, 43 и 60 заполненных клеток.

Логические методы решения

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

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

Все методы рассматриваются в статье [2], но здесь я опишу несколько из них.

Первый метод – Х-крыло.

«X-крыло» — позиция, когда один из кандидатов дважды (и только дважды) встречается в двух строчках головоломки. Эти кандидаты должны входить в две колонки, что обеспечивает формирование прямоугольного Х-крыла. Также две колонки с двумя (и только с двумя) клетками, которые содержат одинаковых кандидатов (входящие в две строки) также формируют X-крыло. Эти четыре клетки — единственные возможные места расположения для «настоящих» кандидатов в этих строках или колонках. Другие подобные кандидаты, расположенные по периметру прямоугольника, образованного «настоящими» кандидатами, должны быть удалены. Возможно эта комбинация была названа X-крылом потому, что

Рассмотрим пример решения Х-крыла (рисунок вверху). Как видим, для легкости восприятия из кандидатов отображены только шестерки (был применен фильтр кандидатов — программа Simple Sudoku это умеет делать).

Синие и ярко-зеленые ячейки формируют классическое «X-крыло» — первая и девятая строчки имеют только по две ячейки с кандидатом 6, их разделяют две колонки (седьмая и восьмая), кандидаты образуют прямоугольник. «Настоящих» кандидатов представляют синие, или ярко-зеленые ячейки. Потому другие кандидаты в шестой и девятой колонках нужно удалить (они выделены желтым контуром).

 

 

Slicind and dacing

Рассмотрим метод slicing and dacing на примере:

На первом шаге рассматриваются пересечения столбца и строки для цифры 1 в рамках квадрата G1-I3. Получается, что 1 может стоять либо на позиции H1 либо на позиции I1.

На основе полученного результата на первом шаге просматривается полученная строка. В квадрате D1-F3 с учётом стоящей на позиции E8 единицы и полученной на первом шаге строки остаётся только одна позиция – D2. Таким образом, после работы алгоритма получаем судоку:

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

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

При решении стандартными логическими методами (скрытые пары, скрытые квадраты и т. п.) решение не найдено:

Но мы видим, что в клетках B3 и C3 может стоять только пара 46. Алгоритм делает предположение, что стоит в B3 стоит 4, доходит до несоответствия, ставит 6 и получает результат:

Таким образом исходное судоку разрешено.

Блок-схема алгоритма выглядит следующим образом:

Составление судоку

Составление судоку может осуществляться двумя методами – либо сокрытием случайной ячейки после составления правильного латинского квадрата, либо наоборот открытием случайных ячеек. В первом случае после каждого шага выполняется решение и проверяется количество итераций и их сложность (применение методов первичных, slicing and dicing, предположений).

Составление открытием

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

 

Решение вычёркиванием

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

Литература

1. Нечаев В.В. Концептуальное модельное представление задачи как системы. Информационные технологии, № --. 2009. ----- с.

2. http://www.angusj.com/sudoku/hints.php

 

 

 

Приложение. Программный код

Курсовой проект

 

 

Тема: «Модель интеллектуальной рекурсивной машины – генератора вспомогательных концептуальных моделей задач – базовой исходной концептуальной модели»

Дисциплина: Моделирование систем

 

 

Студент: Соловьев А.Н.

Группа: ИТС-3-07

Руководитель: Нечаев В.В.

 

МОСКВА 2010

Оглавление

Введение. 3

Концептуальное модельное представление задачи как системы.. 4

Программная реализация представления концептуальной модели задачи. 8

Решение задач посредством прямого расчёта. 8

Судоку. 13

Решение судоку. 14

Разрешение концептуальных моделей. 14

Метод полного перебора. 17

Логические методы решения. 19

Составление судоку. 25

Составление открытием.. 25

Решение вычёркиванием.. 26

Переносимость и интегрируемость. 27

Литература. 28

Приложение 1. Программный код. 29

Решатель математических моделей. 29

Решатель судоку методом полного перебора. 35

Решатель судоку аналитическими методами. 35

Генератор судоку методом открытий. 43

 

 

Введение

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

В ходе данной работы будет рассмотрено представление концептуальной модели задачи (КМЗ) на основе триады «Задача – Данные – Решатель» и работа одного из компонентов подобной системы – генератора вспомогательных концептуальных моделей.

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

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

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

 

Концептуальное модельное представление задачи как системы

Деятельность человека имеет две основные формы: умственную - “деятельность мозга” и физическую - “деятельность рук”. Очевидно, что и умственная и физическая деятельность сопряжены с постоянной необходимостью решения разнообразных задач. Спектр таких задач определяется многочисленными факторами, как существенными, так и малозначимыми. К существенным факторам, прежде всего, следует отнести причины возникновения задачи. В качестве первопричины, порождающей задачу, выступают потребности человека. Удовлетворение потребностей осуществляется в процессе взаимодействия человека не только с внешней, но и с собственной внутренней средой, т.е. с природой, с другими людьми или самим собой. Реализация потребностей всегда связана с решением соответствующих этим потребностям задач. Практически весь спектр потребностей человека определяется тремя сферами его деятельности: материальной, социальной и духовной. Следовательно, можно констатировать, что возникновение задач обусловлено материальными, социальными и духовными факторами. К существенным факторам, определяющим содержание и свойства задач, следует также отнести: предметную область существования задачи, её размерность и уровень сложности, степень определенности, возможности формализации, полноту исходных данных, требования к конечному результату, а также ряд других свойств, характеристик, параметров и особенностей.

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

Концептуальная модель задачи разрабатывалась на основе методов системно-комплексного анализа (СК - анализа) “ внутреннего устройства задачи ”, как целостной системы, и её внешнего окружения - среды существования задачи. Для успешного разрешения проблемы создания КМЗ использовались:

· системно-комплексный подход и СК-анализ;

· основы теории концептуального моделирования;

· методологические аспекты метамоделирования;

· технология концептуального метамоделирования (КММ - технология), а также метод раскрытия неопределённости системной задачи на уровне её концептуального представления, основанный на метазадачной технологии и рекурсивных механизмах, приводящий к рекурсивным и взаимнорекурсивным структурам системной КМЗ.

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

Многоуровневое представление концептуальной модели системной задачи осуществляется на основе метода стратификации. Для формирования страт - уровней организации задачи необходим критерий или основание стратификации. В качестве такого критерия в рассматриваемом случае целесообразно выбрать показатель неопределённости системной задачи . В соответствие с указанным критерием введём качественную шкалу неопределённости. На шкале неопределённости ранжируем компоненты концептуальной модели, представленной системой кортежей (1), по степени возрастания неопределённости. При этом будет иметь место следующая последовательность страт - уровней неопределённости системной задачи:

· конечного результата — решения - ;

· исходных данных (начальной информации) - ;

· показателя адекватности - ;

· программы решения задачи - ;

· алгоритма решения задачи - ;

· метода решения задачи - ;

· цели системной задачи - ;

· среды существования задачи - .

Графическая интерпретация шкалы неопределённости имеет вид, представленный на рис.1. В последовательности страт (см. рис. 1) определённость задачи возрастает при движении по шкале сверху вниз. При этом, каждый выделенный на шкале уровень - страта разбивает её на две части. Верхняя часть шкалы включает все известные (определённые) компоненты, а нижняя - компоненты, которые необходимо определить, т.е. неизвестные.

 

 

 

Рис. 2. Ранжированное представление компонентов системной задачи

по шкале неопределённости

 

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

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

КМСЗ – концептуальная модель системной задачи

ПЦНД – критерии полноты, целостности, необходимости, достаточности

Ан-р – анализатор

ГВЗ – генератор вспомогательных задач

КМВЗ – концептуальная модель вспомогательной задачи

На основании концептуальной модели системной задачи, которая представляется концептом 0го ранга (К) мы разворачиваем пирамиду, каждым уровнем которой будут соответствующие концептуальные вспомогательные задачи (В).

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