TL;DR Очень подробный разбор алгоритмов решения задачи о кратчайшем пути от классики до двунаправленного А* и ALT с кодом и примерами на OSM

Люди пытались найти более быстрые способы передвижения на протяжении всей своей истории. Появление качественной дорожной системы в римской империи в своё время привело к её расцвету, но со временем выяснилось, что и в продуманных дорожных системах бывают забавные изъяны, как например в небезызвестной задаче о кёнигсбергских мостах, считающейся отправной точкой возникновения теории графов. Неудивительно и то, что с развитием вычислительной техники логистические задачи стали одними из первых, над которыми трудились первопроходцы компьютерных наук. Задача о кратчайшем пути -- одна из них, звучит достаточно просто: есть несколько городов и дорог, соединяющих пару городов между собой, мы хотим попасть из города А в город Б пройдя при этом минимальное расстояние. Первый системный подход к этой задаче был описан в работе Эгервари в 1931г., спустя 25 лет Эдсгер Дейкстра придумал алгоритм, который сейчас является частью любого уважающего себя базового курса алгоритмов на графах. На нём же, будем честны, заканчиваются знания о кратчайших путях у большинства профессиональных разработчиков, ибо сценариев, где реализации с википедии/stackoverflow будет не хватать, крайне мало.

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

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

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

Приятного прочтения )

Распространённая задача программистов в работе с геопространственными данными — отобразить маршруты между различными точками. Решением, которое может понадобиться в разработке веб-сайта, делимся к старту курса по Fullstack-разработке на Python.

Экономичное отопление. Как утеплить дом и не разориться?

Каждый городской житель мечтает о загородном доме.

Тишина, свежий воздух!

И тут же вы едете смотреть участок земли в превосходном живописном и экологичном месте.

Вопрос стоимости отопления загородного дома‑ это та проблема, которую начинают решать уже ввязавшись в стройку на уже купленном участке земли в живописном месте.

И тут внезапно выясняется, что газа нет!

Что это означает?

Это означает, что у вас в наличии 15 кВт подключенного электричества на все хозяйственные нужды, включая отопление.

15кВт — много это или мало?

Ответ как обычно прячется в самом вопросе, а именно: Смотря для чего?

Ниже приведён проект реального одноэтажного дома. (см.рис.1–2)

Уже лет 50, со времён выхода первого издания «Языка программирования Си» Кернигана и Ритчи, известно, что «числа с плавающей запятой» одинарной точности имеют размер 32 бита, а числа двойной точности — 64 бита. Существуют ещё и 80-битные числа расширенной точности типа «long double». Эти типы данных покрывали почти все нужды обработки вещественных чисел. Но в последние несколько лет, с наступлением эпохи больших нейросетевых моделей, у разработчиков появилась потребность в типах данных, которые не «больше», а «меньше» существующих, потребность в том, чтобы как можно сильнее «сжать» типы данных, представляющие числа с плавающей запятой.

Я, честно говоря, был удивлён, когда узнал о существовании 4-битного формата для представления чисел с плавающей запятой. Да как такое вообще возможно? Лучший способ узнать об этом — самостоятельно поработать с такими числами. Сейчас мы исследуем самые популярные форматы чисел с плавающей запятой, создадим с использованием некоторых из них простую нейронную сеть и понаблюдаем за тем, как она работает.

Новое доказательство за авторством австралийского писателя-фантаста Грега Игана и доказательство от 2011 года, анонимно опубликованное в сети, признали значительными прорывами в области изучения загадки, которую математики исследуют уже 25 лет

Привет, Хабр! В этой статье я расскажу вам про 5 моих любимых до сих пор не решенных задач, условие которых очень легко понять, однако очень трудно решить.

Эти задачи показались мне интересными, поэтому я решил написать про них статью. И нет, здесь не будет их доказательств.

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

Квантовые компьютеры. С точки зрения традиционного программиста-математика.
Часть 1. Основы. Квантовый регистр.

О чем эта публикация

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

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

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

Добрый день! Меня зовут Михаил Емельянов, недавно я опубликовал на «Хабре» небольшую статью с примерным путеводителем начинающего Python-разработчика. Пользуясь этим материалом как своего рода оглавлением книги, я написал первые четыре главы мини-учебника «Ядро планеты Python», где постарался коротко, но достаточно ёмко раскрыть специфику, удобство, красоту и силу этого прекрасного языка.

Оригинал учебника лежит на GitHub, вы вольны сколько угодно дополнять и переделывать его. Самое главное — учебник написан на Jupiter Notebook, а это значит, что вы можете интерактивно редактировать код, мгновенно добавляя новые сущности или проясняя непонятные моменты.

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

И уж конечно, никогда при написании a * b мы не задумываемся о том, как реализовано умножение чисел a и b в нашем языке. Какие вообще есть алгоритмы умножения? Это какая-то нетривиальная задача?

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

Привет, Хабр! В этой статье я продемонстрирую 5 трюков Python на понятных для новичков примерах, которые помогут вам писать более элегантный Python код в вашей повседневной работе.

Изучая программирование я встречаю примеры невозможных алгоритмов. Интуиция говорит, что такого не может быть, но компьютер опровергает её простым запуском кода. Как такую задачу, требующую минимум кубических затрат по времени, можно решить всего за квадрат? А вон ту я точно решу за линию. Что? Есть гораздо более эффективный и элегантный алгоритм, работающий за логарифм? Удивительно!

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

Интересно? Добро пожаловать под кат!

Пожалуй, наиболее популярной парадигмой программирования является императивное программирование, но это не единственный вид программирования, широки известны функциональное и логическое программирование. Constraint Programming (Программирование в ограничениях/Ограниченное программирование) не так популярно. Но это очень мощный инструмент для решения комбинаторных задач. Вместо реализации алгоритма, который решает задачу, с последующей тратой кучи времени на его отладку, рефакторинг и оптимизацию, программирование с ограничениями позволяет вам просто описать модель в специальном синтаксисе, а особая программа (решатель) найдет решение для вас (или скажет, если их нет). Впечатляет не правда ли? Мне кажется, каждый программист должен знать о такой возможности.