📄Работа №133789
Тема: Многошаговые игры поиска
Тип работы
Бакалаврская работа
Предмет
информатика
Объем:
45 листов
Год:
2016
Просмотров:
58
4760
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 3
Постановка задачи 5
Глава 1. Теоретико-игровая модель простого поиска 6
1.1. Составление модели 6
1.2. Аналитическое решение случая 2 х 2 8
1.3. Программная реализация случая N х к 12
1.4. Результаты программной реализации 18
Глава 2. Теоретико-игровая модель множественного поиска 23
2.1. Единовременный поиск в двух коробках 23
2.2. Единовременный поиск в m коробках 25
2.3. Программная реализация множественного поиска 27
2.4. Результаты программной реализации 32
Выводы 37
Заключение 38
Список литературы 39
Приложение 40
Постановка задачи 5
Глава 1. Теоретико-игровая модель простого поиска 6
1.1. Составление модели 6
1.2. Аналитическое решение случая 2 х 2 8
1.3. Программная реализация случая N х к 12
1.4. Результаты программной реализации 18
Глава 2. Теоретико-игровая модель множественного поиска 23
2.1. Единовременный поиск в двух коробках 23
2.2. Единовременный поиск в m коробках 25
2.3. Программная реализация множественного поиска 27
2.4. Результаты программной реализации 32
Выводы 37
Заключение 38
Список литературы 39
Приложение 40
📖 Введение
Поиск различных объектов издревле представляет собой одну из ключевых сторон человеческой активности. В работе [1] процесс поиска определяется как целенаправленное обследование конкретной области пространства для обнаружения находящегося там объекта. Обнаружением объекта можно считать получение информации о его местоположении путем
установления с ним прямого энергетического контакта. Это вполне естественная проблема, с которой мы сталкиваемся на ежедневной основе. К
примеру, перед тем как уходить утром на работу, необходимо собрать определенный набор вещей (ключи, кошелек, документы), которые в свою очередь необходимо локализовать. Их местоположение многообразно, и есть
потребность свести количество времени, затраченное на поиск, к минимуму. Отходя от подобных бытовых проблем, можно расширить список задач
до локализации поврежденных файлов компьютера, разведки месторождений нефти или поиска заблудившегося в лесу человека.
Одним из путей исследования поиска является построение и анализ
математических моделей, отображающих объективные закономерности поиска и позволяющие установить связь между условиями его выполнения и
его результатами, с целью дальнейшего анализа критериев эффективности
поиска. Конечной целью теории поиска является установление оптимального способа ведения поисковых действий применительно к определенной
обстановке и условиям проведения поиска. Выбор оптимального способа
поиска основан на анализе математической модели, соответствующей поисковой ситуации, что позволяет локализовать объект поисков с минимальными затратами имеющихся ресурсов, ввиду их частой ограниченности.
В 1957 году в свет вышла работа Б. О. Купмана [7], в которой задачи поиска рассматривались как задачи оптимального распределения ре-
3сурсов, направленных на поиск, т.е. односторонние задачи оптимизации.
С момента выхода этой работы теория поиска получила широкое распространение, в результате чего появилось большое число публикаций, и стало
общепринятым проводить разделение задач поиска на два класса: поиск
неподвижного и поиск подвижного объектов. Также объект поиска может
рассматриваться как пассивный (не оказывает сопротивления собственному обнаружению) и активный (оказывает сопротивление). Полное и систематическое изложение теории решения поисковых задач было приведено
в работах [3, 6]. Проблематика оптимальности поиска затронута также в
работах [4, 8].
В данной работе речь пойдет о многошаговой задаче поиска неподвижного пассивного объекта в дискретной среде, идеей для рассмотрения
которой послужила статья [5]. Многошаговость задачи обусловлена повторяющейся процедурой поиска.
установления с ним прямого энергетического контакта. Это вполне естественная проблема, с которой мы сталкиваемся на ежедневной основе. К
примеру, перед тем как уходить утром на работу, необходимо собрать определенный набор вещей (ключи, кошелек, документы), которые в свою очередь необходимо локализовать. Их местоположение многообразно, и есть
потребность свести количество времени, затраченное на поиск, к минимуму. Отходя от подобных бытовых проблем, можно расширить список задач
до локализации поврежденных файлов компьютера, разведки месторождений нефти или поиска заблудившегося в лесу человека.
Одним из путей исследования поиска является построение и анализ
математических моделей, отображающих объективные закономерности поиска и позволяющие установить связь между условиями его выполнения и
его результатами, с целью дальнейшего анализа критериев эффективности
поиска. Конечной целью теории поиска является установление оптимального способа ведения поисковых действий применительно к определенной
обстановке и условиям проведения поиска. Выбор оптимального способа
поиска основан на анализе математической модели, соответствующей поисковой ситуации, что позволяет локализовать объект поисков с минимальными затратами имеющихся ресурсов, ввиду их частой ограниченности.
В 1957 году в свет вышла работа Б. О. Купмана [7], в которой задачи поиска рассматривались как задачи оптимального распределения ре-
3сурсов, направленных на поиск, т.е. односторонние задачи оптимизации.
С момента выхода этой работы теория поиска получила широкое распространение, в результате чего появилось большое число публикаций, и стало
общепринятым проводить разделение задач поиска на два класса: поиск
неподвижного и поиск подвижного объектов. Также объект поиска может
рассматриваться как пассивный (не оказывает сопротивления собственному обнаружению) и активный (оказывает сопротивление). Полное и систематическое изложение теории решения поисковых задач было приведено
в работах [3, 6]. Проблематика оптимальности поиска затронута также в
работах [4, 8].
В данной работе речь пойдет о многошаговой задаче поиска неподвижного пассивного объекта в дискретной среде, идеей для рассмотрения
которой послужила статья [5]. Многошаговость задачи обусловлена повторяющейся процедурой поиска.
✅ Заключение
В результате проделанной работы была составлена теоретико-игровая
модель многошаговой задачи поиска неподвижного пассивного объекта в
дискретной среде с последующим нормативным анализом поведения игроков на случай двухшагового поиска объекта среди его двух возможных
положений. Была реализована программная реализация данной модели на
случай k-шагового поиска объекта среди N возможных положений. К сожалению, ресурсоемкость алгоритма программной реализации превысила
ожидаемую, в связи с чем решение данной задачи для больших значений k
и N невозможно, что сделало невозможным корректный численный анализ
задач.
Данная теоретико-игровая модель была обобщена на случай одновременной проверки в m возможных положениях объекта за один шаг, после
чего был разработан программный алгоритм, способный решать данную
задачу для значения m = 2. В результате тестирования алгоритма на различных входных данных было обнаружено, что функция затрат игрока S
в данном классе задач может быть ограничена как сверху (снизу). Данные
выводы являются не совсем корректными ввиду отсутствия возможности
проверить их при большом значении шага k, т.к. программный алгоритм
оказался еще более ресурсоемким по сравнению с алгоритмом простого поиска.
В ходе дальнейшей работы планируется произвести оптимизацию работы существующих алгоритмов с целью уменьшить их ресурсоемкость, а
также разработать программный алгоритм на случай одновременной проверки в m возможных положениях для дальнейшего численного анализа
большего класса задач.
3
модель многошаговой задачи поиска неподвижного пассивного объекта в
дискретной среде с последующим нормативным анализом поведения игроков на случай двухшагового поиска объекта среди его двух возможных
положений. Была реализована программная реализация данной модели на
случай k-шагового поиска объекта среди N возможных положений. К сожалению, ресурсоемкость алгоритма программной реализации превысила
ожидаемую, в связи с чем решение данной задачи для больших значений k
и N невозможно, что сделало невозможным корректный численный анализ
задач.
Данная теоретико-игровая модель была обобщена на случай одновременной проверки в m возможных положениях объекта за один шаг, после
чего был разработан программный алгоритм, способный решать данную
задачу для значения m = 2. В результате тестирования алгоритма на различных входных данных было обнаружено, что функция затрат игрока S
в данном классе задач может быть ограничена как сверху (снизу). Данные
выводы являются не совсем корректными ввиду отсутствия возможности
проверить их при большом значении шага k, т.к. программный алгоритм
оказался еще более ресурсоемким по сравнению с алгоритмом простого поиска.
В ходе дальнейшей работы планируется произвести оптимизацию работы существующих алгоритмов с целью уменьшить их ресурсоемкость, а
также разработать программный алгоритм на случай одновременной проверки в m возможных положениях для дальнейшего численного анализа
большего класса задач.
3
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.