Complexidade ciclomática (complexidade)

Question

Tenho um programa para encontrar a distância / caminho mais curto e recebi uma resposta correta, mas estou recebendo um problema, ou seja, "A função 'shortestPath' tem uma complexidade de 9. O máximo permitido é 6." Este é o algoritmo:

const graph = {
  start: { A: 5, D: 8 },
  A: { B: 9, C: 3 },
  D: { C: 4, E: 6 },
  C: { B: 5, E: 2 },
  B: { end: 7 },
  E: { end: 4 },
  end: {}
};

function shortestCostNode(costs, processed) {
  return Object.keys(costs).reduce((lowest, node) => {
    if (lowest === null || costs[node] < costs[lowest]) {
      if (!processed.includes(node)) {
        lowest = node;
      }
    }
    
    return lowest;
  }, null);
}

// this function returns the minimum cost and path to reach end
function shortestPath(graph) {
  // track lowest cost to reach each node
  const costs = Object.assign({ end: Infinity }, graph.start);
  
  const parents = { end: null };
  
  for (let child in graph.start) {
    parents[child] = 'start';
  }
  
  const processed = [];
  let node = shortestCostNode(costs, processed);
  
  while (node) {
    let cost = costs[node];
    let children = graph[node];
    
    for (let n in children) {
      if (children.hasOwnProperty(n)) {
        let newCost = cost + children[n];
        
        if (!costs[n] || costs[n] > newCost) {
          costs[n] = newCost;
          parents[n] = node;
        }
      }
    }
    
    processed.push(node);
    node = shortestCostNode(costs, processed);
  }

  let optimalPath = ["end"];
  let parent = parents.end;
  
  while (parent) {
    optimalPath.push(parent);
    parent = parents[parent];
  }
  
  optimalPath.reverse();

  const result = {
    distance: costs.end,
    path: optimalPath
  };
  return result;
}

Como reduzir a complexidade da função shortestPath?

Answer 1

Complexidade ciclomática

é uma medida do número de caminhos possíveis por meio de algum código. Por exemplo, uma ifdeclaração com uma cláusula, por exemplo, if (foo) {}tem dois caminhos, um se foo for verdadeiro e outro se falso. Qualquer ponto onde o código pode se ramificar, os ramos são contados como parte da complexidade ciclomática.

Infelizmente, como a complexidade é somada difere, portanto, sem saber como a métrica foi calculada, não há uma maneira fácil de dar uma resposta. O melhor que você pode fazer é reduzir o número de ramificações possíveis no código.

Melhorar o código

Olhando para o seu código, há muito espaço para reduzir o número de branches.

A função shortestCostNodenão é necessária, pois o link mais curto em um nó não tem influência no resultado final. O link mais curto pode muito bem levar você ao caminho mais longo. Pesquisar pelo link mais curto não é uma melhoria na seleção de nós sequencialmente.

shortestCostNodeé a principal fonte de complexidade da sua solução, ele randomiza efetivamente a sua pesquisa. Por isso, você deve rastrear qual caminho percorreu para não acabar repetindo o mesmo caminho, isso adiciona muita bagagem.

Se você pesquisar sistematicamente todos os caminhos possíveis em ordem (mantendo o controle de onde você não esteve), você elimina a necessidade de rastrear onde esteve e pode, assim, remover uma grande quantidade de código.

Use uma pilha para pesquisar uma árvore

Como a busca pelo caminho mais curto envolve viajar ao longo de caminhos e depois voltar para o galho não percorrido mais próximo, uma pilha é a melhor maneira de acompanhar seu progresso.

Você começa em um nó, empurra todos os caminhos e o custo até a pilha e, em seguida, abre um caminho e se move ao longo desse caminho para o próximo nó, adicionando o custo conforme você faz. Em seguida, faça o mesmo para o próximo nó.

Ao chegar a um nó final, você verifica a distância e, se for o mais curto até agora, você salva essa distância e o caminho percorrido. Em seguida, puxe a próxima etapa do caminho da pilha até que todos os caminhos tenham sido verificados.

Uma pilha recursiva

A maneira mais simples (mas não a mais rápida) de implementar uma pilha é por meio de recursão.

Assim, você acaba com uma função parecida com

function shortestPath(graph) {
    const result = {distance: Infinity}, endName = "end";
    function followPath(node, totalDist = 0, path = ["start"]) {
        for (const [name, length] of Object.entries(node)) {
            const distance = totalDist + length;
            if (distance < result.distance) {
                if (name === endName) {  
                    Object.assign(result, {distance, path: [...path, endName]}); 
                } else {
                    path.push(name);
                    followPath(graph[name], distance, path);
                    path.pop();
                }
            }
        }
    }
    followPath(graph.start);
    return result;
}

A função tem uma complexidade ciclomática de cerca de 5.

Observe que a função só segue caminhos enquanto a distância percorrida é menor que o caminho mais curto já encontrado. Isso significa que você pode não precisar verificar todos os caminhos até o fim.

Também há muito espaço para melhorias (em termos de complexidade e desempenho), mas como você não definiu muito sobre a possível estrutura dos gráficos, não vale a pena continuar.

Answer 2

const vs let

Em primeiro lugar, gostaria de aplaudir o uso de constem alguns lugares. No entanto, existem lugares onde constpoderia ser usado em vez de let- por exemplo optimalPath, para , uma vez que nunca é reatribuído. É aconselhável usar como padrão conste depois mudar para letquando a reatribuição for considerada necessária. Isso ajuda a evitar a reatribuição acidental e outros bugs .

Adicionando a optimalPath

Em vez de chamar push()para adicionar itens optimalPathe depois chamar reverse, o unshift()método pode ser usado para adicionar itens ao início da matriz, o que elimina a necessidade de inverter a matriz.

Iterando em shortestCostnode()

Observe a documentação MDN para Array.prototype.reduce()- para o parâmetroinitialValue

initialValue Optional
Um valor a ser usado como o primeiro argumento para a primeira chamada docallback. Se nãoinitialValuefor fornecido, o primeiro elemento na matriz será usado como oaccumulatorvaloriniciale ignorado comocurrentValue. Chamar a redução () em uma matriz vazia sem uminitialValuelançará aTypeError.

Isso significa que em vez de passar nullpelo valor inicial, o valor poderia ser omitido para usar o primeiro valor como o valor inicial de loweste ele ignoraria a primeira iteração. Isso eliminaria a necessidade de verificar lowest === nullessa ifcondição.

Memoização

Uma possível otimização é memorizar os resultados - por exemplo, se shortestCostNode()alguma vez for chamado com argumentos duplicados, armazene o valor de retorno calculado para que possa ser pesquisado em chamadas subsequentes e retornado sem a necessidade de recalcular o valor.

Iterando sobre itens filhos

Para o loop dentro do whileloop

for (let n in children) {

      if (children.hasOwnProperty(n)) {

considere usar um for...ofloop combinado comObject.entries(children)

Então, não há necessidade de verificar se a propriedade existe em children( em vez de mais acima na cadeia de protótipos)

for (const [n, child] of Object.entries(children)) {

Isso usa em constvez de `let porque os valores não precisam ser reatribuídos dentro do loop.

Um nome mais apropriado para nseria key:

for (const [key, child] of Object.entries(children)) {