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

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

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

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
}

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

Здесь мы реализовали вспомогательный класс 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 ] ]
// }

Выводы

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

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