Рубрика «дейкстра» - 2

Приветствую всех и особенно тех кто интересуется задачами дискретной математики и теорией графов.

Предыстория

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

Читать полностью »

M* — алгоритм поиска кратчайшего пути, через весь мир, на смартфоне - 1

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

Под катом представлена обобщенная эвристика к алгоритму A*, полезная именно в свете практической пригодности на больших графах при ограниченных ресурсах, например, на мобилке.
Читать полностью »

В продолжение статей про устройство таблицы маршрутизации и про реализацию протокола BGP в Quagga, в настоящей статье я разберу как работает протокол OSPF. Я ограничусь случаем для одной OSPF зоны без редистрибъюции маршрутов из других протоколов маршрутизации.
Читать полностью »

image
Изображение с сайта abv24.com

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

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

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

Сейчас это не кажется чем-то необычным, но в 50-е годы это прозвучало как откровение. Дейкстра понял и убедительно показал, как теория может и должна помочь практике.Читать полностью »

image

Некоторые считают, что современный мир почти не знает Никлауса Вирта и даже не догадывается о его огромном вкладе в мировую компьютерную науку. Кто-то полагает его «отцом Паскаля». Вирта вспоминают не только педагоги в ВУЗах, когда преподают студентам Turbo Pascal, но и коммерческие разработчики, пишущие на Delphi.

На самом деле, Никлаус Вирт является инженером с большой буквы, его вклад в развитие языков программирования не ограничивается Паскалем, а только начинается с него. Кроме того, Вирт — педагог, общественный деятель и, можно сказать, философ. Попробуем оценить реальный масштаб его личности и вклад в ИТ-индустрию.Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js