A seguir está a versão em Markdown com o máximo de conteúdo extraído do PDF ****, preservando títulos, explicações, fórmulas, pseudocódigo e código Java.

---

Projeto de Algoritmos: Algoritmos Gulosos

Disciplina: ACH2002 - Introdução à Ciência da Computação II Autor: Delano M. Beder Instituição: Escola de Artes, Ciências e Humanidades (EACH) - USP Data: 09/2008

---

Algoritmos Gulosos: Conceitos Básicos

Tipicamente, algoritmos gulosos são utilizados para resolver:

• problemas de otimização

Um algoritmo guloso:

• sempre faz a escolha que parece ser a melhor a cada iteração
• utiliza um critério guloso
• toma uma decisão localmente ótima

---

Propriedade da Escolha Gulosa

A propriedade da escolha gulosa afirma que:

a cada iteração é tomada uma decisão que levará a um ótimo global.

Além disso:

• uma escolha feita nunca é revista
• não há backtracking

---

Algoritmos Gulosos: Ideias Básicas

A estratégia gulosa consiste em:

construir por etapas uma solução ótima.

Em cada passo:

1. seleciona-se um elemento da entrada
2. verifica-se se ele é viável
3. se for viável, ele passa a fazer parte da solução
4. caso contrário, é descartado

Após uma sequência de decisões:

• uma solução para o problema é obtida

Importante:

• nenhum elemento é examinado mais de uma vez
• ou ele entra na solução
• ou é descartado definitivamente

Observação:

• frequentemente a entrada do problema já vem ordenada

---

Exemplo: Intercalação (Fusão) de Vetores

Foi apresentado um método para fusão de dois vetores ordenados.

Código Java

int[] intercalacao(int[] a, int[] b) {

    int posa = 0,
        posb = 0,
        posc = 0;

    int[] c = new int[a.length + b.length];

    // Enquanto nenhuma das sequências está vazia...
    while (posa < a.length && posb < b.length) {

        // Pega o menor elemento das duas sequências
        if (b[posb] <= a[posa]) {
            c[posc] = b[posb];
            posb++;
        } else {
            c[posc] = a[posa];
            posa++;
        }

        posc++;
    }

---

Intercalação de Vetores (Continuação)

    // Completa com a sequência que ainda não acabou
    while (posa < a.length) {
        c[posc] = a[posa];
        posc++;
        posa++;
    }

    while (posb < b.length) {
        c[posc] = b[posb];
        posc++;
        posb++;
    }

    return c; // retorna o valor resultado da intercalação
}

---

Intercalação Sucessiva de Vetores

Problema:

• existem (n) vetores
• é necessário intercalá-los sucessivamente

Há várias ordens possíveis de intercalação.

Entretanto:

a ordem escolhida altera o número total de comparações.

---

Número de Comparações para Dois Vetores

Se dois vetores possuem tamanhos:

• (m_1)
• (m_2)

Então:

• o vetor resultante terá tamanho (m_1 + m_2)
• o número máximo de comparações será:

[ m_1 + m_2 - 1]

---

Exemplo com Três Vetores

Considere três vetores:

• (V_1) com tamanho 15
• (V_2) com tamanho 10
• (V_3) com tamanho 5

---

Opção 1: Intercalar V1 e V2 primeiro

Primeiro:

[ V_1 + V_2 V_{12}]

Número de comparações:

[ 15 + 10 - 1 = 24]

Depois:

[ V_{12} + V_3]

Número de comparações:

[ (15 + 10) + 5 - 1 = 29]

Total:

[ 24 + 29 = 53]

---

Opção 2: Intercalar V2 e V3 primeiro

Primeiro:

[ V_2 + V_3 V_{23}]

Número de comparações:

[ 10 + 5 - 1 = 14]

Depois:

[ V_{23} + V_1]

Número de comparações:

[ (10 + 5) + 15 - 1 = 29]

Total:

[ 14 + 29 = 43]

---

Opção 3: Intercalar V1 e V3 primeiro

Primeiro:

[ V_1 + V_3 V_{13}]

Número de comparações:

[ 15 + 5 - 1 = 19]

Depois:

[ V_{13} + V_2]

Número de comparações:

[ (15 + 5) + 10 - 1 = 29]

Total:

[ 19 + 29 = 48]

---

Comparação Entre Estratégias

Resumo:

Ordem	Comparações
(V_1 + V_2), depois (V_3)	53
(V_2 + V_3), depois (V_1)	43
(V_1 + V_3), depois (V_2)	48

Conclusão:

o primeiro par escolhido influencia fortemente o número total de comparações.

---

Fórmulas Gerais

Caso 1

[ V_1 + V_2 V_{12}]

Depois:

[ V_{12} + V_3]

Total:

[ (m_1 + m_2 - 1) + (m_1 + m_2 + m_3 - 1)]

[ 2(m_1 + m_2) + m_3 - 2]

---

Caso 2

[ V_2 + V_3 V_{23}]

Depois:

[ V_{23} + V_1]

Total:

[ (m_2 + m_3 - 1) + (m_2 + m_3 + m_1 - 1)]

[ 2(m_2 + m_3) + m_1 - 2]

---

Caso 3

[ V_1 + V_3 V_{13}]

Depois:

[ V_{13} + V_2]

Total:

[ (m_1 + m_3 - 1) + (m_1 + m_3 + m_2 - 1)]

[ 2(m_1 + m_3) + m_2 - 2]

---

Estratégia Gulosa para Intercalação

A estratégia gulosa consiste em:

selecionar, a cada passo, os dois menores vetores disponíveis.

Essa escolha minimiza o impacto do fator multiplicativo nas comparações futuras.

---

Exemplo da Estratégia Gulosa

Tamanhos iniciais dos vetores:

10 20 30 40 50

Primeira escolha:

10 + 20 = 30

Novo conjunto:

30 30 40 50

Segunda escolha:

30 + 30 = 60

Novo conjunto:

40 50 60

Terceira escolha:

40 + 50 = 90

Novo conjunto:

60 90

Última escolha:

60 + 90 = 150

---

Procedimento: Intercalação Ótima de Vetores

procedimento intercala_ótima_vetores

Entrada:
    Conjunto V de n vetores (com seus tamanhos)

Saída:
    par (intercalação dos n vetores, número de comparações)

BEGIN

numCmp = 0;

REPITA

    escolhe os dois menores vetores A e B (seleção gulosa)

    V = V - {A, B};

    C = Intercala(A, B);

    V = V + {C};

    numCmp = numCmp + tam(A) + tam(B) - 1

ATÉ QUE |V| = 1;

retorne_saída(V, numCmp);

END

---

Implementação em Java

int[] merge(int[][] conjunto) {

    int tam = conjunto.length;
    int numCmp = 0;

    do {

        // escolhe os dois menores vetores A e B
        Menores menores = menoresVetores(conjunto);

        int prim = menores.getPrimeiro();
        int seg = menores.getSegundo();

        int[] A = conjunto[prim];
        int[] B = conjunto[seg];

        // V = V - A, B
        conjunto = removeVetores(conjunto, menores);

        // C = Intercala(A, B)
        int[] C = merge(A, B);

        // V = V + C
        conjunto[tam - 2] = C;

        numCmp = numCmp + A.length + B.length - 1;

        tam = tam - 1;

    } while (tam > 1);

    System.out.println(
        "Foram feitas " + numCmp + " Comparações"
    );

    return conjunto[0];
}

---

Resumo

Foi apresentada a técnica de projeto de algoritmos baseada em algoritmos gulosos.

A ideia central é:

• construir uma solução ótima por etapas
• escolher sempre a melhor alternativa local
• nunca reconsiderar escolhas anteriores

Processo:

1. escolher um elemento
2. verificar viabilidade
3. adicionar ou descartar
4. repetir até formar a solução

---

Referências

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein. Algoritmos - Tradução da 2ª Edição Americana. Editora Campus, 2002.

2. Laira V. Toscani e Paulo A. S. Veloso. Complexidade de Algoritmos. Série Livros Didáticos, Instituto de Informática da UFRGS, 2ª edição, 2005.