Исследовательские задачи


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


 Принцесса в темной комнате (разработка стратегии преследования)

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

Формулировка и краткая теория


Составление расписаний учебных занятий

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

Описание идеи


Игра с полной информацией

Игрой с полной информацией называется такая игра, в которой оба противника располагают одинаковой и полной информацией о ходе игры. Примером такой игры являются шахматы. Различие между противниками проявляется только в умении извлекать выгоду из своего знания, но знание это одинаково. Противоположный пример - любая карточная игра, являющаяся по своей природе игрой вероятностной. Программирование игр с полной информации хорошо изученый вопрос. Технология разработки таких программ описана во многих книгах и опирается она на две вещи: во-первых, умение создавать так называемую оценочную функцию и организовывать оптимальный проход дерева перебора ходов. Оценочная функция позволяет оценивать качество позиции, и если бы было возможно для игры составить идеальную функцию оценки, то можно было бы ограничится анализом ситуации после одного хода. К сожалению это невозможно даже для хорошо изученых шахмат. Поэтому приходится просчитывать позицию на несколько ходов вперед. И здесь возникает проблема слишком сильного и слишком быстрого ветвления дерева игры, анализ которого требует больших вычислительных ресурсов. Поэтому создание качественной оценки и оптимального метода обхода есть нерешенная проблема для каждой новой игры. А есть игры настолько сложные, что создать для них хорошо играющую программу до сих пор не удалось. Такова например игра Го. Мы в нашей школе очень уважаем эту задачу и несколько раз решали её для разных игр. Чуть ниже исходники и исполняемые файлы для некоторых из них. Но вообще задача неисчерпаемая, в силу того, что игр с полной информацией очень и очень много.

Исходники шашек Фокус (первая версия) Исходники шашек Фокус (вторая версия) Исполняемый файл шашек Фокус Описание для шашек Фокус

Исходники для игры Халма Исполняемый файл для игры Халма

Исходники для игры Го-бан Исполняемый файл для игры Го-бан Описание для игры Го-бан

Исходники игры Реверси Исполняемый файл для игры Реверси

Исходники игры Сенегальские шашки