Алгоритмы на графах
2026-02-26 20:11 Diff
https://ru.hexlet.io/courses/algorithms-graphs/lessons/littles-algorithm-code/theory_unit

В этом уроке мы перейдем от теории к практике. Вы узнаете, как реализовать алгоритм Литтла в коде.

Чтобы реализовать алгоритм Литтла, мы написали такой объемный код:

Нажмите, чтобы увидеть код

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

Здесь мы реализовали вспомогательный класс Node, в котором сосредоточили функции для работы с узлами дерева решений.

JavaScript хранит ссылку на объекты, в том числе на массивы. Если мы хотим создать копию матрицы смежности в каждом узле, мы не можем просто скопировать массив. Нужно создать новый массив и скопировать в него все значения исходного массива.

Матрица — это массив массивов. Поэтому мы выполняем глубокое копирование:

Еще нам нужно создать две функции:

  • Первая функция будет искать минимумы в каждой строке
  • Вторая — редуцировать, то есть вычитать минимумы из каждого элемента каждой строки

Так выглядит реализация в коде:

Далее мы напишем похожие функции и для столбцов. Затем реализуем метод редуцирования матрицы и по строкам и по столбцам:

Последний метод в классе Node — это getCellWithMaxPenalty. Он находит ячейку матрицы с наибольшим штрафом.

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

Во время работы алгоритма Литтла мы должны исключить из рассмотрения закрывающие ребра — те, которые могут завершить маршрут раньше времени.

Для поиска закрывающих ребер напишем функцию getCloseEdges. Для ее работы реализуем вспомогательные функции findNextStartCity и findNextEndCity:

На каждом шаге алгоритма мы строим левое и правое поддеревья из какого-то узла дерева решений.

Вынесем код построения в функцию makeChildren. Используем написанные нами ранее методы и функции — getCellWithMaxPenalty, cloneMatrix и reduce:

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

Выводы

В этом уроке мы закончили изучать алгоритм Литтла. Теперь вы знаете, как он работает в теории и как реализовать его в коде. Повторим ключевые выводы, к которым мы пришли в прошлом теоретическом уроке:

  • Алгоритм Литтла находит оптимальное решение в дереве решений
  • Для работы алгоритма важно, чтобы оценка нижней границы была корректной
  • Обычно алгоритм Литтла работает быстрее метода перебора, в худшем случае — с той же скоростью O(n!)