Алгоритмы *

3 недели назад я написал инструкцию о том как получить доступ к ChatGPT в России. За это время она неожиданно набрала более 130т просмотров, что показывает явный интерес сообщества к этой теме.

За последнее время я собрал достаточно много интересной информации вокруг этой технологии и очень хочу с вами всем этим поделиться. Я являюсь больше разработчиком мобильных приложений, а не специалистом в области ИИ - поэтому текст данной серии статей ориентирован больше на гипотетические размышления, чем на точные технические детали. Если вы можете опровергнуть что-то из написанного мной - жду вас в комментариях!

Привет, Habr! На связи Михаил Будылин и Антон Денисов, мы работаем в отделе аналитики данных X5 Tech.

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

Что делает код хорошим? Большинство программистов ответят: хороший код должен быть структурирован, легко читаем и понятен. Но так ли важно качество кода, если он медленный? В большинстве задач производительность кода не критична, хотя и желательна. Но есть задачи, время выполнения которых столь огромно, что выигрыш в производительности доминирует над всем остальным.

Я говорю про NP-трудные задачи (NP-трудность - недетерминированная полиномиальная трудность по времени) и на одной из данного класса хочу акцентировать ваше внимание. Задаче коммивояжера.

Мы не будем рассматривать эвристические алгоритмы, нам нужно точное решение.

Computer Vision позволил создать принципиально новые продукты и механики в многих областях жизни: умный город, беспилотный транспорт, аналитика производств.
То же самое произошло и с супермаркетами: “оценка длины очереди”, “оценка загруженности зала”, “оценка загруженности полок товарами”, “проверка выкладки”, “проверка качества уборки”, “проверка ценников” и многое-многое другое это теперь автоматизированные задачи.
В этой статье я хочу рассказать про то, какие используются общие принципы для распознавания товаров. Эти алгоритмы необходимы для проверки выкладки, заполненности полок, контроля остатков и других задач.
Так получилось что за последние 7 лет мы были вовлечены в решение и консультирование по большинству таких задач, так что накопилось много интересного опыта.

Всем привет, на связи Фарук, инженер-разработчик электроники и встроенного ПО в Whoosh (читается как ВУШ, ощущается как вжууух). Работаю я в embedded отделе (хардкорные программисты, что пишут прошивку на C для различных железок и проектируют эти самые железки), но в основном занимаюсь анализом различных данных от нашего IoT модуля и разработкой алгоритмов для работы с этими данными.

Наша компания — сервис аренды электросамокатов (а местами еще и электровелосипедов) или, иными словами, кикшеринг. О том, как мы к этому пришли и что из себя представляем можно почитать здесь.

Одно из отличий использования шерингового самоката от личного — наличие определенных правил. Например, вы видели когда-нибудь парочку влюбленных, вдвоем на самокате, исчезающих в закате? Или может наблюдали троих парней, которые в обнимку, преодолев смущенье, едут навстречу новым приключеньям? А может быть вы видели как чей-то отец, словно швец, жнец и на самокате ездец, с одним ребенком подмышкой а с другим на шее смело едет по парковой аллее?
Вызывают ли у вас эти картины гнев и праведное негодование? А может быть вы и сами не прочь прокатиться с другом/подругой на одном самокате? У нас для вас есть две новости.

Во-первых, так нельзя. А во-вторых, добро пожаловать под кат.

Привет, меня зовут Абай Баймуканов, я работают алгоритмистом в ИТ-компании Relog, разрабатывающей облачный сервис для оптимизации городской доставки.

Для решения транспортных задач в логистике нужны лучшие алгоритмы, поэтому мы решили провести собственное исследование и выбрали для него два самых популярных открытых алгоритма - Vroom и Jsprit.

Нужно было понять какой из них лучше не только по качеству, но и выдает решение (построение маршрутов с учетом различных транспортных задач) за короткое время.

Какую задачу решали

Есть разные виды VRP-задач, например, CVRP (учет весогабаритных параметров), VRPTW (учет временных окон), MDVRP (задача с несколькими складами) и PDVRP(задача с забор-доставка). Для теста мы взяли CVRPTW (CVRP+VRPTW), поскольку это самая актуальная для наших клиентов задача.

Про сами алгоритмы. В чем их разница и преимущества

Для решения задач мы использовали два солвера Vroom и Jsprit. Оба они являются движками с открытым исходным кодом и решают CVRPTW, а также имеют много звезд Github.

VROOM

Vroom — это движок оптимизации с открытым исходным кодом, написанный на C++17, предназначенный для поиска эффективных решений разных реальных задач маршрутизации транспортных средств (VRP) за небольшое вычислительное время. Он решает задачу в 2 этапа:

В данной статье будут рассмотрены базовые возможности подсистемы "Оценка производительности" в библиотеке стандартных подсистем.

В материале статьи я приведу два примера использования "оценки производительности" - для обычных "линейных операций" и для "длительных операций" (фоновых). Данную тему считаю интересной для оценки возможностей ваших систем. Сам довольно часто использую данных функционал.

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

Создание новой ключевой операции, встраивание ее в объект оценки произодительности.

Для начала, я подготовлю две ключевые операции, одну из которых, затем, встрою в объект. Делается это вот таким кодом...

Библиотека Ranges для C++20 предлагает альтернативы для большинства алгоритмов. На этот раз я хочу показать вам десять немодифицирующих операций. Мы сравним их со «старой» стандартной версией и увидим их преимущества и ограничения.

Подробности — к старту нашего курса по разработке на C++.

1. Насколько ему могут быть интересны наши рекомендации.
2. Зачем мы ему это показываем.

Привет всем! В данной статье предлагаю небольшой обзор возможностей актуальной библиотеки стандартных подсистем (БСП) на предмет формирования большинства существующих штрихкодов.

В данной статье рассмотрим примеры выполнения функций и процедур в многопоточном режиме, используя возможности Библиотеки стандартных подсистем платформы 1С.

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

Введение

Всем привет! В данном материале, я решил, что немного отойду от своего основного профиля - практической разработке и изучения возможностей библиотеке стандартных подсистем (БСП) и затрону работу программиста с языком запросов 1с.

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

С 1 по 7 ноября проходила квалификация Yandex Cup 2022. В секции Алгоритм: Марафон организаторы предложили интересную задачу программирования в ограничениях, обобщения известной задачи коммивояжёра, задачу поиска маршрута (vehicle routing problem). В статье расскажу о своем решении на основе Google OR-tools.

Всем здравствуйте, уважаемые Хабровчане!

У меня достаточно давно закралась идея опубликовать свой первый пост, который будет полезен для сообщества, как-то поможет взглянуть на мир привычных вещей иначе, раскроет те технологии, на которые ранее никто не обращал внимания, или недостаточно был усердчив в их изучении.

Начну с небольшого знакомства и расскажу о своем опыте работы. Без малого 13 лет я являюсь исследователем транспортных сетей в телеком индустрии. Работал в одном из крупнейших операторов связи, был экспертом, менеджером, обычным инженером. Строил и свопировал региональные транспортные сети, развернул с коллегами систему мониторинга сетей MBH от Москвы до Владикавказа, крайние два года отдал изучению графовых баз данных, которые позволили решить не решаемую проблему - автодискавери и построение топологии сетей с путями прохождения трафика сервисов мобильной сети и B2B клиентов. Если забежать немного вперед, то данная система осталась не нужна главному заказчику, и мы благополучно выкинули ее на помойку истории. К сожалению, так бывает, но сейчас не об этом.

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

Немного тезисов - что нужно понять.

В данной статье вспомним как обрабатывать результаты запроса в вычисляемых полях СКД, а так же сделаем небольшой обзор на новые функции СКД платформы 8.3.20.

В алгоритмических задачах на графах мы часто используем четыре известных алгоритма: Поиск в ширину или глубину, алгоритмы Дейкстры и А*. Разбираемся, почему на деле это один и тот же алгоритм.

Я люблю давать простые задачки студентам на лекции. Во-первых, понятно, скольких мы потеряли, во-вторых, это переключение из режима потребления информации в режим выдачи результатов, в третьих — возможность проявить себя для шустрых. Сплошные плюсы!

Одна из простых задач звучит так: «При переводе картинки из цветового пространства RGB в YUV мы выполняем прореживание, то есть выкидываем каждый четный столбец и каждую четную строку в компонентах U и V (все компоненты пикселя по 1 байту). Вопрос: во сколько раз меньше данных у нас стало?» Эта операция называется chroma subsampling и широко используется при сжатии видео, например.

Забавно, что когда-то давно, когда винчестеры были меньше, а дискеты больше, студенты реально отвечали на этот вопрос быстро. А в последние годы регулярно народ в ступор впадает. Приходится разбирать по частям: «Если выкинуть каждую четную строку и каждый четный столбец, во сколько раз меньше данных будет у компоненты?» Почти хором: «В четыре». Начинаю подкалывать: «Отлично! У нас было 3 яблока, первое осталось как есть, а от второго и третьего осталось по четвертинке. Во сколько раз меньше яблок у нас стало?» Народ ржет, но, наконец-то, дает правильный ответ (заметим, не все). 

Это было бы смешно, если бы от способности быстро в уме прикинуть результат не зависела способность быстрее создавать сложные алгоритмы. 

И хорошо видно, как эта способность в широких массах студентов заметно плавно падает. Причем не только в нашей стране. Придуман даже специальный термин: «цифровое слабоумие» ("digital dementia") — снижение когнитивных способностей, достаточно серьезное, чтобы повлиять на повседневную деятельность человека. 

Кому интересно как теряют мозг студенты масштабы бедствия и что с этим делать — добро пожаловать под кат!