Принимаем муравьев в шахматную школу

Возьмите шахматы, точнее только одну шахматную фигуру — коня. Поставьте его на любую клетку шахматной доски. Сможет вы сделать шестьдесят три хода конем так, чтобы побывать на каждой клетке только единожды? Это задача хоть и трудна, но на счастье имеет очень большое количество решений.

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

Ученый Филип Хингстон занимается проблемой хода коня уже длительное время, обнаружив в природе живой аналог — муравьев.

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

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

Программа прогонялась миллионы раз, при этом запах в правильных решениях «усиливался» а в неправильных — ослабевал.

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

Благодаря данному алгоритму было найдено пятьсот тысяч маршрутов. Этот алгоритм показал более правильные результаты, чем используемый ранее генетический алгоритм. И при этом он имитирует принцип естественного отбора: побеждают сильнейшие.

Почему так произошло непонятно. Наверное муравьи просто полюбили шахматы!

Проблему хода коня впервые попытались решить в девятом веке нашей эры, но ученые того времени и предположить не могли, что их почин подхватят компьютерные муравьи-исследователи.