Математична модель популяції мурах дозволила знайти вирішення найдавнішої шахової задачі
Приберіть всі фігури з шахівниці, залишивши лише одного коня. Після цього постарайтеся зробити цим конем послідовність ходів таким чином, щоб кінь побував у кожному з 64 квадратів шахової дошки тільки один раз. Нагадаємо, що в шаховий кінь робить хід досить хитрим чином, він ходить на дві клітини в одному з напрямків, і на одну клітину в напрямку, перпендикулярному до попереднього. Це так звана задача ходу конем і її досить складно вирішити навіть досвідченому шахісту. Вчені-математики підрахували, що кількість рішень цієї задачі приголомшливо велика. Якщо кінь закінчує свій тур в тій же клітині, з якої він починав рух, це називається замкнутим маршрутом і число таких рішень становить більше 26 трильйонів. Але якщо кінь, пройшовши через всі 64 клітини, не повертається у вихідну точку, це називається незамкнутим маршрутом, і кількість таких маршрутів не піддається обчисленню, настільки воно велике.
Рішення завдання ходу конем було досить популярним заняттям для вчених-математиків протягом багатьох століть. А нещодавно група програмістів і математиків з університету Ноттінгема (University of Nottingham) застосувала для пошуку розв'язків задачі абсолютно нетрадиційних для цього метод. Вони створили в надрах комп'ютера оптимізовану під завдання математичну модель, що описує поведінку колонії мурах, окремі особини яких чудово справляються зі знаходженням оптимального шляху між мурашником і джерелом їжі.
"Наша комп'ютерна модель в точності моделює поведінку популяції мурах. Але в нашому випадку завданням для мурашок є не пошуки їжі та доставка її в мурашник, наші віртуальні мурахи запрограмовані на пошуки розв'язання задачі ходу конем" - розповідає Грем Кендол (Graham Kendall), один з провідних програмістів, - "Віртуальні мурашки діють також, кік і їх живі побратими, при русі вони залишають за собою слід з гостро пахнуть сполук, феромонів. Кожен віртуальний мураха мітить свій шлях по шахівниці дозою ферромона, і за сумарною кількістю виділеного ферромона можна судити про успішність вирішення завдання будь-якої окремо взятої особиною".
Звичайно, математичної моделі колонії мурах також потрібно досить велика кількість часу та обчислювальних ресурсів для того, щоб знайти рішення задачі. А найбільша кількість обчислювальних ресурсів "пожирає" пошук відповідного шляхи для наступного ходу. І в результаті переміщень колонії віртуальних мурашок по віртуальній дошці на її поверхні залишаються прокладені мурахами доріжки з феромонів. Найбільша концентрація феромонів спостерігається на ділянках шляхів, по яких мурашки пройшли більшу кількість разів і які ведуть до правильного вирішення поставленого завдання.
Завдяки такому інноваційному методу, Грему Кендолу і його колегам вдалося знайти більше 500 тисяч рішень задачі ходу конем за прийнятний для цього час. Звичайно, цю задачу можна вирішувати і більш прямим методом, методом "грубої сили", методом звичайного перебору. Але в цьому випадку на пошук варіантів рішень потрібно ще більше часу і кількість обчислювальних ресурсів, адже складність завдання ходу конем з цієї точки зору не поступається складності відомої задачі мандрівного комівояжера.