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

00:46
Инаугурационная речь 45-го Президента США Дональда Трампа
00:44
Страх и ненависть в Давосе. Чего боится глобальная элита?
00:26
Сорос испугался будущего с Трампом
00:24
Это вам не «кровавый Янукович». «Русские» силовики Авакова растоптали стадо активистов в центре Киева
00:22
Инаугурация 45-го президента США Дональда Трампа
00:21
Киев приравнял активистов Майдана к участникам боевых действий
00:20
Порошенко в своем Twitter поздравил Трампа с инаугурацией
00:19
Шойгу доложили о начале строительства первого самолета Ту-160М2
00:14
Во Львове активисты изгоняли мусор пением гимна Украины и криками «Ганьба!»
00:13
Президент USR поблагодарил жителей мира
00:12
Украинские власти и британская модель экспорта демократии
00:02
Украинские инженеры попытались сделать аналог «Искандера»
17:06
Песков «как гражданин» выразил надежду на участие Путина в выборах в 2018 году
17:06
Ще не вмерла Украина, или Как пожарных собирают среди волонтёров
17:05
Надвигающийся трампец и ужаснувшиеся мыши
17:04
Обама адресовал свой последний звонок Меркель
17:04
Головной офис «Рошен» подтвердил закрытие фабрики в Липецке
17:03
Прощай Обама...
16:50
Строительство трассы «Таврида» к Керченскому мосту начнется в феврале
16:50
СК РФ начал доследственную проверку в отношении Шендеровича
16:48
Пожалейте Украину: который век над ней издевается Россия
16:47
Россия сегодня разрабатывает многоразовую ракету
16:46
Лукашенко потребовал от правительства найти замену российской нефти
16:44
Марин Ле Пен бросила вызов ЕС
12:42
2020: Литва без штанов, но с автоматом
10:42
Воскресить «большую восьмерку» не удастся никому
10:41
Балога высмеял кадрового дипломата Порошенко: После китайцев молить о помощи останется только марсиан
10:37
Российские порты вышли на рекорд
10:37
Украинская методичка для американского майдана
10:34
Возрождение легенды: зачем Россия воссоздала 150-ю Идрицко-Берлинскую дивизию
10:34
Давос-2017 как символ завершения эпохи глобализации
10:33
Майкл Мур и Роберт Де Ниро возглавили митинг против Трампа в Нью-Йорке
10:32
У разбитой бензоколонки
10:30
Тем временем: Третью годовщину начала столкновений на Грушевского майданщики отметили дракой с полицией
10:30
имошенко, Билозир, Бляхер, Ковальчук и Левочкин поехали поклониться Трампу
10:29
Чубайс рассказал об ужасе в Давосе из-за избрания Трампа
09:16
Берлин должен показать Трампу характер
09:13
Экипажи кораблей Тихоокеанского флота готовятся к выходам в море
09:08
Русские хотят быть скандинавами
09:04
Новый Шёлковый путь буксует на Транссибе
09:02
Что если за скандалом с прослушками стояли россияне?
08:54
Порошенко собрался к Трампу «за большим удовольствием»
08:51
Россия уже побеждает
08:48
Украинскую оборонку поразил «Гром»
08:46
Мы никогда не были Северной Америкой
Все новости

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

«    Январь 2017    »
ПнВтСрЧтПтСбВс
 1
2345678
9101112131415
16171819202122
23242526272829
3031 
» » Математическая модель популяции муравьев позволила найти решения древнейшей шахматной задачи

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

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

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

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

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

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

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




Источник





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

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


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

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


Loading...

Loading...

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