Программный комплекс для лабораторных работ по курсу "Интеллектуальные системы"

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

ВВЕДЕНИЕ

В этой работе разрабатывается программный комплекс для лабораторных работ по курсуинтеллектуальные системы на основе поиска в пространстве состояний.

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

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



АНАЛИЗ АЛГОРИТМА ПОИСК В ПРОСТРАНСТВЕ СОСТОЯНИЙ

Поиск в пространстве состояний- это группа различных математических методов, которые являются основаниемвреализации задач ИИ.

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

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

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

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

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

Путь от начального состояния до целевого состояния называетсярешением задачи.

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

Качество алгоритма определяется следующими показателями.

Полнота алгоритма это такое свойство при котором всегда находится решение при его существовании.

Пространственная сложность информация об объёме памяти, которое потребуется алгоритму.

Оптимальность свойство алгоритма всегда находить решение с наименьшей стоимостью.

Временная сложность оценивает время работы алгоритма.

Методы поиска в пространстве состояний делятся на неинформированные и информированные.

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

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

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

Информированный поиск- это такая стратегия поиска решений в пространстве состояний, в которой используетсяинформация, относящаяся к конкретной задаче. Информированные методы обычно бывают более эффективными по сравнению с неинформированными методами.[1]

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

Алгоритмы поиска:

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

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

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

Данный метод один из первых предложили Аилсой Ленд и Элисон Дойг в 1960 году для решения задач целочисленного программирования.

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

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

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

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

Значение является минимумом функции и достигается на соответствующем подмножестве, при условии если нижняя граница для узла графасойдется с верхней границей, то это

Данный метод применяется для решения задач коммивояжёра и задачи о ранце.

3. Поиск по первому наилучшему совпадению

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

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

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

Алгоритм поиска A* (А-звездочка) является примером оптимального поиска «лучший - первый».

Использование жадного алгоритма расширяет первого потомка родителей. После генерации потомков:

Если эвристическая оценка потомка лучше, чем у его родителя, потомок ставится в начало очереди (с родителями повторно прямо за ним), и цикл перезапускается.

Иначе потомок ставится в очередь (в месте, определяемом его эвристической стоимостью). Далее производится оценка оставшихся наследников у родителя (если они имеются).

4. Поиск A* (А звезда илиА стар) - в математике и информатике, алгоритм поиска по первому наилучшему совпадению на графе, который определяет маршрут с наименьшей стоимостью от одной вершины к другой.

Порядок обхода вершин определяется эвристической функцией «стоимость +расстояние» (обычно обозначаемой как f(x)). Эта функция - сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет), и функции эвристической оценки расстояния от рассматриваемой вершины к конечной (обозначается как h(x)).

Этот алгоритм был впервые описан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. Это по сути было расширение алгоритма Дейкстры, созданного в 1959 году. Новый алгоритм достигал более высокой производительности (по времени) с помощью эвристики. В их работе он упоминается как «алгоритм A». Но так как он вычисляет лучший маршрут для заданной эвристики, он был назван A*.[2]

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

Алгоритмы данного поиска:

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

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

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

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

Для исследования топологических свойств графов подойдет алгоритм поиска в глубину

Поиск в глубину - естественный выбор, когда человек лично ходит по лабиринту и видит то, что непосредственно рядом с ним. Идёт, ведя левой рукой по стенке, это будет поиском в глубину, если лабиринт древовидный.[4]

Четвертым алгоритмом является поиск с возвратом илибэктрекинг.Бэктрекинг используется для нахождения решений задачи, в которой требуется полный перебор вариантов. Термин бэктрекингввел американский ученый Дерриком Генри Лемером в 1950 году.Решение задачи бэктрекингосновывается к последовательному расширению частичного решения. Если на следующем шаге такое расширение провести не удается, то возвращаются к более короткому частичному решению и продолжают поиск дальше. Бэктрекинг позволяет найти все решения поставленной задачи. Для быстроты исполнения метода стараются организовать вычисления таким образом, чтобы как можно раньше выявлять заведомо ненужные варианты, что поможет уменьшить время поиска решения задачи. Основным примером использования бэктрекинга является задача о расстановке ферзей, в которой нужно расставлять на шахматной доске восемь ферзей так, чтобы ни один из них не находился под угрозой другого. Сначала на шахматную доску ставят одного из восьми ферзя, а потом ставят каждого следующего ферзя так, чтобы его не могли атаковатьпоставленные на доску ферзи. В ситуации если на следующем шаге ферзя нельзя поставить, то возвращаются на предыдущий шаг и пробуютустановить ранее поставленного ферзя на другое место. С помощью рассматриваемого метода можно решить и другие задачи с перебором.

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



АНАЛИЗ ТРЕБОВАНИЙ К РАЗРАБАТЫВАЕМОМУ ПО

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

Остановимся на трех: крестики-нолики, задача о расстановке ферзей, пятнашки.

Крестики-нолики - игра на логикуна двоих на поле 3х3 клетки. Один игрок ставит на поле крестики, другой нолики.Игрокисоблюдая очередностьрасставляют на свободные клетки свои фигуры (Х или О). Кто первый выстроит по вертикали, горизонтали или диагонали в ряд три своих фигуры становится победителем.

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

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

Пятнашки были придуманы Ноем Чепмэном в1878 году. Головоломка имеет набор квадратных табличек с числами, заключённых в квадратную коробку. В наборе 15 табличек. И получается, что в коробке 4х4 остается пустое место для таблички. Суть игры в том, что нужно перемещатьтаблички по коробушке, идобитьсячто бы их по номера шли по порядку, сделав это за меньшее число ходов.[6]

АНАЛИЗ И ВЫБОР СРЕДСТВ РАЗРАБОТКИ

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

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

Современные средства разработки должны использовать визуальные компоненты для наглядного проектирования интерфейса, поддерживать БД, иметь возможность использования CASE-технологий, поддерживать объектно-ориентированного стиль программирования. Даннымифункциями обладают:BorlandC++ Builder, MicrosoftVisualStudio.

Для реализации программного комплекса была выбрана MicrosoftVisualStudio. Она предоставляет большие возможности для программирования программ.

MicrosoftVisualStudio - это продукт Microsoft для быстрого создания различного рода программ.MicrosoftVisualStudio имеет производительный инструмент визуального построения приложений. Онсостоитизнастоящего компилятора кода и предоставляет пользователю средства визуального программирования.

MicrosoftVisualStudioпроизводит небольшие по размерам и эффективные исполняемые модули

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

Работодателей волнует как быстро и насколько качественно будут создаваться их программы.MicrosoftVisualStudiможет обеспечить это, она реально может взять на себя выполнение работы по подготовке приложений. Так же она может согласовывать деятельность группы постановщиков, кодировщиков, тестеров и технических писателей. Возможности MicrosoftVisualStudio полностью отвечают требованиям.[7]

РЕАЛИЗАЦИЯ

Все программы реализованы на языке программирования с++.

Крестики-нолики.

Разработанная программа состоит из трёх модулей:

Game_logic.cpp - модуль с правилами проверки выигрыша.

Bot.cpp - модуль искусственного интеллекта.

Field.cpp - модуль проекта.

Реализация логики игры:

ФункцияInt32 Game_logic::Checkпроверкавыигрыша.

ФункцияBooleanGame_logic::Check_1(array<Int16, 2>^ minor) поисквыигрышаповертикали

ФункцияBoolean Game_logic::Check_2(array<Int16, 2>^ minor) поисквыигрышаподиагонали

ФункцияBoolean Game_logic::Check_3(array<Int16, 2>^ minor) поиск выигрыша по горизонтали

Реализация искусственного интеллекта выглядит:

ФункцияVoidBot::Get_neighbors() ищетзанятыеячейки.

Функция Void Bot::Get_free_points(int x, int y) ищетсвободныеячейки.

ФункцияInt32 Bot::Calculate(intgamer, intn, intm) высчитываетв какую ячейку поставить для выигрыша в партии.

Реализацияигровойдоски:

ФункцияVoidField::Fill_elem(Int32 n, Int32 m) ставитнаполеXилиO.

ФункцияVoidField::Draw_field() рисуетдоску и выводит выигрышное состояние.

Функция VoidField::Replay() позволяет начать игру заново.

Задача о расстановке ферзей

Разработанная программа состоит из двух модулей:

1. Unit.cpp- модуль содержащий алгоритма перебора с возвратом и визуализации;

2. Queens.cpp - файл проекта.

Непосредственно функция рисования состояния доски выполняется в обработчике формы void __fastcall TForm1::paintBoardPaint(TObject *Sender).

Поиск решения производится при помощи «поиска в глубину», то есть рекурсивным вызовом одной и той же функции «rSolve».

Функции, используемые для решения задачи о расстановке ферзей:

1. voidModifyBoard(intRow,intColumn, intd) - внесение изменений приустановки/снятии ферзя в матрицу «угроз»;

2. voidPutQueen(intRow,intColumn) -ставит на доску ферзя

3. voidGetQueen(intRow,int Column) - снятиесдоскиферзя;

4. voidrSolve(intColumn) - рекурсивная часть решения, обрабатывает отдельно взятую вертикаль и вызывает себя для следующей вертикали;

5. voiddeleteLog() - освобождают память доски, используется при изменении размера доски;

6. voiddeleteBoard() - освобождают память журнала, используется при изменении размера доски;

7. voidSolve() - поиск решения.

Пятнашки.

Разработанная программа состоит модуля:Sceleton_DIALOG.cpp

Реализация

ФункцияvoidSwapElements(intnum)обменивает местами элементы если пустая ячейка рядом

Функция void RanddomMass(void) заполняет поле случайными числами.

ФункцияintFindElements(intD) ищетпозициичисла

ФункцияvoidTrasser_patch(intstart, intfinish)создает маршрт из точки А в точку В при использовании алгоритма А*.

ФункцияintTrass_Parent(intparent) устанавливает новую точку родителя.

ФункцияboolCheck_Block_Position(intp)проверяет заблокирована ли данная позиция в массиве блокированных элементов n_block

ФункцияintTrasser_Area(staticintaa) определяетв каком направлении можно двигаться на поле.

Функция intSteps(inta1, inta2) ведет подсчет числа шагов к от одной точки к другой.

Функция void Set_ElementPosition(int number,int ni) ставитчисловнужнуюпозицию.

Функция bool Make_Line_End(void) сборкаэлементов.



ТЕСТИРОВАНИЕ

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

Тестирование программы проводилось в условиях близких к реальному использованию.

Крестики-нолики.

Примеры состояний программы:

Начальное состояние доски показано на рисунке 1.

Рисунок 1 - Начальное состояние.

Мы видим пустое поле 3х3. Так же имеются кнопка «Выход», при нажатии программа закрывается и кнопка «Перезапустить», при нажатии программа переходит в начальное состояние и игра начинается заново.

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

Рисунок 2 - Победный результат

Так же есть ситуация ничьи. Когда никому не удалось собрать выигрышную ситуацию. Программа останавливается и желтым цветом ничего не выделяется. Ситуация показана на рисунке 3. Так же остаются активные кнопки Перезапустить и Выход.

Рисунок 3 - Ситуация ничьи

Задача о расстановке ферзей.

Примеры состояний программы:

Начальное состояние доски показано на рисунке 4.

Рисунок 4 - Начальное состояние

Слева на форме расположено изображение доски с условными отметками на ней. Красным кругом обозначаются клетки, в которых расположены ферзи, красными точками отмечены клетки, находящиеся под боем уже установленных фигур и не исключенные применяемыми эвристиками.

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

Справа от доски расположен выпадающий список для выбора размера доски.

Следующая группа управляющих элементов предназначена для визуализации алгоритма:

1. кнопка, приостанавливающая визуализацию («Stop»);

2. кнопка, запускающая выполнение визуализации («Play»);

3. кнопка, возвращающая процесс визуализации в начало («|<»);

4. кнопка, выполняющая возврат на один шаг(«<»);

5. кнопка, выполняющая переход к заданному шагу алгоритма, номер шага вводится пользователем в отдельном окне (« »);

6. кнопка, выполняющая один шаг(«>»);

7. кнопка, возвращающая процесс визуализации в конец(«>|»).

Элемент под кнопками показывает процент выполненных шагов.

Для настройки скорости воспроизведения визуализации используется выпадающий список.

На форме выводится информация о текущем шаге и общем количестве шагов алгоритма.

При нажатии на кнопку Playпроисходит перебор расстановок ферзей на доске с выводом информации, описывающей текущий шаг алгоритма показано на рисунке 5.

Рисунок 5 - Перебор расстановок.

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

Рисунок 6 - Расстановка найдена.

Пятнашки.

Пример состояний программы:

Начальное состояние программы показано на рисунке 7.

Рисунок 7 - Начальное состояние.

При нажатии вкладки Mainвыходит меню со списком выбора, показано на рисунке 8. Можно выбрать «New», «Go!!!»

Рисунок 8 - Список выбора.

При выборе на вкладке Main«New» сгенерируется рандомное поле, которое показано на рисунке 9.

Рисунок 9 - Сгенерируемое поле.

И можно начинать собирать пазл. При нажатии на число, если оно стоит рядом с пустой ячейкой, то они поменяются местами.

При выборе на вкладке Main«Go!!!» программа начнет автоматически собирать пазл и в конце выдаст информацию с поздравлением.

При тестировании программного комплекса была продемонстрирована работоспособность всех программ. Ситуации, в которых поведение программы являетсянеправильным были не выявлены.



ЗАКЛЮЧЕНИЕ

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

В данной работе рассмотрены теоретические вопросы, касающиеся алгоритма поиска в пространстве.

Разработанный программный комплекс является примером использования алгоритма поиска в пространстве состояний и включает в себя три программы: крестики-нолики, задача о расстановке ферзей, пятнашки.

совпадение поиск крестики пятнашки



СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Стюарт Рассел Искусственный интеллект: современный подход- 2-е изд. /Стюарт Рассел, Питер Норвиг - М.: «Вильямс», 2006. - 1408 с.

Лорьер Ж.Л. Системы искусственного интеллекта / Ж. Л.Лорьер, В. Л. Стефанюка. - М.: Мир, 1991. - 568 с.

Левитин А. В. Алгоритмы. Введение в разработку и анализ / А. В.Левитин - М.: «Вильямс», 2006. - 576 с.

Кормен Т. Алгоритмы: построение и анализ(второе издание) / Т.Кормен, Ч.Лейзерсон,Р.Ривест- М.: «Вильямс», 2005. - 1290 с.

Павлов С.Н. Системы искусственного интеллекта : учеб.пособие. В 2-х частях. / С. Н. Павлов. - Томск: «Эль Контент», 2011. - Ч. 1. - 176 c.

Люгер Искусственный интеллект: стратегии и методы решения сложных проблем / Люгер, Ф. Джордж - М.: «Вильямс», 2003. - 864 с.

Ник Рендольф VisualStudio 2010 для профессионалов = ProfessionalVisualStudio 2010 / Н. Рендольф, Д. Гарднер, М. Минутилло, К. Андерсон - М.: «Диалектика», 2011. - С. 1184



ПРИЛОЖЕНИЕ

(обязательное)

Исходный код программного комплекса.

Крестики-нолики.

Bot.cpp

#include "Bot.h"

Bot::Bot(array<Int16, 2>^ field)

{

this->field = field;

grid_advantage = gcnew array<Int16, 2>(field->GetLength(0), field->GetLength(1));

for (Int32 i = 0; i < field->GetLength(0); i++)

{

for (Int32 j = 0; j < field->GetLength(1); j++)

{

grid_advantage[i, j] = -1;

}

}

}

Void Bot::Get_neighbors()

{

for (Int32 i = 0; i < field->GetLength(0); i++)

{

for (Int32 j = 0; j < field->GetLength(1); j++)

{

if(field[i,j] != 0)Get_free_points(i, j);

}

}

}

Void Bot::Get_free_points(int x, int y)

{

for (Int32 i = x - 1; i <= x + 1; i++)

{

for (Int32 j = y - 1; j <= y + 1; j++)

{

if (i < 0 || i >= field->GetLength(0) || j < 0 ||j >= field->GetLength(1) || (i == x && j == y))

{

continue;

}

else

{

if (field[i,j] == 0)

{

grid_advantage[i, j] = 0;

}

}

}

}

}

Void Bot::Calculate_point_gravity()

{

int player_gravity, bot_gravity;

Get_neighbors();

for (Int32 i = 0; i < grid_advantage->GetLength(0); i++)

for (Int32 j = 0; j < grid_advantage->GetLength(1); j++)

{

if (grid_advantage[i, j] == 0)

{

player_gravity = Calculate(1, i, j);

bot_gravity = Calculate(2, i, j);

grid_advantage[i, j] = player_gravity + bot_gravity;

}

}

}

Void Bot::Start()

{

Calculate_point_gravity();

int max = -1;

int _n, _m;

for (int i = 0; i < grid_advantage->GetLength(0); i++){

for (int j = 0; j < grid_advantage->GetLength(1); j++)

{

if(max < grid_advantage[i, j])

{

max = grid_advantage[i, j];

_n = i;

_m = j;

}

}

}

field[_n, _m] = 2;

}

Int32 Bot::Calculate(int gamer, int n, int m)

{

int gravity_of_cell = 0;

int gravity_of_sequence = 0;

field[n, m] = gamer; // устанавливаем новое значение

int end;

// веспогоризонтали

(grid_advantage->GetLongLength(1) - m) <= 3 ?

end = grid_advantage->GetLongLength(1) :

end = m + 3;

for (int first_of_segment = m; first_of_segment < end; first_of_segment++)

{

if (first_of_segment - 2 >= 0)

{

for (int k = 2; k >= 0; k--)

{

if (field[n, first_of_segment - k] == 0) continue;

if (field[n, first_of_segment - k] != gamer)

{

gravity_of_sequence = 0;

break;

}

if (field[n, first_of_segment - k] == gamer)

{

gravity_of_sequence++;

continue;

}

}

if (gravity_of_sequence == 3)

{

if (gamer == 1) gravity_of_sequence = 1000;

else gravity_of_sequence = 10000;

}

gravity_of_cell += gravity_of_sequence;

gravity_of_sequence = 0;

}

}

gravity_of_sequence = 0;

// весповертикали

(grid_advantage->GetLongLength(0) - n) <= 3 ?

end = grid_advantage->GetLongLength(0) :

end = n + 3;

for (int first_of_segment = n; first_of_segment < end; first_of_segment++)

{

if (first_of_segment - 2 >= 0)

{

for (int k = 2; k >= 0; k--)

{

if (field[first_of_segment - k, m] == 0) continue;

if (field[first_of_segment - k, m] != gamer)

{

gravity_of_sequence = 0;

break;

}

if (field[first_of_segment - k, m] == gamer)

{

gravity_of_sequence++;

continue;

}

}

if (gravity_of_sequence == 3)

{

if (gamer == 1) gravity_of_sequence = 1000;

else gravity_of_sequence = 10000;

}

gravity_of_cell += gravity_of_sequence;

gravity_of_sequence = 0;

}

}

gravity_of_sequence = 0;

int end_i, end_j;

// веспопервойдиагонали "\"

(grid_advantage->GetLongLength(0) - n) <= 3 ?

end_i = grid_advantage->GetLongLength(0) :

end_i = n + 3;

(grid_advantage->GetLongLength(1) - m) <= 3 ?

end_j = grid_advantage->GetLongLength(1) :

end_j = m + 3;

for (int i = n, j = m; i < end_i && j < end_j; i++, j++)

{

if (i - 2 >= 0 && j - 2 >= 0)

{

for (int k = 2; k >= 0; k--)

{

if (field[i - k, j - k] == 0) continue;

if (field[i - k, j - k] != gamer)

{

gravity_of_sequence = 0;

break;

}

if (field[i - k, j - k] == gamer)

{

gravity_of_sequence++;

continue;

}

}

if (gravity_of_sequence == 3)

{

if (gamer == 1) gravity_of_sequence = 1000;

else gravity_of_sequence = 10000;

}

gravity_of_cell += gravity_of_sequence;

gravity_of_sequence = 0;

}

}

gravity_of_sequence = 0;

// вес по второй диагонали "/"

n - 3 <0 ?end_i = 0 :end_i = n - 2;

(grid_advantage->GetLongLength(1) - m) <= 3 ?

end_j = grid_advantage->GetLongLength(1) :

end_j = m + 3;

for (int i = n, j = m; i >= end_i && j < end_j; i--, j++)

{

if (i + 2 < grid_advantage->GetLongLength(0) && j - 2 >= 0)

{

for (int k = 2; k >= 0; k--)

{

if (field[i + k, j - k] == 0) continue;

if (field[i + k, j - k] != gamer)

{

gravity_of_sequence = 0;

break;

}

if (field[i + k, j - k] == gamer)

{

gravity_of_sequence++;

continue;

}

}

if (gravity_of_sequence == 3)

{

if (gamer == 1) gravity_of_sequence = 1000;

else gravity_of_sequence = 10000;

}

gravity_of_cell += gravity_of_sequence;

gravity_of_sequence = 0;

}

}

gravity_of_sequence = 0;

field[n, m] = 0; // возвращаемзначение

return gravity_of_cell;

}

Game_logic.cpp

#include "Game_logic.h"

Game_logic::Game_logic(array<Int16, 2>^ field)

{

this->field = field;

}

Int32 Game_logic::Start()

{

array<Int16, 2>^ minor = gcnew array<Int16, 2>(3, 3);

for (Int32 i = 0; i < field->GetLength(0); i++)

for (Int32 j = 0; j < field->GetLength(1); j++)

{

if (!Get_minor(minor, i, j)) break;

switch (Check(minor))

{

case 0:

{

continue;

break;

}

case 1:

{

return 1;

break;

}

case 2:

{

return 2;

break;

}

case 3:

{

return 3;

break;

}

}

}

}

Boolean Game_logic::Get_minor(array<Int16, 2>^ minor, Int32 x, Int32 y)

{

if (x + 3 > field->GetLength(0) || y + 3 > field->GetLength(1)) return false;

for (Int32 i = x, n = 0; i < x + 3; i++, n++)

for (Int32 j = y, m = 0; j < y + 3; j++, m++)

{

minor[n, m] = field[i, j];

this->x_begin = this->x_end = x;

this->y_begin = this->y_end = y;

}

return true;

}

Void Game_logic::Save_field(array<Int16, 2>^ new_field)

{

for (Int32 i = 0; i < field->GetLength(0); i++)

for (Int32 j = 0; j < field->GetLength(1); j++)

field[i, j] = new_field[i, j];

}

Int32 Game_logic::Check(array<Int16, 2>^ minor)

{

if (Check_1(minor))

{

return 1;// повертикали

}

else if (Check_2(minor))

{

return 2;// подиагонали

}

else if (Check_3(minor))

{

return 3; // погоризонтали

}

else

{

for (Int32 i = 0; i < field->GetLength(0); i++)

for (Int32 j = 0; j < field->GetLength(1); j++)

{

if (field[i, j] == 0) return 0; // игранезакончена

}

return 2;// ничья

}

}

Boolean Game_logic::Check_1(array<Int16, 2>^ minor)

{

for (int i = 0; i < 3; i++)

for (int j = 1; j < 3; j++)

{

if (minor[i, j - 1] != 0 && minor[i, j - 1] == minor[i, j])

{

if (j == 2)

{

this->x_begin += i;

this->x_end += i;

this->y_end += 2;

return true;

}

else continue;

}

else break;

}

return false;

}

Boolean Game_logic::Check_2(array<Int16, 2>^ minor)

{

for (int i = 1; i < 3; i++)

{

if (minor[i - 1, i - 1] != 0 && minor[i - 1, i - 1] == minor[i, i])

{

if (i == 2)

{

this->x_end += 2;

this->y_end += 2;

return true;

}

else continue;

}

else break;

}

for (int i = 3, tmp = 0; i >= 0; i--)

for (int j = 1; j < 3; j++)

{

if (i + j == 2)

{

if (minor[i, j] != 0 && minor[i + 1, j - 1] == minor[i, j])

{

if (++tmp == 2)

{

this->x_begin += 2;

this->y_end += 2;

return true;

}

else continue;

}

else break;

}

}

return false;

}

Boolean Game_logic::Check_3(array<Int16, 2>^ minor)

{

for (int j = 0; j < 3; j++)

for (int i = 1; i < 3; i++)

{

if (minor[i - 1, j] != 0 && minor[i - 1, j] == minor[i, j])

{

if (i == 2)

{

this->x_end +=2;

this->y_begin += j;

this->y_end += j;

return true;

}

else continue;

}

else break;

}

return false;

}

Field.cpp

#include "Field.h"

Field::Field(Graphics^ graph, Int32 count_cells)

{

this->graph = graph;

this->count_cells = count_cells;

value_of_width = this->graph->VisibleClipBounds.Width / count_cells;

value_of_height = this->graph->VisibleClipBounds.Height / count_cells;

first_gamer = true;

field = gcnew array<Int16, 2>(Convert::ToInt32(count_cells),

Convert::ToInt32(count_cells));

ts = gcnew ThreadStart(this, &Field::Start);

t = gcnew Thread(ts);

is_win = false;

this->graph->Clear(Color::White);

}

Void Field::Resize_field()

{

if (count_h_old != count_cells || count_w_old != count_cells)

{

count_w_old = count_cells;

count_h_old = count_cells;

Replay();

}

}

Void Field::Start()

{

try

{

game_logic = gcnew Game_logic(field);

how_win = game_logic->Start();

if (how_win == 1 || how_win == 2 || how_win == 3) is_win = true;

else is_win = false;

Draw_field();

}

catch (ThreadAbortException^ ex)

{

t = nullptr;

Run();

}

}

Void Field::Fill_elem(Int32 n, Int32 m)

{

Pen^ blackPen = gcnew Pen(Color::Black, 3.0f);

graph->FillRectangle(gcnew SolidBrush(Color::Yellow), n, m,

value_of_width - 1, value_of_height - 1);

if (field[game_logic->x_begin, game_logic->y_begin] == 1)

{

// нарисовать X

graph->DrawLine(blackPen, n + 10, m + 10,

n + value_of_width - 10,

m + value_of_height - 10);

graph->DrawLine(blackPen, n + value_of_width - 10, m + 10,

n + 10,

m + value_of_height - 10);

Rectangle rect = Rectangle(n, m, value_of_width, value_of_height);

graph->DrawRectangle(gcnew Pen(Color::Black, 2.0f), rect);

}

else

{

// нарисовать O

graph->DrawEllipse(blackPen, n + 10, m + 10, value_of_width - 22, value_of_height - 22);

Rectangle rect = Rectangle(n, m, value_of_width, value_of_height);

graph->DrawRectangle(gcnew Pen(Color::Black, 2.0f), rect);

}

}

Void Field::Draw_field()

{

try

{

Resize_field();

graph->Clear(Color::White);

value_of_width = graph->VisibleClipBounds.Width / count_cells;

value_of_height = graph->VisibleClipBounds.Height / count_cells;

Int32 n_begin = (graph->VisibleClipBounds.Width - value_of_width * count_cells) / 2;

Int32 m_begin = (graph->VisibleClipBounds.Height - value_of_height * count_cells) / 2;

Pen^ blackPen = gcnew Pen(Color::Black, 3.0f);

for (Int32 i = 0, n = n_begin; i < count_cells; i++, n = n + value_of_width)

for (Int32 j = 0, m = m_begin; j < count_cells; j++, m = m + value_of_height)

{

if (field[i, j] == 1)

{

// нарисоватьХ

graph->DrawLine(blackPen, n + 10, m + 10,

n + value_of_width - 10,

m + value_of_height - 10);

graph->DrawLine(blackPen, n + value_of_width - 10, m + 10,

n + 10,

m + value_of_height - 10);

Rectangle rect = Rectangle(n, m, value_of_width, value_of_height);

graph->DrawRectangle(gcnew Pen(Color::Black, 2.0f), rect);

}

else if (field[i, j] == 2)

{

// нарисовать O

graph->DrawEllipse(blackPen, n + 10, m + 10, value_of_width - 22, value_of_height - 22);

Rectangle rect = Rectangle(n, m, value_of_width, value_of_height);

graph->DrawRectangle(gcnew Pen(Color::Black, 2.0f), rect);

}

else

{

Rectangle rect = Rectangle(n, m, value_of_width, value_of_height);

graph->DrawRectangle(gcnew Pen(Color::Black, 2.0f), rect);

}

}

if (is_win)

{

Int32 n_begin = (graph->VisibleClipBounds.Width - value_of_width * count_cells) / 2;

Int32 m_begin = (graph->VisibleClipBounds.Height - value_of_height * count_cells) / 2;

if (how_win == 1)// по вертикали

{

Int32 n = n_begin + game_logic->x_begin * value_of_width;

for (int j = game_logic->y_begin, m = m_begin + game_logic->y_begin*value_of_height; j < game_logic->y_begin + 3; j++, m = m + value_of_height)

{

Fill_elem(n, m);

}

}

if (how_win == 2)

{

if (game_logic->x_begin < game_logic->x_end) // диагональ

{

for (int i = 0, n = n_begin + game_logic->x_begin * value_of_width; i < 3; i++, n = n + value_of_width)

for (int j = 0, m = m_begin + game_logic->y_begin*value_of_height; j < 3; j++, m = m + value_of_height)

{

if (i == j)

{

graph->FillRectangle(gcnew SolidBrush(Color::Yellow), n, m,

value_of_width - 1, value_of_height - 1);

if (field[game_logic->x_begin, game_logic->y_begin] == 1)

{

// нарисовать X

graph->DrawLine(blackPen, n + 10, m + 10,

n + value_of_width - 10,

m + value_of_height - 10);

graph->DrawLine(blackPen, n + value_of_width - 10, m + 10,

n + 10,

m + value_of_height - 10);

Rectangle rect = Rectangle(n, m, value_of_width, value_of_height);

graph->DrawRectangle(gcnew Pen(Color::Black, 2.0f), rect);

}

else

{

// нарисовать O

graph->DrawEllipse(blackPen, n + 10, m + 10, value_of_width - 22, value_of_height - 22);

Rectangle rect = Rectangle(n, m, value_of_width, value_of_height);

graph->DrawRectangle(gcnew Pen(Color::Black, 2.0f), rect);

}

}

}

}

else // обратнаядиагональ

{

for (int i = 0, n = n_begin + game_logic->x_begin * value_of_width; i < 3; i++, n = n - value_of_width)

for (int j = 0, m = m_begin + game_logic->y_begin*value_of_height; j < 3; j++, m = m + value_of_height)

{

if (i == j)

{

graph->FillRectangle(gcnew SolidBrush(Color::Yellow), n, m,

value_of_width - 1, value_of_height - 1);

if (field[game_logic->x_begin, game_logic->y_begin] == 1)

{

// нарисовать X

graph->DrawLine(blackPen, n + 10, m + 10,

n + value_of_width - 10,

m + value_of_height - 10);

graph->DrawLine(blackPen, n + value_of_width - 10, m + 10,

n + 10,

m + value_of_height - 10);

Rectangle rect = Rectangle(n, m, value_of_width, value_of_height);

graph->DrawRectangle(gcnew Pen(Color::Black, 2.0f), rect);

}

else

{

// нарисовать O

graph->DrawEllipse(blackPen, n + 10, m + 10, value_of_width - 22, value_of_height - 22);

Rectangle rect = Rectangle(n, m, value_of_width, value_of_height);

graph->DrawRectangle(gcnew Pen(Color::Black, 2.0f), rect);

}

}

}

}

}

if (how_win == 3) // погоризонтали

{

Int32 m = m_begin + game_logic->y_begin * value_of_height;

for (Int32 i = game_logic->x_begin, n = n_begin + game_logic->x_begin * value_of_width; i < game_logic->x_begin + 3; i++, n = n + value_of_width)

{

Fill_elem(n, m);

}

}

}

bg->Render();

}

catch (InvalidOperationException^ ex) {}

}

Void Field::Draw_elem(Int32 x, Int32 y)

{

value_of_width = (graph->VisibleClipBounds.Width / count_cells);

value_of_height = (graph->VisibleClipBounds.Height / count_cells);

Int32 min_i = (graph->VisibleClipBounds.Width - value_of_width*count_cells) / 2;

Int32 min_j = (graph->VisibleClipBounds.Height - value_of_height*count_cells) / 2;

if (x < min_i || y < min_j || x > min_i + value_of_width*count_cells ||

y > min_j + value_of_height*count_cells) return;

Int32 i = 0, j = 0;

while (x >= min_i + value_of_width)

{

i++;

min_i += value_of_width;

}

while (y >= min_j + value_of_height)

{

j++;

min_j += value_of_height;

}

if (field[i, j] != 0) return;

field[i, j] = 1;

Draw_field();

t->Sleep(150);

Bot^ bot = gcnew Bot(field);

bot->Start();

/*if (first_gamer)

{

field[i, j] = 1;

first_gamer = false;

}

else

{

field[i, j] = 2;

first_gamer = true;

}*/

Draw_field();

}

Void Field::Run()

{

if (t && t->IsAlive)

{

t->Abort();

}

else

{

ts = gcnew ThreadStart(this, &Field::Start);

t = gcnew Thread(ts);

t->Start();

}

}

Void Field::Replay()

{

if (field) delete[] field;

field = gcnew array<Int16, 2>(Convert::ToInt32(count_cells),

Convert::ToInt32(count_cells));

first_gamer = true;

is_win = false;

Draw_field();

}

Задача о расстановке ферзей

#include<vcl.h>

#pragma hdrstop

#include "Unit1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

typedefstructLogRecord

{

int * b; //расстановка

String* Comment; //Текстовоеописание

int ** board; //Копия "угроз"

} LogRecord;

int * B=NULL; //Рабочаядоска

LogRecord * Log = NULL; //Журнал

intLogLen = 0; //Длина журнала

int ** Board = NULL; //Доска с угрозами

int N = 5; //Размердоски

int Index = 0;

// Функции работы с журналом операций

voidSaveToLog(StringComment)

{

Log = (LogRecord*)realloc(Log, sizeof(LogRecord)*(LogLen+1));

Log[LogLen].b = new int[N];

for (int n=0; n<N; n++) Log[LogLen].b[n] = B[n];//Запомнитьдоску

Log[LogLen].Comment = new String(Comment);

Log[LogLen].board = new int*[N];

for (int r=0; r < N; r++) {

Log[LogLen].board[r] = new int[N];

for ( int c=0; c < N; c++) Log[LogLen].board[r][c] = Board[r][c];

}

LogLen++;

}

String RestoreFromLog(int index)

{

if (index<0) return "";

if (index>=LogLen) return "";

for (int n=0; n<N; n++) B[n] = Log[index].b[n];//Восстановитьдоску

for (int r=0; r < N; r++) {

for (int c=0; c < N; c++) Board[r][c] = Log[index].board[r][c];

}

return *(Log[index].Comment);

}

//Функцииотображения

void __fastcall TForm1::ShowLog(int index)

//Показатьзаписьжурнала index

{

LabelDescription->Caption = RestoreFromLog(index);

paintBoard->Repaint();

LabelIndex->Caption = IntToStr(Index+1)+"/"+IntToStr(LogLen);

}

//---------------------------------------------------------------------------

void __fastcall TForm1::paintBoardPaint(TObject *Sender)

//Обновление изображения доски

{

//Очистить

int W = paintBoard->Width - 10; //Общая ширина

int H = paintBoard->Height - 10;

int W8 = W / N; //Ширинаодногостолбца

int H8 = H / N;

W = W8 * N; //Скорректированная общая ширина

H = H8 * N;

paintBoard->Canvas->Brush->Color = clYellow;

TRectRect;

//Нарисоватьклеточки

paintBoard->Canvas->Pen->Color = clBlack;

for (int r=0; r < N; r++)

for (int c=0; c < N; c++)

{

Rect.Left = c * W8+1;

Rect.Right = Rect.Left + W8 - 2;

Rect.Top = H - H8 - r * H8 +1;

Rect.Bottom =Rect.Top + H8 -2;

if ((r+c) % 2 == 1) //Еслинужно

paintBoard->Canvas->Brush->Color = clLtGray;

else

paintBoard->Canvas->Brush->Color = clYellow;

paintBoard->Canvas->Rectangle(Rect.Left-1,Rect.Top-1,Rect.Right+2,Rect.Bottom+2);

}

//Нарисоватьбуквы

paintBoard->Canvas->Brush->Color = clWhite;

for (int c=0; c < N; c++)

paintBoard->Canvas->TextOutA(c*W8+W8/2-3,H+2,char('A'+c));

//Нарисоватьцифры

for (int r=0; r < N; r++)

paintBoard->Canvas->TextOutA(W+4,H-H8 - r*H8 + 3,IntToStr(r+1));

//Нарисовать "угрозы"

paintBoard->Canvas->Brush->Color = clRed;

for (int r=0; r < N; r++)

for (int c=0; c < N; c++)

if (Board[r][c]!=0) {

int x = W8 * c + W8/2;

int y = H-H8-H8*r+H8/2;

paintBoard->Canvas->Ellipse(x-2,y-2,x+2,y+2);

}

//расставитьферзей (красныекруги)

paintBoard->Canvas->Brush->Color = clRed;

for (int n = 0; n < N; n++)

if (B[n]>=0)

{

int x = W8 * n;

int y = H-H8-H8*B[n];

paintBoard->Canvas->Ellipse(x,y,x+W8,y+H8);

}

}

//Решениезадачиоферзях.

voidModifyBoard(intRow,int Column, int d)

//Изменить счетчики угроз на остатке доски

{

intup = Row + 1; //Диагональ "вверх"

intdown = Row - 1; //Диагональ "вниз"

for (intс=Column+1; с<N; с++) {

if (up>=0 && up<N) Board[up][с]+=d;

if (down>=0 && down<N)Board[down][с]+=d;

Board[Row][с]+=d;

up++;

down--;

}

}

voidPutQueen(intRow,int Column)

{

ModifyBoard(Row,Column,1); //Увеличитьсчетчикиугроз

B[Column] = Row; //Установитьферзя (дляиндикации)

String S ="Установленна ";

S+=(char)('A'+Column);

S+=IntToStr(Row+1);

SaveToLog(S);

}

voidGetQueen(intRow,int Column)

{

ModifyBoard(Row,Column,-1); //Уменьшитьсчетчикиугроз

B[Column] = -1; //Снятьферзя

String S ="Снятс ";

S+=(char)('A'+Column);

S+=IntToStr(Row+1);

SaveToLog(S);

}

voidrSolve(int Column)

{

//Попытаться поставить ферзя в столбец Column

//Если Column == N, то цель достигнута!

if (Column == N) {

SaveToLog("Расстановка найдена");

return;

}

//Если цель не достигнута, перебрать все возможные варианты

for (int r=0; r < N; r++) { //Для всех горизонталей

if (Board[r][Column]==0) { //Если есть возможность поставить ферзя

PutQueen(r,Column);

rSolve(Column+1);

GetQueen(r,Column);

}

}

}

voiddeleteLog()

{

for (int n = 0; n <LogLen; n++) {

delete Log[n].Comment;

delete Log[n].b;

for (int r=0; r < N; r++) delete Log[n].board[r];

delete Log[n].board;

}

if (Log) delete Log;

Log = NULL;

LogLen = 0;

Index=-1;

}

voiddeleteBoard()

{

for ( int r=0; r < N; r++)

delete Board[r];

delete Board;

}

void Solve()

{

//Пересоздать

if (Log) deleteLog();

N = Form1->ComboBoxN->ItemIndex+1;

delete B; B = new int[N];

Index=0;

//Очиститьдоску

for (int n=0; n < N; n++) B[n] = -1;

//Подготовить вспомогательную

if (Board) deleteBoard;

Board = new int *[N];

for (int r=0; r < N; r++)

{

Board[r] = new int[N];

for (int c=0; c < N; c++)

Board[r][c]=0; //Нет угрозы

}

rSolve(0);

SaveToLog("Готово");

}

//---------------------------------------------------------------------------

void __fastcall TForm1::FormCreate(TObject *Sender)

{

Solve();

ShowLog(Index);

}

//---------------------------------------------------------------------------

void __fastcall TForm1::SpeedButtonFirstClick(TObject *Sender)

{

Index = 0;

ShowLog(Index);

}

//---------------------------------------------------------------------------

void __fastcall TForm1::SpeedButtonLastClick(TObject *Sender)

{

Index = LogLen-1;

ShowLog(Index);

}

//---------------------------------------------------------------------------

void __fastcall TForm1::SpeedButtonPrevClick(TObject *Sender)

{

Index--;

if (Index<0) Index = 0;

ShowLog(Index);

}

//---------------------------------------------------------------------------

void __fastcall TForm1::SpeedButtonNextClick(TObject *Sender)

{

Index++;

if (Index>=LogLen) Index = LogLen-1;

ShowLog(Index);

}

//---------------------------------------------------------------------------

void __fastcall TForm1::ComboBoxNChange(TObject *Sender)

{

Solve();

ShowLog(Index);

}

//---------------------------------------------------------------------------

//Воспроизведение

void __fastcall TForm1::BitBtnPlayClick(TObject *Sender)

{

Timer1->Enabled = true;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::BitBtnStopClick(TObject *Sender)

{

Timer1->Enabled = false;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::ComboBox1Change(TObject *Sender)

{

Timer1->Interval = 250 + ComboBox1->ItemIndex * 250;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Timer1Timer(TObject *Sender)

{

SpeedButtonNextClick(Sender);

if (Index>=LogLen-1) BitBtnStopClick(Sender);

}

//---------------------------------------------------------------------------

void __fastcall TForm1::SpeedButton1Click(TObject *Sender)

{

String S = IntToStr(Index+1);

if (!InputQuery("Позиция","",S)) return;

try

{

Index = StrToInt(S)-1;

}

catch (...)

{

return;

}

if (Index<0) Index=0;

if (Index>=LogLen) Index=LogLen-1;

ShowLog(Index);

}

//---------------------------------------------------------------------------

Пятнашки

Sceleton_DIALOG.cpp

#include "stdafx.h"

#include "Sceleton_DIALOG.h"

#define MAX_LOADSTRING 100

// Global Variables:

HINSTANCE hInst;// current instance

TCHAR szTitle[MAX_LOADSTRING];// The title bar text

TCHAR szWindowClass[MAX_LOADSTRING];// the main window class name

// Forward declarations of functions included in this code module:

//ATOMMyRegisterClass(HINSTANCE hInstance);

//BOOLInitInstance(HINSTANCE, int);

//LRESULT CALLBACKWndProc(HWND, UINT, WPARAM, LPARAM);

//INT_PTR CALLBACKAbout(HWND, UINT, WPARAM, LPARAM);

INT_PTR CALLBACKDFunc(HWND, UINT, WPARAM, LPARAM);

static HWND hBut[16],hBt; //массивкнопок

static int mas[16]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0}; //массивчисел 0-15 (приотладкеудобнозаполнять)

static int n_block[16];//массив блокированных элементов

static int map_15[16]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,};//массив собранных и блокированных элементов

static int close_list[16];//массив закрытых при трассировке элементов

static int mass_a[4];//массив окружения элемента [0]=слева,[1]=справа,[2]=сверху,[3]=снизу (если рядом нет ячеек или блокированы, то содержит -1, если есть то номер ячейки)

int Min_F =100;//минимальная стоимость маршрута F

...