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

15:05
ВСУ уходят с Донбасса? Кто сегодня взорвёт столицу?
13:03
Global Times: у США не получится расшатать основы дружбы Москвы и Пекина
12:59
CNN: о Чуркине скорбят даже его бывшие оппоненты в ООН
12:55
Сообразить на троих: Бжезинский советует Трампу войти в альянс с Россией и Китаем
12:54
Times: Эстония предупреждает — в драчливости британских военных следует винить Россию
12:53
Трамп, любовь и голуби
12:52
Новая Антанта идёт на войну: Почему Германия создает ЕС-2?
12:52
Первое путинское предупреждение
12:50
Утка по-черногорски: «идите жрать, пожалуйста!»
12:47
Россия не угрожает Швеции
12:44
В Подмосковье на БД заступил 5-й ЗРП, оснащенный новыми ЗРС С-400 «Триумф»
12:37
Россия делает шаг к холодной войне
12:26
Александр Роджерс: Ежегодный Майдан. Эта музыка будет вечной
12:25
Вслед за Сирией - Афганистан
12:24
Су-35 хватают как горячие пирожки
12:13
Человек-эпоха: самые яркие высказывания Виталия Чуркина
12:08
Эффектная работа российского Ми-35 в Сирии попала на видео
12:07
Российские суперсовременные танки пойдут на Ближний Восток
12:07
Силовой «диалог»: чем РФ ответит на усиление НАТО в Черном море
12:04
Возвращение МиГ-27: ударный самолет получит новое сердце
10:58
Турецкая лиса обманула русского медведя
10:52
Воздушная тревога: Россия готовится к внезапному удару НАТО
10:50
Что смерть Виталия Чуркина означает для ООН
10:25
Новейший ледокол «Илья Муромец» войдет в состав ВМФ России осенью текущего года
09:17
Порвут ли республиканцы с Трампом из-за России?
09:12
Депутаты топят Порошенко в компромате
09:10
Острый кризис доверия между Европой и США
09:05
Русские МБР «разорвут в клочья» американскую ПРО
09:01
Уроки русского: в или на Украине?
08:58
Пять ярких моментов из жизни Виталия Чуркина
08:49
Какую пользу санкции против России приносят США?
08:45
Союз с Тегераном опасен для Москвы
08:42
Путин и возвращение великой России
00:00
Этот день в истории - 21 Февраля
22:37
Падение Сингапура: урок на сегодня
22:31
Трампа взяли в заложники
22:29
Новая политика США по отношению к Ирану
22:27
ДНР и ЛНР — уже не Украина
22:24
О сотрудничестве России с США говорить рано
20:52
Помощь России в Сирии: подмога идёт с моря
20:52
Сельскохозяйственный вертолет стал ударным. КТ-112УД на IDEX 2017
20:50
Умер постоянный представитель России при ООН Виталий Чуркин
20:47
Бешеная защита: В Литве полицейским пришлось усмирять солдат НАТО электрошокерами
20:46
Одесское Землячество России спасло жизнь сыну одесского журналиста
20:44
На Украине возник ажиотажный спрос на донецкие паспорта
Все новости

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

«    Февраль 2017    »
ПнВтСрЧтПтСбВс
 12345
6789101112
13141516171819
20212223242526
2728 
» » Математическая модель популяции муравьев позволила найти решения древнейшей шахматной задачи

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

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

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

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

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

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

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




Источник





Опубликовано: legioner    

Похожие публикации


Добавьте комментарий

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


Loading...

Loading...

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