В этом уроке мы перейдем от теории к практике. Вы узнаете, как реализовать алгоритм Литтла в коде.
Чтобы реализовать алгоритм Литтла, мы написали такой объемный код:
Нажмите, чтобы увидеть код
class Node {
matrix;
bound;
route;
constructor(matrix, bound, route) {
this.matrix = matrix;
this.bound = bound;
this.route = route;
}
static cloneMatrix(matrix) {
return matrix.map((row) => row.slice());
}
static rowMins(matrix) {
const mins = [];
for (let row = 0; row < matrix.length; row += 1) {
mins[row] = matrix[row][0];
}
for (let row = 0; row < matrix.length; row += 1) {
for (let column = 1; column < matrix.length; column += 1) {
if (mins[row] > matrix[row][column]) {
mins[row] = matrix[row][column];
}
}
}
mins.sumFinites = function sumFinites() {
return this.reduce((a, b) => (isFinite(b) ? a + b : a), 0);
};
return mins;
}
static columnMins(matrix) {
const mins = [];
for (let column = 0; column < matrix.length; column += 1) {
mins[column] = matrix[column][0];
}
for (let row = 1; row < matrix.length; row += 1) {
for (let column = 0; column < matrix.length; column += 1) {
if (mins[column] > matrix[row][column]) {
mins[column] = matrix[row][column];
}
}
}
mins.sumFinites = function sumFinites() {
return this.reduce((a, b) => (isFinite(b) ? a + b : a), 0);
};
return mins;
}
static reduceRows(matrix, mins) {
for (let row = 0; row < matrix.length; row += 1) {
for (let column = 0; column < matrix.length; column += 1) {
if (isFinite(mins[row])) {
matrix[row][column] = matrix[row][column] - mins[row];
}
}
}
}
static reduceColumns(matrix, mins) {
for (let row = 0; row < matrix.length; row += 1) {
for (let column = 0; column < matrix.length; column += 1) {
if (isFinite(mins[column])) {
matrix[row][column] = matrix[row][column] - mins[column];
}
}
}
}
static reduce(matrix) {
const rowMins = Node.rowMins(matrix);
Node.reduceRows(matrix, rowMins);
const columnMins = Node.columnMins(matrix);
Node.reduceColumns(matrix, columnMins);
return rowMins.sumFinites() + columnMins.sumFinites();
}
getCellWithMaxPenalty() {
let maxPenalty = -Infinity;
let cellWithMaxPenalty = null;
for (let row = 0; row < this.matrix.length; row += 1) {
for (let column = 0; column < this.matrix.length; column += 1) {
if (this.matrix[row][column] === 0) {
let rowMin = Infinity;
for (let i = 0; i < this.matrix.length; i += 1) {
if (!isFinite(this.matrix[row][i]) || i === column) {
continue;
}
if (rowMin > this.matrix[row][i]) {
rowMin = this.matrix[row][i];
}
}
let columnMin = Infinity;
for (let i = 0; i < this.matrix.length; i += 1) {
if (!isFinite(this.matrix[i][column]) || i === row) {
continue;
}
if (columnMin > this.matrix[i][column]) {
columnMin = this.matrix[i][column];
}
}
const penalty = rowMin + columnMin;
if (maxPenalty < penalty) {
maxPenalty = penalty;
cellWithMaxPenalty = [row, column, maxPenalty];
}
}
}
}
return cellWithMaxPenalty;
}
}
const isFinite = (value) => Number.isFinite(value);
const findNextStartCity = (edges, startCity) => {
for (let i = 0; i < edges.length; i += 1) {
if (edges[i][1] === startCity) {
return i;
}
}
return -1;
};
const findNextEndCity = (edges, endCity) => {
for (let i = 0; i < edges.length; i += 1) {
if (edges[i][0] === endCity) {
return i;
}
}
return -1;
};
const getCloseEdges = (route) => {
const result = [];
const edges = [...route];
while (edges.length > 0) {
let length = 1;
let startCity = edges[0][0];
let endCity = edges[0][1];
edges.splice(0, 1);
let index = findNextStartCity(edges, startCity);
while (index !== -1) {
length += 1;
[startCity] = edges[index];
edges.splice(index, 1);
index = findNextStartCity(edges, startCity);
}
index = findNextEndCity(edges, endCity);
while (index !== -1) {
length += 1;
[, endCity] = edges[index];
edges.splice(index, 1);
index = findNextEndCity(edges, endCity);
}
if (length >= 2) {
result.push([endCity, startCity]);
}
}
return result;
};
const makeChildren = (minNode) => {
const [row, column, leftPenalty] = minNode.getCellWithMaxPenalty();
const leftMatrix = Node.cloneMatrix(minNode.matrix);
leftMatrix[row][column] = Infinity;
Node.reduce(leftMatrix);
const leftBound = minNode.bound + leftPenalty;
const leftRoute = [...minNode.route];
const leftChild = new Node(leftMatrix, leftBound, leftRoute);
const rightMatrix = Node.cloneMatrix(minNode.matrix);
rightMatrix[column][row] = Infinity;
for (let i = 0; i < rightMatrix.length; i += 1) {
rightMatrix[row][i] = Infinity;
rightMatrix[i][column] = Infinity;
}
const rightRoute = [...minNode.route, [row, column]];
const closeEdges = getCloseEdges(rightRoute);
closeEdges.forEach(([currRow, currEdge]) => {
rightMatrix[currRow][currEdge] = Infinity;
});
const rightPenalty = Node.reduce(rightMatrix);
const rightBound = minNode.bound + rightPenalty;
const rightChild = new Node(rightMatrix, rightBound, rightRoute);
return [leftChild, rightChild];
};
const little = (matrix) => {
const rootMatrix = Node.cloneMatrix(matrix);
const minBound = Node.reduce(rootMatrix);
const root = new Node(rootMatrix, minBound, []);
const priorityQueue = [root];
let record = null;
while (priorityQueue.length > 0) {
let minIndex = 0;
let minNode = priorityQueue[minIndex];
for (let i = 1; i < priorityQueue.length; i += 1) {
if (minNode.bound > priorityQueue[i].bound) {
minNode = priorityQueue[i];
minIndex = i;
}
}
priorityQueue.splice(minIndex, 1);
if (record !== null) {
if (record.length <= minNode.bound) {
break;
}
}
if (minNode.route.length === matrix.length - 2) {
for (let row = 0; row < matrix.length; row += 1) {
for (let column = 0; column < matrix.length; column += 1) {
if (isFinite(minNode.matrix[row][column])) {
minNode.bound += minNode.matrix[row][column];
minNode.route.push([row, column]);
}
}
}
if (record == null || record.length > minNode.bound) {
record = { length: minNode.bound, route: minNode.route };
}
} else {
const [leftChild, rightChild] = makeChildren(minNode);
priorityQueue.push(leftChild);
priorityQueue.push(rightChild);
}
}
return record;
};https://replit.com/@hexlet/algorithms-graphs-littles-algorithm-code
В таком объемном коде сложно разобраться самостоятельно, поэтому мы подробно обсудим, что происходит на каждом шаге.
Здесь мы реализовали вспомогательный класс Node, в котором сосредоточили функции для работы с узлами дерева решений.
JavaScript хранит ссылку на объекты, в том числе на массивы. Если мы хотим создать копию матрицы смежности в каждом узле, мы не можем просто скопировать массив. Нужно создать новый массив и скопировать в него все значения исходного массива.
Матрица — это массив массивов. Поэтому мы выполняем глубокое копирование:
static cloneMatrix(matrix) {
return matrix.map(row => row.slice());
}Еще нам нужно создать две функции:
-
Первая функция будет искать минимумы в каждой строке
-
Вторая — редуцировать, то есть вычитать минимумы из каждого элемента каждой строки
Так выглядит реализация в коде:
static rowMins(matrix) {
const mins = [];
for (let row = 0; row < matrix.length; row += 1) {
mins[row] = matrix[row][0];
}
for (let row = 0; row < matrix.length; row += 1) {
for (let column = 1; column < matrix.length; column += 1) {
if (mins[row] > matrix[row][column]) {
mins[row] = matrix[row][column];
}
}
}
mins.sumFinites = function sumFinites() {
return this.reduce((a, b) => (isFinite(b) ? a + b : a), 0);
};
return mins;
}
static reduceRows(matrix, mins) {
for (let row = 0; row < matrix.length; row += 1) {
for (let column = 0; column < matrix.length; column += 1) {
if (isFinite(mins[row])) {
matrix[row][column] = matrix[row][column] - mins[row];
}
}
}
}Далее мы напишем похожие функции и для столбцов. Затем реализуем метод редуцирования матрицы и по строкам и по столбцам:
static reduce(matrix) {
const rowMins = Node.rowMins(matrix);
Node.reduceRows(matrix, rowMins);
const columnMins = Node.columnMins(matrix);
Node.reduceColumns(matrix, columnMins);
return rowMins.sumFinites() + columnMins.sumFinites();
}Последний метод в классе Node — это getCellWithMaxPenalty. Он находит ячейку матрицы с наибольшим штрафом.
Как мы помним, метод пробегает по всем нулевым элементам и складывает минимумы в той же строке и в том же столбце. При вычислении минимума сам элемент не учитывается:
getCellWithMaxPenalty() {
let maxPenalty = -Infinity;
let cellWithMaxPenalty = null;
for (let row = 0; row < this.matrix.length; row += 1) {
for (let column = 0; column < this.matrix.length; column += 1) {
if (this.matrix[row][column] === 0) {
let rowMin = Infinity;
for (let i = 0; i < this.matrix.length; i += 1) {
if (!isFinite(this.matrix[row][i]) || i === column) {
continue;
}
if (rowMin > this.matrix[row][i]) {
rowMin = this.matrix[row][i];
}
}
let columnMin = Infinity;
for (let i = 0; i < this.matrix.length; i += 1) {
if (!isFinite(this.matrix[i][column]) || i === row) {
continue;
}
if (columnMin > this.matrix[i][column]) {
columnMin = this.matrix[i][column];
}
}
const penalty = rowMin + columnMin;
if (maxPenalty < penalty) {
maxPenalty = penalty;
cellWithMaxPenalty = [row, column, maxPenalty];
}
}
}
}
return cellWithMaxPenalty;
}
}Во время работы алгоритма Литтла мы должны исключить из рассмотрения закрывающие ребра — те, которые могут завершить маршрут раньше времени.
Для поиска закрывающих ребер напишем функцию getCloseEdges. Для ее работы реализуем вспомогательные функции findNextStartCity и findNextEndCity:
const findNextStartCity = (edges, startCity) => {
for (let i = 0; i < edges.length; i += 1) {
if (edges[i][1] === startCity) {
return i;
}
}
return -1;
};
const findNextEndCity = (edges, endCity) => {
for (let i = 0; i < edges.length; i += 1) {
if (edges[i][0] === endCity) {
return i;
}
}
return -1;
};
const getCloseEdges = (route) => {
const result = [];
const edges = [...route];
while (edges.length > 0) {
let length = 1;
let startCity = edges[0][0];
let endCity = edges[0][1];
edges.splice(0, 1);
let index = findNextStartCity(edges, startCity);
while (index !== -1) {
length += 1;
[startCity] = edges[index];
edges.splice(index, 1);
index = findNextStartCity(edges, startCity);
}
index = findNextEndCity(edges, endCity);
while (index !== -1) {
length += 1;
[, endCity] = edges[index];
edges.splice(index, 1);
index = findNextEndCity(edges, endCity);
}
if (length >= 2) {
result.push([endCity, startCity]);
}
}
return result;
};На каждом шаге алгоритма мы строим левое и правое поддеревья из какого-то узла дерева решений.
Вынесем код построения в функцию makeChildren. Используем написанные нами ранее методы и функции — getCellWithMaxPenalty, cloneMatrix и reduce:
const makeChildren = (minNode) => {
const [row, column, leftPenalty] = minNode.getCellWithMaxPenalty();
const leftMatrix = Node.cloneMatrix(minNode.matrix);
leftMatrix[row][column] = Infinity;
Node.reduce(leftMatrix);
const leftBound = minNode.bound + leftPenalty;
const leftRoute = [...minNode.route];
const leftChild = new Node(leftMatrix, leftBound, leftRoute);
const rightMatrix = Node.cloneMatrix(minNode.matrix);
rightMatrix[column][row] = Infinity;
for (let i = 0; i < rightMatrix.length; i += 1) {
rightMatrix[row][i] = Infinity;
rightMatrix[i][column] = Infinity;
}
const rightRoute = [...minNode.route, [row, column]];
const closeEdges = getCloseEdges(rightRoute);
closeEdges.forEach(([currRow, currEdge]) => {
rightMatrix[currRow][currEdge] = Infinity;
});
const rightPenalty = Node.reduce(rightMatrix);
const rightBound = minNode.bound + rightPenalty;
const rightChild = new Node(rightMatrix, rightBound, rightRoute);
return [leftChild, rightChild];
};Наконец, реализуем функцию little. В стандартной библиотеке JavaScript нет структуры данных, которая представляла бы очередь с приоритетами. Поэтому мы сделаем собственную простую структуру и будем выбирать узел с наименьшей нижней границей каждом шаге алгоритма:
const little = (matrix) => {
const rootMatrix = Node.cloneMatrix(matrix);
const minBound = Node.reduce(rootMatrix);
const root = new Node(rootMatrix, minBound, []);
const priorityQueue = [root];
let record = null;
while (priorityQueue.length > 0) {
let minIndex = 0;
let minNode = priorityQueue[minIndex];
for (let i = 1; i < priorityQueue.length; i += 1) {
if (minNode.bound > priorityQueue[i].bound) {
minNode = priorityQueue[i];
minIndex = i;
}
}
priorityQueue.splice(minIndex, 1);
if (record !== null) {
if (record.length <= minNode.bound) {
break;
}
}
if (minNode.route.length === matrix.length - 2) {
for (let row = 0; row < matrix.length; row += 1) {
for (let column = 0; column < matrix.length; column += 1) {
if (isFinite(minNode.matrix[row][column])) {
minNode.bound += minNode.matrix[row][column];
minNode.route.push([row, column]);
}
}
}
if (record == null || record.length > minNode.bound) {
record = { length: minNode.bound, route: minNode.route };
}
} else {
const [leftChild, rightChild] = makeChildren(minNode);
priorityQueue.push(leftChild);
priorityQueue.push(rightChild);
}
}
return record;
};
const matrix = [
[Infinity, 27, 43, 16, 30, 26],
[7, Infinity, 16, 1, 30, 25],
[20, 13, Infinity, 35, 5, 0],
[21, 16, 25, Infinity, 18, 18],
[12, 46, 27, 48, Infinity, 5],
[23, 5, 5, 9, 5, Infinity]
];
console.log(little(matrix)); // {
// length: 63,
// route: [ [ 0, 3 ], [ 1, 0 ],
// [ 4, 5 ], [ 2, 4 ],
// [ 3, 2 ], [ 5, 1 ] ]
// }Выводы
В этом уроке мы закончили изучать алгоритм Литтла. Теперь вы знаете, как он работает в теории и как реализовать его в коде. Повторим ключевые выводы, к которым мы пришли в прошлом теоретическом уроке:
-
Алгоритм Литтла находит оптимальное решение в дереве решений
-
Для работы алгоритма важно, чтобы оценка нижней границы была корректной
-
Обычно алгоритм Литтла работает быстрее метода перебора, в худшем случае — с той же скоростью
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
