Задача коммивояжера

Нейросетевая игра в имитацию

Здравствуйте, коллеги. В конце 1960-ых годов прошлого века Ричард Фейнман прочитал в Калтехе курс лекций по общей физике. Фейнман согласился прочитать свой курс ровно один раз. Университет понимал, что лекции станут историческим событием, взялся записывать все лекции и фотографировать все рисунки, которые Фейнман делал на доске. Может быть, именно после этого у университета осталась привычка фотографировать все доски, к которым прикасалась его рука. Фотография справа сделана в год смерти Фейнмана. В верхнем левом углу написано: «What I cannot create, I do not understand«. Это говорили себе не только физики, но и биологи. В 2011 году, Крейгом Вентером был создан первый в мире синтетический живой организм, т.е. ДНК этого организма создана человеком. Организм не очень большой, всего из одной клетки. Помимо всего того, что необходимо для воспроизводства программы жизнедеятельности, в ДНК были закодированы имена создателей, их электропочты, и цитата Ричарда Фейнмана (пусть и с ошибкой, ее кстати позже исправили). Хотите узнать, к чему эта прохладная тут? Приглашаю под кат, коллеги.

Методы решения

Точные методы

Известно два эффективных метода точного решения обобщённой задачи коммивояжёра: Brunch-and-Cut, а также метод приведения обобщённой задачи к обычной задаче коммивояжёра, способы решения которой хорошо изучены.

В 2002 году показано, что обобщённая задача коммивояжера может быть сведена к обыкновенной задаче коммивояжера той же размерности заменой матрицы весов[источник не указан 2013 дней].

К простейшим эвристическим методам решения обобщённой задачи коммивояжёра следует отнести жадный алгоритм, на каждом шаге выбирающий ребро наименьшей стоимости из множества рёбер, не нарушающих корректности решения, а также более эффективный метод ближайшего соседа (Nearest Neighbour), начинающий с произвольной вершины и на каждом шаге добавляющий к решению вершину, наиболее близкую к последней добавленной. Существуют также и другие эвристики, являющиеся модификациями известных эвристик для обычной задачи коммивояжёра.

В частности, часто используются следующие виды локального поиска:

• 2-opt, широко применяемый во многих задачах комбинаторной оптимизации, сводится к удалению двух рёбер из тура и вставке двух новых рёбер, не нарушающих корректности решения (в случае 2-opt вставляемые рёбра определены однозначно). Тур считается локальным минимумом, если в нём не существует ни одной пары рёбер, замена которых привела бы к улучшению решения. Таким образом, и размер окрестности, и сложность эвристики составляют O(m2){\displaystyle O(m^{2})}, где m{\displaystyle m} — это число кластеров.
• 3-opt подобен 2-opt, однако на каждом удаляется не два, а три ребра. В случае 3-opt, для восстановления корректности тура существует восемь нетривиальных способов вставки новых рёбер. Один из этих способов сохраняет направление каждого из фрагментов тура, что является важным свойством для асимметричных задач. Размер окрестности, и сложность эвристики составляют O(m3){\displaystyle O(m^{3})}.
• Существуют естественные модификации 2-opt и 3-opt алгоритмов, дополнительно включающие поиск оптимальных вершин внутри изменяемых кластеров.
• «Insertion» является частным случаем 3-opt. На каждой итерации алгоритм удаляет вершину и пытается найти более выгодную для неё позицию. Сложность алгоритма составляет O(m2){\displaystyle O(m^{2})}. Широко применяется модификация, рассматривающая вставку не только удалённой вершины, но и любой другой вершины соответствующего кластера.
• Кластерная оптимизация — локальный поиск, специфичный для обобщённой задачи коммивояжёра. Суть алгоритма заключается в нахождении кратчайшего пути через заданную последовательность кластеров. Иными словами, окрестность алгоритма включает в себя все туры, отличающиеся от исходного не более чем выбором вершин внутри каждого из кластеров. Размер исследуемой окрестности составляет:

∏i=1m|Ci|,{\displaystyle \prod _{i=1}^{m}|C_{i}|\,,}
где Ci{\displaystyle C_{i}} — это кластер под номером i{\displaystyle i}. Применяя поиск кратчайшего пути в специально построенном графе, алгоритм находит локальный минимум за O(ms3){\displaystyle O(ms^{3})}, где s=maxi|Ci|{\displaystyle s=\max _{i}|C_{i}|}. Таким образом, Cluster Optimization относится к классу локальных поисков с очень большой окрестностью, то есть исследует экспоненциальную окрестность за полиномиальное время.

Метаэвристики

Хорошо исследована область генетических алгоритмов, показавших свою эффективность для данной задачи. Первая работа в этой области принадлежит Снайдеру и Даскину, в дальнейшем важные результаты получены Зильбергольцем и Голденом, Гютеном и Карапетяном.

Когда лучше не использовать глубинное обучение

Перевод

Я понимаю, что странно начинать блог с негатива, но за последние несколько дней поднялась волна дискуссий, которая хорошо соотносится с некоторыми темами, над которыми я думал в последнее время. Всё началось с поста Джеффа Лика в блоге Simply Stats с предостережением об использовании глубинного обучения на малом размере выборки. Он утверждает, что при малом размере выборки (что часто наблюдается в биологии), линейные модели с небольшим количеством параметров работают эффективнее, чем нейросети даже с минимумом слоёв и скрытых блоков.
Далее он показывает, что очень простой линейный предиктор с десятью самыми информативными признаками работает эффективнее простой нейросети в задаче классификации нулей и единиц в наборе данных MNIST, при использовании всего около 80 образцов. Эта статья сподвигла Эндрю Бима написать опровержение, в котором правильно обученная нейросеть сумела превзойти простую линейную модель, даже на очень малом количестве образцов.
Такие споры идут на фоне того, что всё больше и больше исследователей в области биомедицинской информатики применяют глубинное обучение на различных задачах. Оправдан ли ажиотаж, или нам достаточно линейных моделей? Как всегда, здесь нет однозначного ответа. В этой статье я хочу рассмотреть случаи применения машинного обучения, где использование глубоких нейросетей вообще не имеет смысла. А также поговорить о распространённых предрассудках, которые, на мой взгляд, мешают действительно эффективно применять глубинное обучение, особенно у новичков.

Что должен знать о поиске каждый разработчик

• Перевод
• Tutorial

Хотите внедрить или доработать функцию поиска? Вам сюда.

Спросите разработчика: «Как бы вы реализовали функцию поиска в своем продукте?» или «Как создать поисковую систему?». Вероятно, в ответ вы услышите что-нибудь такое: «Ну, мы просто запустим кластер Elasticsearch: с поиском сегодня всё просто».
Но так ли это? Во многих современных продуктах по-прежнему не лучшим образом поиск. Настоящий специалист по поисковым системам скажет вам, что лишь немногие разработчики глубоко понимают, как работает поиск, а ведь это знание часто необходимо для улучшения качества поиска.
Есть множество программных пакетов с открытым исходным кодом, проведено немало исследований, однако лишь немногие избранные понимают, как нужно делать функциональный поиск. Как ни забавно, но если поискать в Интернете связанную с реализацией поиска информацию, вы не найдете актуальных и содержательных обзоров.

Цель статьи

Этот текст можно считать собранием ценных идей и ресурсов, которые могут помочь в создании функции поиска. Статья, безусловно, не претендует на исчерпывающую полноту, однако я надеюсь, что ваши отзывы помогут ее доработать (оставляйте замечания в комментариях или свяжитесь со мной).
Основываясь на опыте работы с универсальными решениями и узкоспециализированными проектами самого разного масштаба (в компаниях Google, Airbnb и нескольких стартапах), я расскажу о некоторых популярных подходах, алгоритмах, методах и инструментах.
Недооценка и непонимание масштабов и сложности задачи поиска могут привести к тому, что у пользователей останутся плохие впечатления, разработчики потратят время впустую, а продукт провалится. Переведено в Alconost

Доступно о криптографии на эллиптических кривых

Перевод

Тем, кто знаком с криптографией с открытым ключом, наверно известны аббревиатуры ECC, ECDH и ECDSA. Первая — это сокращение от Elliptic Curve Cryptography (криптография на эллиптических кривых), остальные — это названия основанных на ней алгоритмов.
Сегодня криптосистемы на эллиптических кривых используются в TLS, PGP и SSH, важнейших технологиях, на которых базируются современный веб и мир ИТ. Я уже не говорю о Bitcoin и других криптовалютах.
До того, как ECC стала популярной, почти все алгоритмы с открытым ключом основывались на RSA, DSA и DH, альтернативных криптосистемах на основе модулярной арифметики. RSA и компания по-прежнему популярны, и часто используются вместе с ECC. Однако несмотря на то, что магия, лежащая в фундаменте RSA и подобных ей алгоритмов легко объяснима и понятна многим, а грубые реализации пишутся довольно просто, основы ECC всё ещё являются для большинства людей загадкой.
В этой серии статей я познакомлю вас с основами мира криптографии на эллиптических кривых. Моя цель — не создание полного и подробного руководства по ECC (в Интернете полно информации по этой теме), а простой обзор ECC и объяснение того, почему её считают безопасной. Я не буду тратить время на долгие математические доказательства или скучные подробности реализации. Также я представлю полезные примеры с визуальными интерактивными инструментами и скриптами.

Наглядное объяснение чисел с плавающей запятой

Перевод

В начале 90-х создание трёхмерного игрового движка означало, что вы заставите машину выполнять почти не свойственные ей задачи. Персональные компьютеры того времени предназначались для запуска текстовых процессоров и электронных таблиц, а не для 3D-вычислений с частотой 70 кадров в секунду. Серьёзным препятствием стало то, что, несмотря на свою мощь, ЦП не имел аппаратного устройства для вычислений с плавающей запятой. У программистов было только АЛУ, перемалывающее целые числа.
При написании книги Game Engine Black Book: Wolfenstein 3D я хотел наглядно показать, насколько велики были проблемы при работе без плавающей запятой. Мои попытки разобраться в числах с плавающей запятой при помощи каноничных статей мозг воспринимал в штыки. Я начал искать другой способ. Что-нибудь, далёкое от и их загадочных экспонент с мантиссами. Может быть, в виде рисунка, потому что их мой мозг воспринимает проще.
В результате я написал эту статью и решил добавить её в книгу. Не буду утверждать, что это моё изобретение, но пока мне не приходилось видеть такого объяснения чисел с плавающей запятой. Надеюсь, статья поможет тем, у кого, как и у меня, аллергия на математические обозначения.

Описание алгоритмов сортировки и сравнение их производительности

Из песочницы

Вступление

На эту тему написано уже немало статей. Однако я еще не видел статьи, в которой сравниваются все основные сортировки на большом числе тестов разного типа и размера. Кроме того, далеко не везде выложены реализации и описание набора тестов. Это приводит к тому, что могут возникнуть сомнения в правильности исследования. Однако цель моей работы состоит не только в том, чтобы определить, какие сортировки работают быстрее всего (в целом это и так известно). В первую очередь мне было интересно исследовать алгоритмы, оптимизировать их, чтобы они работали как можно быстрее. Работая над этим, мне удалось придумать эффективную формулу для сортировки Шелла.
Во многом статья посвящена тому, как написать все алгоритмы и протестировать их. Если говорить о самом программировании, то иногда могут возникнуть совершенно неожиданные трудности (во многом благодаря оптимизатору C++). Однако не менее трудно решить, какие именно тесты и в каких количествах нужно сделать. Коды всех алгоритмов, которые выложены в данной статье, написаны мной. Доступны и результаты запусков на всех тестах. Единственное, что я не могу показать — это сами тесты, поскольку они весят почти 140 ГБ. При малейшем подозрении я проверял и код, соответствующий тесту, и сам тест. Надеюсь, что статья Вам понравится.

Под капотом Ethereum Virtual Machine. Часть 1 — Solidity basics

Из песочницы

В последнее время все чаще в новостях можно услышать слова «криптовалюта» и «блокчейн» и, как следствие, наблюдается приток большого количества заинтересованных этими технологиями людей, а вместе с этим и огромное количество новых продуктов. Зачастую, для реализации какой-то внутренней логики проекта или же для сбора средств используются «умные контракты» — особые программы, созданные на платформе Ethereum и живущие внутри его блокчейна. В сети уже существует достаточно материала, посвященного созданию простых смарт-контрактов и базовым принципам, однако практически нету описания работы виртуальной машины Ethereum (далее EVM) на более низком уровне, поэтому в этой серии статей я бы хотел разобрать работу EVM более детально.

Solidity — язык, созданный для разработки умных контрактов, существует относительно недавно — его разработка началась только в 2014 году и, как следствие, местами он »сыроват». В этой статье я начну с более общего описания работы EVM и некоторых отличительных особенностей solidity, которые нужны для понимая более низко-уровневой работы.

P.s Статья предпологает наличие некоторых базовых знаний о написании смарт-контрактов, а также о блокчейне Ethereum’a в целом, так что если вы слышите об этом в первый раз, то рекомендую сначала ознакомиться с основами, например, здесь:

• Hello world на solidity и деплой контракта в сеть
• Подборка инструментов для разработки
• Описание работы Ethereum и его блокчейна

Быстрый рендеринг океанских волн на мобильных устройствах

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

В этой статье мы хотели поговорить о моделировании волн в открытом море и представить алгоритм, который позволил достичь достаточно интересные результаты при приемлемых 25-30Fps на среднем китайфоне.

Автоэнкодеры в Keras, Часть 5: GAN(Generative Adversarial Networks) и tensorflow

Tutorial

• Часть 1: Введение
• Часть 2: Manifold learning и скрытые (latent) переменные
• Часть 3: Вариационные автоэнкодеры (VAE)
• Часть 4: Conditional VAE
• Часть 5: GAN (Generative Adversarial Networks) и tensorflow
• Часть 6: VAE + GAN

(Из-за вчерашнего бага с перезалитыми картинками на хабрасторейдж, случившегося не по моей вине, вчера был вынужден убрать эту статью сразу после публикации. Выкладываю заново.)
При всех преимуществах вариационных автоэнкодеров VAE, которыми мы занимались в предыдущих постах, они обладают одним существенным недостатком: из-за плохого способа сравнения оригинальных и восстановленных объектов, сгенерированные ими объекты хоть и похожи на объекты из обучающей выборки, но легко от них отличимы (например, размыты).
Этот недостаток в куда меньшей степени проявляется у другого подхода, а именно у генеративных состязающихся сетей — GAN’ов.
Формально GAN’ы, конечно, не относятся к автоэнкодерам, однако между ними и вариационными автоэнкодерами есть сходства, они также пригодятся для следующей части. Так что не будет лишним с ними тоже познакомиться.

Коротко о GAN

GAN’ы впервые были предложены в статье и сейчас очень активно исследуются. Наиболее state-of-the-art генеративные модели так или иначе используют adversarial.
Схема GAN:

Краткий курс машинного обучения или как создать нейронную сеть для решения скоринг задачи

Tutorial

Мы часто слышим такие словесные конструкции, как «машинное обучение», «нейронные сети». Эти выражения уже плотно вошли в общественное сознание и чаще всего ассоциируются с распознаванием образов и речи, с генерацией человекоподобного текста. На самом деле алгоритмы машинного обучения могут решать множество различных типов задач, в том числе помогать малому бизнесу, интернет-изданию, да чему угодно. В этой статье я расскажу как создать нейросеть, которая способна решить реальную бизнес-задачу по созданию скоринговой модели. Мы рассмотрим все этапы: от подготовки данных до создания модели и оценки ее качества.
Вопросы, которые разобраны в статье:
• Как собрать и подготовить данные для построения модели?
• Что такое нейронная сеть и как она устроена?
• Как написать свою нейронную сеть с нуля?
• Как правильно обучить нейронную сеть на имеющихся данных?
• Как интерпретировать модель и ее результаты?
• Как корректно оценить качество модели?

«Еще один шаг к блокчейну»: Bitfury Group представили Exonum 0.2

По данным аналитических агентств, рынок блокчейн-технологий вырастет с 210 млн долларов в 2016 году до 2,3 млрд долларов к 2021. Среднегодовой рост составит 61,5%. При этом в формировании рынка участвуют как крупные компании (например, IBM, вложившие 200 млн долларов в IoT-проекты, связанные с блокчейном), так и небольшие стартапы, адаптирующие блокчейны под разные нужды.
Bitfury Group выпускает новую версию открытого фреймворка для разработки блокчейнов Exonum. Exonum 0.2 содержит регулярные исправления, а также некоторые конструктивные доработки. С помощью Exonum компании и правительственные организации могут создавать функциональные блокчейны, которые будут безопасны, прозрачны и контролируемы.

Замкнутый и незамкнутый варианты задачи

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

Незамкнутый вариант задачи сводится к замкнутому путём замены весов дуг, входящих
в стартовую вершину, на число 0. Оптимальный замкнутый маршрут коммивояжёра в таком графе соответствует оптимальному незамкнутому маршруту в исходном графе.

Чтобы свести замкнутый вариант к незамкнутому, нужно определить число K{\displaystyle K}, строго превосходящее вес любого маршрута коммивояжёра в заданном графе (например, в качестве K{\displaystyle K} можно взять сумму максимальных по весу дуг, выходящих из каждой вершины, увеличенную на 1). Затем нужно добавить к графу новую вершину vn{\displaystyle v_{n}} (предполагаем, что вершины исходного графа пронумерованы числами от 0 до n−1{\displaystyle n-1}, при этом стартовая вершина имеет номер 0). Стоимости дуг, выходящих и входящих в вершину vn{\displaystyle v_{n}}, определяются следующим образом:

• cn,i=3K{\displaystyle c_{n,i}=3K}
• c,n=3K{\displaystyle c_{0,n}=3K}
• ci,n=ci,+2K{\displaystyle c_{i,n}=c_{i,0}+2K} при i{\displaystyle i} от 1{\displaystyle 1} до n−1{\displaystyle n-1}

Оптимальный незамкнутый маршрут коммивояжёра в таком графе соответствует оптимальному замкнутому маршруту коммивояжёра в исходном графе и имеет стоимость на 2K{\displaystyle 2K} больше.

ИИ для покера: как научить алгоритмы блефовать

О том как совершенствуется искусственный интеллект, можно судить по обычным играм. За последние два десятилетия алгоритмы превзошли лучших мировых игроков: сначала пали нарды и шашки, затем шахматы, «Своя Игра» (Jeopardy!), в 2015 году — видеоигры Atari и в прошлом году — Го.

Все эти успехи — про игры с информационной симметрией, где игроки имеют идентичную информацию о текущем состоянии игры. Это свойство полноты информации лежит в основе алгоритмов, обеспечивающих эти успехи, например, локальном поиске во время игры.

Но как обстоит дело с играми с неполной информацией?

Самым наглядный пример такой игры — покер. Чтобы на деле разобраться с этой игрой и алгоритмами решения этой задачи, мы организуем хакатон по написанию игровых ботов на основе машинного обучения. О том как научить алгоритмы блефовать и попробовать свои силы в покер, не трогая карты, под катом.

Евклидова задача коммивояжёра

Если D_ji = D_ij и расстояния между любыми городами i, j, k
удовлетворяют неравенству треугольника:
D_ij + D_jk ≥ D_ik, то
задачу коммивояжёра называют метрической.
Её частным случаем является задача соединения кратчайшей замкнутой ломаной линией точек на плоскости
(расстояние равно обычному евклидовому расстоянию).
Ниже приведены решения такой задачи для 20 и 50 городов:

Несложно видеть, что в евклидовой задача коммивояжёра (ETSP) оптимальный путь не должен иметь пересечений.
Действительно, пусть есть некоторый путь, изображённый ниже на первом рисунке.
Пунктиром обозначены остальные его участки (т.е. приведены только 4-е города).
Если перебросить два участка пути (как на второй картинке), то общий путь вырастет
(сумма диагоналей 4-угольника всегда длиннее суммы двух противоположных сторон):

С ETSP связаны интересные вопросы статистического характера.
Рассмотрим, например, квадрат в котором случайно, с равномерным распределением
размещено N городов. Оказывается, что в большинстве случаев
такие «карты городов» имеют кратчайшие пути примерно одной длины,
пропорциональной квадратному корню из N.

Периоды звездных суток и звездный год в радиоактивном распаде

Здесь будет рассказано о алгоритме сравнения функций плотности вероятности радиоактивного распада, проявляющих периодичность в звездные сутки и звездный год.

*сидерический год — период орбитального движения Земли вокруг Солнца в инерциальной системе отсчёта (относительно «неподвижных звёзд»);
Эта статья массивное продолжение вводной статьи 2014 года по периодам в радиоактивности
Выводы:
— Форма вероятностей неслучайна и зависит от космофизических причин
— Форма вероятностей с высокой вероятностью повторяется с периодичностью в солнечные и звездные сутки, солнечный и звездный год
— Форма вероятностей сходна в ближайшие промежутки времени
— Формы вероятностей часто бывают хирально симметричнымиАкадемия
Более подробно об этом исследовании написано в книге
И статьях на Успехах физических наук: раз и два.
А теперь сам алгоритм и подробнее про задачу!

Айтрекинг: доступные решения и их особенности

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

История

Точно неизвестно, когда проблему коммивояжера исследовали впервые. Однако, известна изданная в 1832 году книга с названием «Коммивояжёр — как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах — советы старого курьера» (нем. Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur), в которой описана проблема, но математический аппарат для её решения не применяется. Зато в ней предложены примеры маршрутов для некоторых регионов Германии и Швейцарии.

Ранним вариантом задачи может рассматриваться англ. Icosian Game Уильяма Гамильтона 19 века, которая заключалась в том, чтобы найти маршруты на графе с 20 узлами. Первые упоминания в качестве математической задачи на оптимизацию принадлежат Карлу Менгеру (нем. Karl Menger), который сформулировал её на математическом коллоквиуме в 1930 году так:

Гамильтон Уильям Роуэн.

Вскоре появилось известное сейчас название задача странствующего торговца (англ. Traveling Salesman Problem), которую предложил Хасслер Уитни (англ. Hassler Whitney) из Принстонского университета.

Вместе с простотой определения и сравнительной простотой нахождения хороших решений задача коммивояжёра отличается тем, что нахождение действительно оптимального пути является достаточно сложной задачей. Учитывая эти свойства, начиная со второй половины XX века исследование задачи коммивояжёра имеет не столько практический смысл, сколько теоретический в качестве модели для разработки новых алгоритмов оптимизации.

Многие современные распространенные методы дискретной оптимизации, такие как метод отсечений, ветвей и границ и различные варианты эвристических алгоритмов, были разработаны на примере задачи коммивояжёра.

В 1950-е и 1960-е годы задача коммивояжёра привлекла внимание ученых в США и Европе. Важный вклад в исследование задачи принадлежит Джорджу Данцигу, Делберту Рею Фалкерсону (англ. Delbert Ray Fulkerson) и Селмеру Джонсону (англ. Selmer M

Johnson), которые в 1954 году в институте RAND Corporation сформулировали задачу в виде задачи дискретной оптимизации и применили для её решения метод отсечений. Используя этот метод, они построили путь коммивояжёра для одной частной постановки задачи с 49 городами и обосновали его оптимальность. В 1960-е и 1970-е годы задача изучалась многими учеными как теоретически, так и с точки зрения её приложений в информатике, экономике, химии и биологии.

Ричард Карп в 1972 году доказал NP-полноту задачи поиска гамильтоновых путей, из чего, благодаря полиномиальной сводимости, вытекала NP-трудность задачи коммивояжёра. На основе этих свойств им было приведено теоретическое обоснование сложности поиска решений задачи на практике.

Больших успехов удалось достичь в конце 1970-х и 1980-х годах, когда Мартин Грётчел (нем. Martin Grötschel), Манфред Падберг (нем. Manfred Padberg) и Джованни Ринальди (итал. Giovanni Rinaldi) и другие, с применением новых методов деления плоскостью, ветвей и границ вычислили решение для отдельного случая задачи с 2393 городами.

В 1990-е годы Дэвид Аплгейт (англ. David Applegate), Роберт Биксби (англ. Robert Bixby), Вашека Шватал (англ. Vašek Chvátal) и Уильям Кук (англ. William Cook) установили рекорды по программе Конкорд. Герхард Райнельт (нем. Gerhard Reinelt) создал TSPLIB — набор стандартизованных экземпляров задачи коммивояжёра различной степени сложности для сравнения результатов работы различных групп исследователей. В марте 2005 года задача с 33 810 узлами была решена программой Конкорд: был вычислен путь длиной в 66 048 945 и доказано отсутствие более коротких путей. В апреле было найдено решение для экземпляра с 85 900 узлами. Используя методы декомпозиции, можно вычислить решения для случаев задачи с миллионами узлов, длина которых менее, чем на 1 % больше оптимальной.

Примечания

1. M. Fischetti, J.J. Salazar-Gonzalez, and P. Toth. A Branch-and-Cut algorithm for the symmetric generalized traveling salesman problem. Operations Research 45 (3) (1997), 378—394.
2. D. Ben-Arieh, G. Gutin, M. Penn, A. Yeo, and A. Zverovitch. Transformations of generalized ATSP into ATSP, Operations Research Letters 31 (2003), 357—365.
3. 6. Arash Behzad, Mohammad Modarres (2002). A New Efficient Transformation of Generalized Traveling Salesman Problem into Traveling Salesman Problem
4. L.V. Snyder and M.S. Daskin. A random-key genetic algorithm for the generalized traveling salesman problem. European Journal of Operational Research 174 (2006), 38−53.
5. J. Silberholz and B. Golden. The Generalized Traveling Salesman Problem: a new Genetic Algorithm approach. Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, 2007, 165−181.

Оценка связанности событий с помощью Байеса

В своей книге Нейт Сильвер приводит такой пример: допустим требуется разместить инвестиции в нескольких предприятиях, которые могут обанкротиться с вероятностью . Требуется оценить свои риски. Чем выше вероятность банкротства, тем меньше мы будем вкладывать денег. И наоборот, если вероятность банкротства стремится к нулю, то можно инвестировать без ограничений.
Если имеется 2 предприятия, тогда вероятность того, что они оба обанкротятся, и мы потеряем все вложения . Так учит стандартная теория вероятности. Но что будет, если предприятия связаны, и банкротство одного ведет к банкротству другого?
Крайним случаем является ситуация, когда предприятия полностью зависимы. Вероятность двойного банкротства ( банкрот1 & банкрот2 ) = ( банкрот1 ), тогда вероятность потери всех вложений равна . Методика оценки риска имеет большой разброс от 0.05 до 0.0025 и реальное значение зависит от того, насколько правильно мы оценили связанность двух событий.

При оценке инвестиций в предприятий имеем от до . То есть максимальная возможная вероятность остается большой , и старая поговорка «не клади яйца в одну корзину» не сработает, если упадет прилавок со всеми корзинами сразу.
Таким образом наши оценки имеют колоссальный разброс, и сколько куда вкладывать остается вопросом. А ведь надо хорошо считать, прежде чем вкладывать. Нейт Сильвер говорит, что незнание этих простых законов аналитиками привело к крахам фондового рынка в 2008 году, когда рейтинговые агенства США оценивали риски, но не оценивали связанность рисков. Что в конце концов привело к эффекту домино, когда сначала свалился крупный игрок и увлек за собой других.
Попробуем разобрать эту проблему, решив простую математическую задачу после ката.

Генерация коротких текстов с ограничивающими условиями — для рекламы и других целей

На практике нередко встречается задача не просто написать какой-то текст, а выполнить некоторые условия — например уложить максимум ключевых слов в заданную длину и/или использовать/не использовать определенные слова и словосочетания

Это бывает важно для бизнеса (при составление рекламных объявлений, в том числе, для контекстной рекламы, при SEO-оптимизации сайтов), для образовательных целей (автоматическое составление тестовых вопросов) и в ряде других случаев. Такие задачи оптимизации вызывают много головной боли, т. к

людям относительно легко сочинять тексты, но при этом не так просто написать что-то отвечающее тем или иным критериям «оптимальности». С другой стороны, компьютеры отлично справляются с задачами оптимизации в других областях, но плохо понимают естественный язык, и поэтому им трудно сочинять текст. В данной статье, рассмотрим известные подходы к решению этой задачи и немного поделимся собственным опытом.

Быстрое удаление пробелов из строк на процессорах ARM

Перевод

Предположим, что я дал вам относительно длинную строку, а вы хотите удалить из неё все пробелы. В ASCII мы можем определить пробелы как знак пробела (‘ ’) и знаки окончания строки (‘\r’ и ‘\n’). Меня больше всего интересуют вопросы алгоритма и производительности, так что мы можем упростить задачу и удалить все байты со значениями меньшими либо равными 32.
В предыдущией статье, где я задавал вопрос об удалении пробелов на скорость, лучшим ответом было использование векторизации с помощью 128-битных регистров (SSE4). Оно оказалось в 5-10 раз быстрее подхода в лоб.
Очень удобно, что во всех процессорах имеются 128-битные векторные регистры, также как в процессорах x64. Неужели процессоры ARM могут работать настолько же быстро, как процессоры x64?