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

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

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

Известны подходы к решению этой задачи методами теории графов с обходом всех вершин и учетом накопления веса на вершинах. Группа программистов и математиков из университета Ноттингема (University of Nottingham) применила для поиска решений задачи другой метод. Они создали и реализовали на компьютере математическую модель, описывающую поведение колонии муравьев, отдельные особи которых замечательно справляются с нахождением оптимального пути между муравейником и источником пищи.

"Наша компьютерная модель в точности моделирует поведение популяции муравьев. Но в нашем случае задачей для муравьев являются не поиски пищи и доставка ее в муравейник, наши виртуальные муравьи запрограммированы на поиски решения задачи хода конем" - рассказывает Грэм Кендол (Graham Kendall), один из ведущих программистов, - "Виртуальные муравьи действуют также, как и их живые собратья, при движении они оставляют за собой след из остро пахнущих соединений, ферромонов. Каждый виртуальный муравей метит свой путь по шахматной доске дозой ферромона, и по суммарному количеству выделенного ферромона можно судить об успешности решения задачи любой отдельно взятой особью".

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

Благодаря такому методу, Грэму Кендолу и его коллегам удалось найти более 500 тысяч решений задачи хода конем за приемлемое для этого время.

Источник

Инструменты математического моделирования на сайте Phnet

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

Замечательные инструменты моделирования из разных областей знания в большом количестве имеются на сайте Phet, который принадлежит университету американского штата Колорадо (University of Colorado). Здесь находятся интерактивные демонстрации и модели, которые иллюстрируют различные процессы из области физики, химии, биологии, другим естественным наукам и математики. Преподаватели могут использовать их на занятиях, а учащиеся и студенты - для самостоятельной работы над предметом.

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

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