Лабораторная работа 1 Методы поиска в пространстве состояний: изучение методов перебора и критериев оценки методов перебора на произвольных графах



Скачать 50.04 Kb.
Дата15.01.2013
Размер50.04 Kb.
ТипЗадача

ЛАБОРАТОРНАЯ РАБОТА 1

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

  1. Цель.



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

  1. Задание на лабораторную работу


Для вариантов задач из таблицы 1 оценить качество работы нижеперечисленных методов перебора по критерию целенаправленности.

Методы перебора для оценки :

  • метод полного перебора;

  • метод равных цен;

  • метод перебора в глубину;

  • оптимальный алгоритм перебора A*.

Требования к реализации программы оценки :

  • все методы должны быть применимы для перебора на произвольных графах, а не только на деревьях;

  • графическое отображение дерева перебора.

Таблица 1.

Вариант

Задание

1

Игра в восемь.

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


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

2

Задача о коммивояжере.

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

3

Задача о двух кувшинах.

Дан кувшин с водой емкостью N и пустой кувшин емкостью M. Требуется получить заданную емкость L. Воду можно либо выливать, либо переливать из одного кувшина в другой. (Kувшины можно полностью наполнять водой из неогpаниченного pезеpвуаpа).

4

Задача о рюкзаке.

Дана упорядоченная по неубыванию последовательность целых положительных чисел. Каждое число может быть ассоциировано с объемом некоторого предмета, который турист может взять с собой в поход. Дано также целое положительное число, которое может быть ассоциировано с объемом рюкзака.
Требуется : найти все подпоследовательности исходной последовательности, сумма элементов которых в точности равна этому числу (определить совокупности тех предметов, которые войдут в рюкзак при полном его заполнении).

5

Задача о миссионерах и каннибалах.

Три миссионера и три каннибала находятся на левом берегу реки. Все хотят перебраться на другой берег. Здесь же небольшая лодка, вмещающая не более двух человек. Если на каком-то берегу каннибалов окажется больше, чем миссионеров, то они съедят миссионеров. Если окажется больше миссионеров, то они обратят каннибалов в свою веру. Требуется найти последовательность перемещений лодки с одного берега на другой, гарантирующую безопасность миссионерам и свободу вероисповедания каннибалам.

6

Задача про банкет.

Имеется круглый стол, за который могут сесть максимум N человек. Требуется разместить N человек за этим столом таким образом, чтобы по обе стороны от каждого сидели его знакомые1.

7

Задача об N ферзях.

Разместить N ферзей на шахматной доске NN так, чтобы на каждой горизонтали, вертикали и диагонали стояло не более одного ферзя.

8

Задача о шахматном коне (задача Эйлера).

Требуется обойти все клетки шахматной доски ходом коня.

9

Путь коня.

На шахматной доске NN, несколько клеток из которой вырезано, заданы две клетки. Построить минимальный путь коня из одной клетки в другую.

10

Задача “Ханойская башня”.

Имеется три стержня, на первом из которых помещены N дисков разного диаметра, причем меньший диск обязательно лежит на большем. Требуется переместить все диски на третий стержень, двигая их по очереди. Ход в этой головоломке состоит в снятии верхнего диска с одного из стержней и перемещении его поверх дисков (если они есть) другого стержня. Ограничение состоит в том, что больший диск нельзя класть на меньший.

11

Задача о трех монетах.

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



  1. Содержание отчета.



Отчет должен быть оформлен в соответствии с СТП 1.302-96 (файл gost.!!!);

  • раздел отчета "Объект исследования" обязательно должен содержать следующие пункты :

  1. Описание представления в пространстве состояний (указать форму описания состояний, операторов, критериев достижения цели).

  2. Представление пространства состояний в виде графа.

  3. Описание оценочной функции.

    • раздел "Результаты исследования" должен содержать результаты оценки качества работы рассмотренных методов, здесь обязательно приводятся используемые в работе наборы тестовых данных.



Список литературы.


  1. Системы искусственного интеллекта : курс лекций для специальности 220400 - Программное обеспечение вычислительной техники и автоматизированных систем. Лекции 2, 3. - Великий Новгород, НовГУ, 2005

  2. Нильсон Н. Искусственный интеллект : Пер. с англ. – М.: Мир, 1973

  3. Слэйгл Дж. Искусственный интеллект : Пер. с англ. – М.: Мир, 1973

  4. Гарднер М. Математические головоломки и развлечения : Пер. с англ. – М.: Мир, 1971

  5. Берж К. Теория графов и ее применения : Пер. с фр. - М.: Издательство иностранной литературы, 1962

  6. Харари Ф. Теория графов : Пер. с англ. - М.: Мир, 1973.

  7. Дискретная математика : алгоритмы. Гамильтоновы графы. // http://rain.ifmo.ru/cat/view.php/theory/graph-circuits-cuts/hamiltonian-2005

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

Похожие:

Лабораторная работа 1 Методы поиска в пространстве состояний: изучение методов перебора и критериев оценки методов перебора на произвольных графах iconРабота №1 «методы одномерной оптимизации» Дисциплина «Методы оптимизации»
...
Лабораторная работа 1 Методы поиска в пространстве состояний: изучение методов перебора и критериев оценки методов перебора на произвольных графах iconЛабораторная работа. Изучение методов компьютерной томографии
Классификация методов вычислительной томографии
Лабораторная работа 1 Методы поиска в пространстве состояний: изучение методов перебора и критериев оценки методов перебора на произвольных графах iconЛабораторная работа №1 изучение магнитного поля плоской катушки
Ознакомление с одним из методов получения магнитного поля в пространстве при помощи плоской катушки с током. Изучение явления взаимной...
Лабораторная работа 1 Методы поиска в пространстве состояний: изучение методов перебора и критериев оценки методов перебора на произвольных графах iconТеория систем, системный анализ, кибернетика
Теория принятия решений представляет собой совокупность математических и численных методов, ориентированных на нахождение наилучших...
Лабораторная работа 1 Методы поиска в пространстве состояний: изучение методов перебора и критериев оценки методов перебора на произвольных графах iconЗанятие №2 по дисциплине «Интеллектуальные системы»
Тема. Методы представления задач и эвристического поиска в пространстве состояний
Лабораторная работа 1 Методы поиска в пространстве состояний: изучение методов перебора и критериев оценки методов перебора на произвольных графах iconОсновное содержание учебной дисциплины
Прямая и обратная задачи методов. Спектроскопические методы исследования. Дифракционные методы. Оптические и другие методы. Характеристическое...
Лабораторная работа 1 Методы поиска в пространстве состояний: изучение методов перебора и критериев оценки методов перебора на произвольных графах iconПрограмма по специальности «Основы аналитической химии» для подготовки специалистов по дистанционной технологии
Классификация методов аналитической химии, особенности методов различных групп. Методы определения; цели, преследуемые при создании...
Лабораторная работа 1 Методы поиска в пространстве состояний: изучение методов перебора и критериев оценки методов перебора на произвольных графах iconПримерная рабочая программа по курсу «методы оптимизации»
Цель дисциплины – изучение основных категорий и методов оптимизации как современного научного направления, возможностей и особенностей...
Лабораторная работа 1 Методы поиска в пространстве состояний: изучение методов перебора и критериев оценки методов перебора на произвольных графах iconИсследовательская работа «Применение метода спуска и перебора в решении диофантовых уравнений»

Лабораторная работа 1 Методы поиска в пространстве состояний: изучение методов перебора и критериев оценки методов перебора на произвольных графах iconЛабораторная работа №3 «Исследование измерителей параметров движения летательного аппарата вокруг центра масс» по дисциплине «Системы управления транспортных средств»
Изучение методов численного интегрирования и дифференцирования непрерывных функций
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org