Лента новостей

02:46
Роберт Фицо: тот, на ком свет клином сошёлся?
02:34
Польша опасается нелегального оружия с Украины
00:40
Обзор ASUS Zenbook 14 OLED (UX3405): ноутбук «всего» с одним дисплеем — зато каким!
00:39
Китай испытал рельсотрон для запуска снарядов в стратосферу, но что-то пошло не так
00:33
Украинские страсти по Белоусову
22:20
Портативные электростанции Duracell, которые выглядят как гигантские щелочные батареи
21:47
Юрай Цинтула, стрелявший в Роберта Фицо, будет находиться под стражей
21:41
Гастроли Елены Зеленской в Белграде: нелепый пиар Киева и сербская многовекторность
21:29
Гастроли Елена Зеленской в Белграде: нелепый пиар Киева и сербская многовекторность
20:38
«Комчас с 23:00, а в 19:00 уже ни одного автобуса». Администрации Донецка мешает комендантский час для налаживания нормальной работы общественного транспорта
20:37
Президент Грузии заветировала законопроект об иноагентах
20:29
США поссорились с WADA из-за китайского допинга
20:26
Молодежи Донбасса презентовали четвертый сезон «ТопБЛОГ»
19:28
ВСУ ведут обстрелы ЛНР, ДНР, Белгородской и Курской области. Обзор ситуации в прифронтовых регионах России на вечер 18 мая
18:47
На Украине завели дело на мужчину, ранившего ножом военкома
18:13
Президент Грузии Зурабишвили наложила вето на законопроект об иноагентах
17:46
Европейский центробанк призвал банки из Евросоюза покинуть Россию
17:45
На Украине дальнобойщики заблокировали трассу Киев–Одесса, протестуя против закона Байдена-Зеленского о мобилизации
17:44
Глава ДНР заявил о выделении 150 участков под коммерческое строительство. Местные жители, ставшие бомжами, возмущены решениями властей
17:43
Вассерман призвал ликвидировать режим Зеленского, как террористическую организацию
17:04
Россия и Китай укрепляют дружбу, преодолевая проблемы, созданные Западом
17:01
Над Рейхстагом 9 мая пролетел беспилотник с российским флагом
16:27
Во Франции призвали отменить антироссийские санкции
16:00
В Киргизии сообщили о 29 пострадавших в результате ночных событий в центре Бишкека
15:59
«Планируете да планируете. На ДМЗ без слёз смотреть нельзя». Пушилин рассказал о массовом запуске предприятий в ДНР
15:51
Подозреваемый в покушении на премьера Словакии Фицо признал вину
15:50
На Украине заочно предъявили обвинение главам ФСБ и Росгвардии
15:23
Протоиерей Ткачёв считает, что белгородцы недостаточно молятся – надо с утра до вечера, тогда обстрелов не будет
15:22
Зеленский пожаловался на нехватку 75% средств ПВО
15:16
Между Китаем и США: Ангола вновь меняет вектор
15:13
Украинские дальнобойщики устроили протест против насильственной мобилизации
14:46
ВСУ обстреляли Херсонскую область. Есть пострадавшие
14:12
Киевский режим ожидает прорывов российской армии на разных участках фронта
14:03
Правительство утвердило план празднования 80-летия Великой Победы
13:37
WSJ: Украина попросила США указать цели в России для поражения
13:36
Депутат Бурляев призвал преподавать детям в школах уроки целомудрия
13:35
Жителям Украины запретили перемещать и продавать свои автомобили, которые будут стоять на учёте в военкомате
13:29
Страсти на бывшей Украине: «Иудейская война»
13:27
Сравнение российских вооруженных сил и армий НАТО в апокалиптическом сценарии третьей мировой войны
12:43
Специальная военная операция ВС РФ и события на Украине 18 мая, день
12:25
Зеленский: Запад боится, что Россия проиграет войну
12:19
Прибалтийский генералитет витает в параллельной реальности
12:17
Арктические терминалы и ледоколы, нагруженные газом. Европа планирует небывалый удар по России
12:15
Зеленский отклонил предложение Макрона об олимпийском перемирии
11:48
«Украина превращается в полный концлагерь». Начал действовать закон о мобилизации, ограничивающий украинцев в правах
Все новости

Архив публикаций



Мировое обозрение»Технологии»Математическая модель популяции муравьев позволила найти решения древнейшей шахматной задачи

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


Задача хода конем

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

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

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

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

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




Источник


Опубликовано: legioner     Источник

Подпишись:





Напишите ваш комментарий к статье:

Информация
Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации.

Новости партнеров

Наверх