Решение задачи хода конем было весьма популярным занятием для ученых-математиков в течение многих столетий. Известно, что число решений этой задачи очень велико. Если конь заканчивает свой тур в той же клетке, с которой он начинал движение, это называется замкнутым маршрутом и число таких решений составляет более 26 триллионов. Но если конь, пройдя через все 64 клетки, не возвращается в исходную точку, это называется незамкнутым маршрутом, и количество таких маршрутов не поддается исчислению.
Известны подходы к решению этой задачи методами теории графов с обходом всех вершин и учетом накопления веса на вершинах. Группа программистов и математиков из университета Ноттингема (University of Nottingham) применила для поиска решений задачи другой метод. Они создали и реализовали на компьютере математическую модель, описывающую поведение колонии муравьев, отдельные особи которых замечательно справляются с нахождением оптимального пути между муравейником и источником пищи.
"Наша компьютерная модель в точности моделирует поведение популяции муравьев. Но в нашем случае задачей для муравьев являются не поиски пищи и доставка ее в муравейник, наши виртуальные муравьи запрограммированы на поиски решения задачи хода конем" - рассказывает Грэм Кендол (Graham Kendall), один из ведущих программистов, - "Виртуальные муравьи действуют также, как и их живые собратья, при движении они оставляют за собой след из остро пахнущих соединений, ферромонов. Каждый виртуальный муравей метит свой путь по шахматной доске дозой ферромона, и по суммарному количеству выделенного ферромона можно судить об успешности решения задачи любой отдельно взятой особью".
В результате перемещений колонии виртуальных муравьев по виртуальной шахматной доске на ее поверхности остаются проложенные муравьями дорожки из ферромонов. Наибольшая концентрация ферромонов наблюдается на участках путей, по которым муравьи прошли большее количество раз и которые ведут к правильному решению поставленной задачи.
Благодаря такому методу, Грэму Кендолу и его коллегам удалось найти более 500 тысяч решений задачи хода конем за приемлемое для этого время.
Известны подходы к решению этой задачи методами теории графов с обходом всех вершин и учетом накопления веса на вершинах. Группа программистов и математиков из университета Ноттингема (University of Nottingham) применила для поиска решений задачи другой метод. Они создали и реализовали на компьютере математическую модель, описывающую поведение колонии муравьев, отдельные особи которых замечательно справляются с нахождением оптимального пути между муравейником и источником пищи.
"Наша компьютерная модель в точности моделирует поведение популяции муравьев. Но в нашем случае задачей для муравьев являются не поиски пищи и доставка ее в муравейник, наши виртуальные муравьи запрограммированы на поиски решения задачи хода конем" - рассказывает Грэм Кендол (Graham Kendall), один из ведущих программистов, - "Виртуальные муравьи действуют также, как и их живые собратья, при движении они оставляют за собой след из остро пахнущих соединений, ферромонов. Каждый виртуальный муравей метит свой путь по шахматной доске дозой ферромона, и по суммарному количеству выделенного ферромона можно судить об успешности решения задачи любой отдельно взятой особью".
В результате перемещений колонии виртуальных муравьев по виртуальной шахматной доске на ее поверхности остаются проложенные муравьями дорожки из ферромонов. Наибольшая концентрация ферромонов наблюдается на участках путей, по которым муравьи прошли большее количество раз и которые ведут к правильному решению поставленной задачи.
Благодаря такому методу, Грэму Кендолу и его коллегам удалось найти более 500 тысяч решений задачи хода конем за приемлемое для этого время.
Комментариев нет:
Отправить комментарий