Pular para o conteúdo
</> Entendendo Algoritmos

Algoritmo guloso

A cada passo, escolhe a melhor opção do momento, sem olhar o quadro todo. Aqui: cobertura de conjuntos. Achar a solução exata exige testar todas as combinações (O(2ⁿ)); o guloso é uma aproximação rápida (O(n²)).

Explicação do algoritmo: escolha um nível para ler.

{ }Ver o código
function coberturaGulosa(universo, conjuntos) {
  const faltam = new Set(universo);
  const escolhidos = [];

  while (faltam.size > 0) {
    // o conjunto que cobre mais itens ainda não cobertos
    let melhor = null;
    let melhorQtd = 0;
    for (const [nome, itens] of Object.entries(conjuntos)) {
      const novos = itens.filter((i) => faltam.has(i)).length;
      if (novos > melhorQtd) {
        melhor = nome;
        melhorQtd = novos;
      }
    }

    if (melhor === null) break;   // sobrou algo que nenhum conjunto cobre
    escolhidos.push(melhor);
    conjuntos[melhor].forEach((i) => faltam.delete(i));
  }

  return escolhidos;
}

Cada estação cobre alguns estados. Meta: cobrir todos os estados com o menor número de estações.

Itens a cobrir
mtwaoridnvutcaaz