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

00:00
Этот день в истории - 28 Апреля
23:48
ISIS однажды извинились за случайное нападение на Израиль
23:46
Пауза «великого кормчего»
23:44
Жебривский заявил о территориальных претензиях на Ростовскую область
23:43
Безвиз. Не для всех, и ненадолго
23:39
Тоголезский скотовоз и секреты Родины
23:36
Владимир Путин и Синдзо Абэ подводят итоги переговоров в Москве
23:33
Латвия, вот твоя реальность: в сто лет на пенсию!
23:31
У НАСА закончились скафандры
23:31
Международные резервы России достигли $400 млрд
23:30
Речь Нарышкина: глава СВР о борьбе за умы, Трампе, Сирии, Корее и киберугрозе НАТО
23:29
Россия и Япония договорились о совместном разведении морских ежей
23:27
Карта «Мир» и финансовый суверенитет
23:25
Киев «атакует» Мариуполь. МВД Украины начало спецоперацию в городе
22:57
Проекту тяжелого военного БПЛА «Альтаир» не хватило денег Минобороны
22:56
Затонувший в Босфоре разведкорабль РФ напичкан сверхсекретным оборудованием
19:43
Воевал против УПА? В тюрьму!
19:36
Helsingin Sanomat: Основная ответственность — на России
19:32
Историческая родина: Керчь ждет своих итальянцев
19:30
Украинская пропаганда проигрывает российской
19:27
Гибель «Лимана»: африканский скотовоз пустили на дно русского разведчика
19:21
Slate.fr: Они будут голосовать за Марин Ле Пен
18:33
США исподтишка готовят ядерный удар по России
18:31
Террорист: Снял Кремль, поел в Маке - пора убивать!
18:30
Сколько ты и я заплатим за свет для ЛНР
18:26
На Украине снова заговорили о введении военного положения
18:26
У Украины даже гипотетически нет возможностей начать строить подлодки
18:25
«Газпром» увеличил требования к «Нафтогазу» до $37 млрд в суде Стокгольма
18:07
Правительство Эстонии имитирует спасение «транзита»
18:06
Киберзащита НАТО: эстонцы отражали атаки вымышленных хакеров
18:05
Москва нашла способ заставить Google признать Крым
18:05
В Польше снесли памятник ОУН-УПА
17:29
Медведев испугался отставки
15:47
Reuters: «Короткое замыкание» в Крыму
15:44
Киев зря торопится топить Марин Ле Пен
15:42
Bloomberg: Российские опросы что-то да значат
15:39
Правило «пяти почему» от системы качества «Тойоты»
15:36
Hlavn? spr?vy: Химическая атака Асада — фейк?
15:32
ПРО США готовит России засаду
15:17
Foreign Policy: Очередная победа трубопроводной политики России
15:12
АТОшники прикидывались инвалидами, чтобы содрать с родины по 200 тысяч гривен
15:11
Кокс признал: Судьбу Украины решают за границей
15:11
Истерика Вятровича: Поляки продались Кремлю и сносят памятники героям УПА
15:10
Польский рокер Балчун и львовские олигархи Дубневичи продают железную дорогу полякам
15:10
Киевляне проклинают «Евровидение»: «Кому нужна эта показуха?»
Все новости

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

«    Апрель 2017    »
ПнВтСрЧтПтСбВс
 12
3456789
10111213141516
17181920212223
24252627282930
» » Математическая модель популяции муравьев позволила найти решения древнейшей шахматной задачи

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

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

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

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

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

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

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




Источник





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

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


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

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


Loading...

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