Как перебрать объект, содержащий 2D-массивы, не получая O (n) ^ 3?

Question

Надеюсь, это не слишком конкретный вопрос c, но я надеюсь получить представление о том, как работать с вложенными объектами и массивами, не создавая программу, которая запускает O (n) ^ 2 или O (n). ^ 3.

Ниже приведена программа, которую я построил, чтобы найти самый дешевый рейс (ы) из пункта А в пункт Б, и, если стоимость полета такая же, как и у наименьшего количества рейсов. Вы увидите, где я маркирую части, которые не эффективны. Как я могу сделать это более эффективным?

//returns an object with an array of IDs that will get you to a destination at the lowest cost. if same cost, then the least amount of flights flights

function leastExpensiveFlight(flightInfo, start, end) {
  var numOfTimes = 1
  var combinedValues = []
  var minValue
  var indexOfMinValue;
  var numOfFlights = []
  var minNumberOfFlights;
  var startTimes = flightInfo.reduce((startTimes, f, index) => {
    if (f[0] == start) {
      startTimes[numOfTimes] = [f];
      numOfTimes++
    }
    return startTimes
  }, {})
  //below is O(n)^2  
  //Gets the Flights where Location 1 = start 
  for (i = 0; i < Object.keys(startTimes).length; i++) {
    for (j = 0; j < startTimes[Object.keys(startTimes)[i]].length; j++) {
      flightInfo.forEach((f, ) => {
        if (startTimes[Object.keys(startTimes)[i]][j] &&
          f[0] === startTimes[Object.keys(startTimes)[i]][j][1] &&
          startTimes[Object.keys(startTimes)[i]][j][1] <= end &&
          f[1] <= end) {
          if (!startTimes[Object.keys(startTimes)[i]].includes(f)) {
            startTimes[Object.keys(startTimes)[i]].push(f)
          }
        }
      })
    }
  }
  //below is O(n)^3!!
  //Finds trips that will get to the destination
  Object.keys(startTimes).forEach((flights) => {
    startTimes[flights].forEach((subFlights1, sFIndex1) => {
      startTimes[flights].forEach((subFlights2, sFIndex2) => {
        if (subFlights1[0] === subFlights2[0] &&
          subFlights1[1] === subFlights2[1] &&
          sFIndex1 != sFIndex2) {
          if (subFlights1[2] >= subFlights2[2]) {
            startTimes[flights].splice(sFIndex1, 1)
          } else {
            startTimes[flights].splice(sFIndex2, 1)
          }
        }
      })
    })
  })
  //below is O(n)^2  
  //Finds the trip with the minimum value and, if same price, least amount of flights
  Object.keys(startTimes).forEach((flights, sTIndex) => {
    startTimes[flights].forEach((subFlights, sFIndex) => {
      if (sFIndex == 0) {
        combinedValues[sTIndex] = subFlights[2]
        numOfFlights.push(1)
      } else {
        combinedValues[sTIndex] += subFlights[2]
        numOfFlights[sTIndex] += 1
      }
      if (sFIndex === startTimes[flights].length - 1 &&
        ((combinedValues[sTIndex] <= minValue) ||
          !minValue)) {
        if ((!minNumberOfFlights ||
            minNumberOfFlights > numOfFlights[sTIndex])) {
          minNumberOfFlights = numOfFlights[sTIndex]
        }
        if (combinedValues[sTIndex] === minValue &&
          numOfFlights[sTIndex] === minNumberOfFlights ||
          (combinedValues[sTIndex] < minValue &&
            numOfFlights[sTIndex] >= minNumberOfFlights) ||
          !minValue) {
          minValue = combinedValues[sTIndex];
          indexOfMinValue = sTIndex
        }
      }
    })
  })

  return startTimes[Object.keys(startTimes)[indexOfMinValue]]
} //Big O is O(n)^3

//2D Array: data[0][0] = Location start,
//          data[0][1] = Location end,
//          data[0][2] = Price,
//          
var data = [
  [4, 5, 400],
  [1, 2, 500],
  [2, 3, 300],
  [1, 3, 900],
  [2, 3, 100],
  [3, 4, 400]
]

//so from location 1 - location 3, the cheapest route would be: [1,2,500],[2,3,100]
console.log(JSON.stringify(leastExpensiveFlight(data, 1, 3)));

Ваша помощь очень ценится. Я пытаюсь стать лучше в кодировании, чтобы я мог go войти в свой инженерный отдел, но, как вы видите, мне еще далеко до go.

[EDIT] - Извините, произошел ошибочный утверждение там, которое я только что исправил.

Answer 1

Я бы подошел к этому, сначала построив график для каждого возможного пути между начальным и конечным узлами. Создайте функцию, которая с учетом начального узла и списка уже посещенных узлов может просматривать данные, чтобы найти каждый путь, ведущий из этого узла. Для каждого пути, который еще не посещен , а не , если путь заканчивается в месте назначения, pu sh весь результат путей, пройденных в массиве finishedPaths. В противном случае рекурсивно вызовите функцию, чтобы она снова выполняла тот же процесс, начиная с конечного узла.

Чтобы уменьшить сложность, чтобы определить, посещался ли узел или нет, используйте объект или набор (которые имеют поиск во время O(1), в отличие от Array.prototype.includes, который выполняется во время O(n)).

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

function leastExpensiveFlight(data, start, end) {
  const pathsByStartLoc = {};
  for (const path of data) {
    const start = path[0];
    if (!pathsByStartLoc[start]) pathsByStartLoc[start] = [];
    pathsByStartLoc[start].push(path);
  }
  const getAllPaths = (
    start,
    costSoFar = 0,
    pathsSoFar = [],
    finishedPaths = [],
    visitedNodes = {}
  ) => {
    if (!pathsByStartLoc[start]) return;
    for (const path of pathsByStartLoc[start]) {
      if (visitedNodes.hasOwnProperty(path[2])) continue;
      if (path[1] === end) {
        finishedPaths.push({ totalCost: costSoFar + path[2], paths: [...pathsSoFar, path] });
      }
      getAllPaths(
        path[1],
        costSoFar + path[2],
        [...pathsSoFar, path],
        finishedPaths, { ...visitedNodes, [path[0]]: true }
      );
    }
    return finishedPaths;
  };
  const allPaths = getAllPaths(start);
  const lowestCost = Math.min(...allPaths.map(({ totalCost }) => totalCost));
  const lowestCostPaths = allPaths.filter(({ totalCost }) => totalCost === lowestCost);
  return lowestCostPaths.reduce((a, item) => a.paths.length < item.paths.length ? a : item);
}       
var data = [
  [4, 5, 400],
  [1, 2, 500],
  [2, 3, 300],
  [1, 3, 900],
  [2, 3, 100],
  [3, 4, 400]
]

//so from location 1 - location 3, the cheapest route would be: [1,2,500],[2,3,300]
console.log(leastExpensiveFlight(data, 1, 3));