Я впервые изучал рекурсивные функции, пытаясь реализовать функцию, которая принимала бы любые два числа и возвращала бы их наибольший общий делитель (сложнее, чем кажется), когда впервые наткнулась на имя Дейкстры. Я залез в кроличью нору в надежде найти лучший подход к своей проблеме и обнаружил, что древнегреческий философ Евклид довольно элегантно решил ее примерно в 300 году до н.э. Осознание того, что проблема, которую я пытался решить более часа на ноутбуке, была решена две тысячи лет назад человеком, у которого было немного больше, чем ручка и бумага, вряд ли меня воодушевляло. Затем я обнаружил другое, более элегантное решение, которое применялось до 1950-х годов. Это было приписано голландскому математику и ученому-компьютерщику Эдсгеру Дейкстре.
В течение следующих нескольких недель моих занятий компьютерным программированием это имя постоянно всплывало, всегда ассоциировавшись с элегантностью алгоритмической логики и структурирования данных. Оказывается, Дейкстра был не только блестящим математиком, но и пионером компьютерного программирования в 50-х и 60-х годах, когда академические институты еще даже не начали признавать эту дисциплину законной областью изучения в рамках науки и математики. . Он определил и решил многие концепции и проблемы, которые сейчас являются стандартными в компьютерных науках. Мало того, он был чрезвычайно активен и оказал огромное влияние, помогая разрабатывать новые языки программирования и направляя среду в направлении, которое он считал наиболее полезным для практики.
Возможно, его самый известный алгоритм или, по крайней мере, его наиболее реализованный алгоритм называется просто алгоритмом кратчайшего пути Дейксры, а иногда просто алгоритмом Дейктры для краткости. По сути, он может взять граф взаимосвязанных узлов с вершинами и ребрами заданного значения и вернуть кратчайший путь от одного узла к другому. Это не только основная логика любого приложения для картографирования направлений, но и чрезвычайно полезная при реализации любой сети передачи данных, которая должна передавать пакеты данных из точки А в точку Б по кратчайшему и быстрому возможному пути.
Вот суть или псевдокод того, как это работает…
- Назначьте предварительное расстояние для каждого узла, 0 для нашей начальной точки, бесконечность для всего остального.
- Держите два набора данных сбоку: один для списка полностью посещенных узлов, а другой для еще не посещенных узлов.
- Для текущего узла рассмотрим каждого непосещенного соседа и рассчитаем новое расстояние до этого узла на основе расстояния текущего пути к нему. Если новое предварительное расстояние меньше, чем расстояние, назначенное в настоящее время соседу, то повторно назначьте новое ориентировочное расстояние соседу.
- Когда закончите рассмотрение всех соседей текущего узла, отметьте текущий посещенный узел и переместите его из непосещенного набора в посещенный набор.
- Если узел назначения становится посещенным, то алгоритм завершается, и вы должны получить ответ.
- В противном случае перейдите к узлу в списке непосещенных с наименьшим предварительным расстоянием и повторите с шага 3.
Удивительно, что этот маленький кусочек вычислительной логики, основанный на некоторых линиях, точках и числах из 1959 года, сохранил свои позиции на протяжении большей половины века, несмотря на цифровую революцию, и до сих пор отвечает за то, что направляет наше беспомощно дезориентированное «я» миллениалов к работать вовремя. Дейкстра, возможно, был не только вычислительным гением, но и заядлым писателем и университетским профессором, написавшим бесчисленное количество статей, эссе и даже скопированных писем с комическими размышлениями. Я предпочитаю его часто цитируемые цитаты о важности доступности в программировании.
«Как нам убедить людей в том, что в программировании простота и ясность — короче говоря, то, что математики называют «изящностью» — это не роскошь, а решающий фактор, который решает между успехом и неудачей?»
В этой постоянно развивающейся области разработки программного обеспечения легко попасть в слишком часто встречающиеся кроличьи норы чрезмерной сложности. Возможно, нам всем было бы хорошо держать слова этого мудрого голландца в затылке, поскольку мы неустанно продвигаем дела вперед.
