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