Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

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

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

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

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

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

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

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

8 <ul><li>Первая функция будет искать минимумы в каждой строке</li>

9 <li>Вторая - редуцировать, то есть вычитать минимумы из каждого элемента каждой строки</li>

10 </ul>Так выглядит реализация в коде:

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

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

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

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

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

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

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

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

19 <h2>Выводы</h2>

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

21 <ul><li>Алгоритм Литтла находит оптимальное решение в дереве решений</li>

22 <li>Для работы алгоритма важно, чтобы оценка нижней границы была корректной</li>

23 <li>Обычно алгоритм Литтла работает быстрее метода перебора, в худшем случае - с той же скоростью O(n!)</li>

24 </ul>