Пару недель назад Даня Тарарухин рассказал на Хабре, как появился наш сервис, Яндекс.Маршрутизация, и как он помогает компаниям с логистикой. Создавая платформу, мы решили несколько интересных проблем, одной из которых и посвящён сегодняшний пост. Я хочу поговорить о самом планировании маршрутов и необходимых для этого ресурсах.
Читать полностью »
Ежедневный маршрут большинства из нас ограничивается поездкой из дома на работу и обратно. И самое сложное препятствие, которое может замедлить наше передвижение, — это пробки. Но в нашей стране есть огромное количество мест, куда можно добраться только на спецтранспорте.
Такой транспорт хорош, если не требуется возить большие объемы грузов или ездить в столь труднодоступные области на регулярной основе. Тогда нам уже стоит задуматься о строительстве инфраструктуры, передвижение по которой возможно и на привычном гражданском транспорте.
И хорошо, если вся сложность проектирования будущего маршрута заключается в поиске линейки и карандаша, чтобы начертить прямую линию на карте, соединяющую пару объектов. Но, увы, наша реальность сильно отличается от этого. Что делать, если местность при полете над ней напоминает хороший кусок швейцарского сыра?
Больше года мы с коллегами из научной лаборатории Digital Design работаем над созданием инструмента, который сможет строить различные сети коммуникаций в автоматическом режиме. За подробностями добро пожаловать под кат.
Двоичный поиск — один из самых базовых известных мне алгоритмов. Имея отсортированный список сравнимых элементов и целевой элемент, двоичный поиск смотрит в середину списка и сравнивает значение с целевым элементом. Если цель больше, мы повторяем с меньшей половиной списка, и наоборот.
При каждом сравнении алгоритм двоичного поиска разбиваем пространство поиска пополам. Благодаря этому всегда будет не более 
сравнений со временем выполнения 
. Красиво, эффективно, полезно.
Но всегда можно посмотреть под другим углом.
Что, если попробовать выполнить двоичный поиск по графу? Большинство алгоритмов поиска по графам, такие как поиск в ширину или поиск в глубину, требуют линейного времени и были придуманы довольно умными людьми. Поэтому если двоичный поиск по графу будет иметь какой-то смысл, то он должен использовать больше информации, чем та, к которой имеют доступ обычные алгоритмы поиска.
Читать полностью »
Эта статья является продолжением моего введения в алгоритм A*. В ней я показал, как реализуются поиск в ширину, алгоритм Дейкстры, жадный поиск по наилучшему первому совпадению и A*. Я стремился как можно больше упростить объяснение.
Поиск по графам — это семейство схожих алгоритмов. Существует множество вариаций алгоритов и их реализаций. Относитесь к коду этой статьи как к отправной точке, а не окончательной версии алгоритма, подходящей ко всем ситуациям.
Читать полностью »
При разработке игр нам часто нужно находить пути из одной точки в другую. Мы не просто стремимся найти кратчайшее расстояние, нам также нужно учесть и длительность движения. Передвигайте звёздочку (начальную точку) и крестик (конечную точку), чтобы увидеть кратчайший путь. [Прим. пер.: в статьях этого автора всегда много интерактивных вставок, рекомендую сходить в оригинал статьи.]
Для поиска этого пути можно использовать алгоритм поиска по графу, который применим, если карта представляет собой граф. A* часто используется в качестве алгоритма поиска по графу. Поиск в ширину — это простейший из алгоритмов поиска по графу, поэтому давайте начнём с него и постепенно перейдём к A*.
Читать полностью »
Изображение с сайта abv24.com
Один из тех людей, с именем которых связано превращение программирования из шаманства в науку, — Эдсгер Дейкстра. Он небезуспешно доказывал, что программирование — высокое искусство и интеллектуальное творчество.
Во всех своих исследованиях Дейкстра придает большое значение простоте и изяществу математических рассуждений. При написании своих работ он создал новый стиль научных и технических сообщений, который можно описать как нечто среднее между журнальными публикациями и дружеской перепиской.
Программирование – не набор пассов и заклинаний, не шаманство, не танцы с бубном, а математическая дисциплина. А всякая дисциплина, если она претендует на нечто большее, чем на внешний эффект, должна строиться на прочном фундаменте. Таким фундаментом для Дейкстры является математическая логика, а точнее – исчисление предикатов.
Сейчас это не кажется чем-то необычным, но в 50-е годы это прозвучало как откровение. Дейкстра понял и убедительно показал, как теория может и должна помочь практике.Читать полностью »
