Алгоритм Литтла: реализация в коде — Алгоритмы на графах

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

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

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

Здесь мы реализовали вспомогательный класс 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 &lt; matrix.length; row += 1) {
      for (let column = 0; column &lt; 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 ] ]
// }

Выводы

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

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

---

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты