segunda-feira, 25 de maio de 2009

Usando BFS para resolver o problema do troco

Um problema clássico em computação é o problema de determinar o numero mínimo de moedas que pode ser usado para se completar uma determinada quantia a ser passada como troco. Neste post, vou apresentar uma aplicação interessante do BFS na resolução desse problema.

Sim, sim, o BFS resolve problemas que tu nem imaginas.

Não sou muito bom em PD. Por isso, abordagens que utilizem conceitos de teoria de grafos sempre me atraem mais. O BFS é meu algoritmo favorito da teoria de grafos, porque possui uma semelhança muito grande com o algoritmo de Prim e com o algoritmo de Dijkstra. Além de ser bunitin [=)].

Agora, como usar o BFS para resolver o problema do troco?

Assim oh. Cada valor se torna um vértice, e as arestas são definidas usando os tipos de moedas que você tem disponivel. Suponho que você pode usar um determinado tipo de moeda quantas vezes quiser. Assim, quando queremos saber o numero minimo de moedas que devemos usar, podemos usar um BFS no grafo que representa os valores que se pode chegar a partir de um determinado valor usando-se os tipos de moedas que você tem a sua disposição. Como no caso do grafo de estados, esse grafo não precisa construido explicitamente. O vértice inicial do BFS é o valor 0 e o vértice final é a quantia que queremos alcançar. Sabendo-se disso, algoritmo fica com o seguinte formato:
Algoritmo MinTroco(T, moeda[] , n) {

    input: T é o total que se deseja pagar, moeda é um vetor com os tipos de 
moedas que você pode usar, n é o numero de tipo de moedas.
    output: Numero mínimo de moedas que pode ser usado.

    Q=vazio;//Como na BFS Q é uma fila
    d=INF;//Inicialize o vetor de distâncias com tudo INF
    Q.push(0);//Insira no fim da fila o vertice inicial
    d[0]=0;//Sete a distancia do vertice inicial para 0

    while (!Q.empty()) {
        u=Q.front(); Q.pop();
        if(u==T)  break;
        du=d[u]+1;

        for (i=0; i < n; i++) {
            v=u+moeda[i];
            if(du < d[v]){
                d[v]=du;
                Q.push(v);
            }
        }

    }

    return d[T]; 
}
É bem legal o poder que o BFS tem, tanto que se você ver problemas com estruturas semelhantes ao do problema do troco, tente ver se não se pode encaixar o BFS ou o Dijkstra. Como lista de exercício deixo o MOEDAS e o ZAK GALOU. Com essa abordagem, o tempo de execução fica mais rápido que usando abordagens mais tradicionais. Boa Sorte!

4 comentários:

  1. Consigo resolver com BFS o problema Moedas?
    Ainda não consigo entender PD, e BFS eu tambem gosto de implementar eh facil.
    Poderia explicar melhor como funcionaria para o problema Moedas?

    ResponderExcluir
  2. Qual seria o vértice final? O que fazer se u+moeda[i]>T(valor a ser alcançado)?

    Desenha o algoritmo executando, vai te ajudar a entender melhor. Tipo constrói o grafo para esse caso e execute o algoritmo.

    Moedas disponiveis: 2 33 1 31
    Valor a ser alcançado: 90

    Quantas moedas vou precisar no minimo?
    Como ficaria o grafo?

    ResponderExcluir