Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Sign in to follow this  
Localhost

BFS - Implementação

Recommended Posts

Localhost

Tenho estado a treinar BFS.

Implementei com o seguinte problema:

- Dados um set S e um número inteiro K, calcular K no menor número de somas possível somando os elementos de S.

Estive mesmo agora a implementar e deu-me algum trabalho, demorei cerca de 15min. a implementar, acham que é razoável para um concurso?

Senti-me um pouco desiludido pelo facto de o BFS não ter superado *por muito* o DFS neste problema ao nível de eficiência.

Deixo aqui o código:

#include <stdio.h>
#include <stdlib.h>

#define MAX 2

typedef struct q{
    int sum,level;
    struct q *next;
}Queue;

void enqueue(int s, int l, Queue *head) {
    Queue *new = (Queue *)malloc(sizeof(Queue));
    new->sum=s;
    new->level=l;
    new->next=NULL;
    while(head->next != NULL) head=head->next;
    head->next=new;
}

Queue *dequeue(int *s, int *l, Queue *head) {
    Queue *aux=head;
    *s=head->sum;
    *l=head->level;
    head=head->next;
    free(aux);
    return head;
}

int is_empty(Queue *head) {
    if(head==NULL) return 1;
    else return 0;
}

Queue *init_queue(Queue *head, int *set) {
    int k=0;
    Queue *aux=NULL, *new=NULL;;
    for(k=0; k < MAX; k++) {
        new=(Queue *) malloc(sizeof(Queue));
        new->sum=set[k];
        new->level=0;
        new->next=NULL;
        if(head == NULL) {
            head=new;
            aux=head;
        }else {
            head->next=new;
            head=head->next;
        }
    }
    return aux;
}

int bfs(int *set, int goal) {
    int k=0, sum=0, level=0;
    Queue *head=NULL;
    head=init_queue(head,set);
    while(!is_empty(head)) {
        head=dequeue(∑,&level,head);
        if(sum==goal) return level;
        for(k=0; k < MAX; k++) {
            if(sum+set[k] <= goal) enqueue(sum+set[k],level+1,head);
        }
    }
    return 0;
}

int main(void) {
    int set[] = {1,2}, K=20;
    printf("%i\n", bfs(set,K)+1);
    return 0;
}

Como podem ver o código deu muito grande num problema simples como este, visto que tive de trabalhar com listas ligadas para armazenar a informação sobre cada membro da queue.

Espero algum feedback sobre o código.


here since 2009

Share this post


Link to post
Share on other sites
Localhost

Ok, lembrei-me de um pormenor que estava a estragar a eficiência toda do BFS que era, na função enqueue ele receber o inicio da lista ligada e não o fim, ou seja, para cada adição de um elemento à queue ele tinha de percorrer a mesma até ao fim e só depois adicionar os dados.

Agora que já melhorei isso ele resolve os casos todos em < 1seg.

Deixo aqui o código:

#include <stdio.h>
#include <stdlib.h>

#define MAX 2

typedef struct q{
    int sum,level;
    struct q *next;
}Queue;

Queue *enqueue(int s, int l, Queue *tail) {
    Queue *new = (Queue *)malloc(sizeof(Queue));
    new->sum=s;
    new->level=l;
    new->next=NULL;
    tail->next=new;
    return tail->next;
}

Queue *dequeue(int *s, int *l, Queue *head) {
    Queue *aux=head;
    *s=head->sum;
    *l=head->level;
    head=head->next;
    free(aux);
    return head;
}

int is_empty(Queue *head) {
    if(head==NULL) return 1;
    else return 0;
}

Queue *init_queue(Queue *head, int *set) {
    int k=0;
    Queue *aux=NULL, *new=NULL;
    for(k=0; k < MAX; k++) {
        new=(Queue *) malloc(sizeof(Queue));
        new->sum=set[k];
        new->level=0;
        new->next=NULL;
        if(head == NULL) {
            head=new;
            aux=head;
        }else {
            head->next=new;
            head=head->next;
        }
    }
    return aux;
}

int bfs(int *set, int goal) {
    int k=0, sum=0, level=0;
    Queue *head=NULL,*tail=NULL;
    head=init_queue(head,set);
    tail=head;
    while(tail->next != NULL) tail=tail->next;
    while(!is_empty(head)) {
        head=dequeue(∑,&level,head);
        if(sum==goal) return level;
        for(k=0; k < MAX; k++) {
            if(sum+set[k] <= goal) tail=enqueue(sum+set[k],level+1,tail);
        }
    }
    return 0;
}

int main(void) {
    int set[] = {1,2}, K=20;
    printf("%i\n", bfs(set,K)+1);
    return 0;
}

Comentem este código em vez do outro e digam-me se posso optimizar mais alguma coisa.  :)


here since 2009

Share this post


Link to post
Share on other sites
Warrior

Normalmente não precisas de criar uma queue com uma lista ligada.

Sabes o número máximo de elementos que podem passar pela queue, podes criar um array de elementos e guardar o índice do primeiro e do último elemento.

Alternativamente, aprende C++. É algo que recomendo veementemente a quem quer participar em concursos.

Mesmo que não queiras aprender tudo de C++ (a maior parte é inútil em concursos) aprende a usar STL.

Neste caso, todo o código seria igual, exceptuando que declararias uma variável:

Queue<int> queue;

e fazias queue.push() queue.top() e queue.pop()

Share this post


Link to post
Share on other sites
mogers

Demasiado java pá cabeça ultimamente? :)

Em C++ seria

queue<int> fila;  // nota o q em minuscula

e fazias queue.push() queue.front() e queue.pop()

Concordo plenamente com o Warrior, ou usas um array em C, ou a classe queue (como uso 99% das vezes) em C++.

http://www.cppreference.com/wiki/stl/queue/start

Btw, esse código resume-se em

// warning, fiz copy e alteração directamente no post, nao compilei
#include <stdio.h>
#include <queue>
using namespace std;

#define MAX 2

struct {
    int sum,level;
} Node;

void enqueue(queue<Node> & q, int s, int l) {
    Node novo;
    novo.sum=s;
    novo.level=l;
    q.push(novo);
}
  
int bfs(int *set, int goal) {
    int k=0, sum=0, level=0;
    queue<Node> q;
    Node head;
    // enqueue do(s) primeiro(s) elemento(s)
    while(! q.empty() ) {
        head=q.front();
        q.pop();
        if(sum==goal) return level;
        for(k=0; k < MAX; k++)
            if(sum+set[k] <= goal) 
                 enqueue(q, sum+set[k],level+1);
    }
    return 0;
}

int main(void) {
    int set[] = {1,2}, K=20;
    printf("%i\n", bfs(set,K)+1);
    return 0;
}


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Warrior

Demasiado java pá cabeça ultimamente? :)

E se eu te disser que fui ao cppreference verificar os métodos és capaz de acreditar?

Não sei como raio fui ver os métodos e depois os troquei.

Share this post


Link to post
Share on other sites
Localhost

Eu posso misturar C++ com C no mesmo código? Por exemplo, posso fazer tudo em C e depois só usar a STL de C++?

E depois para compilar?

Não me agrada muito a ideia de só aprender a STL porque depois não vou saber o que estou a fazer. Prefiro mesmo aprender C++ a fundo e depois sim utilizar C++ para os concursos mas posso sempre ir aprendendo a usar a STL.

Btw, realmente o código ficou mais bonito e limpo, é uma grande diferença. Enquanto um programador que trabalha com C tem que estar a fazer tudo "manualmente" um programador que trabalha com C++ tem o trabalho muito facilitado.

Tenho mesmo que dar o salto para C++.


here since 2009

Share this post


Link to post
Share on other sites
Warrior

De um modo geral, C é um "subconjunto" de C++. As excepções são poucas, podes perfeitamente compilar código C como C++.

Share this post


Link to post
Share on other sites
Localhost

Ok, fiquei esclarecido quanto a essa dúvida.

Agora, um pequeno off-topic (só mesmo para não andar a criar tópicos a torto e a direito), como é que eu com dfs, por exemplo, dado um set imprimir todos os subsets desse set, como é que eu posso limitar o número de vezes que cada elemento do set aparece no subset?

Eu pensei que se fazia assim:

for(k=0; k < 2; k++) {
  if(tm[k] < 3) {
     tm[k]++;
     dfs(k,set,i+1,tm);
     tm[k]--;
  }
}

Mas isto deu-me resultados esquisitos.

No código:

- tm = array que contêm o número de vezes que cada elemento do set aparece

- k = iterador

- i = local onde vai ser colocado mais um elemento do set


here since 2009

Share this post


Link to post
Share on other sites
Warrior

Porquê tm[k] < 3?

É um problema engraçado, pensa um pouco antes de te atirares a ele, vais ver que a resolução é mais simples do que queres pensar.

A forma mais fácil é pensar: dado um elemento K e um conjunto actual de elementos < K, necessito de formar todos os conjuntos de elementos > K, e depois coloco K ou não.

Dessa forma, percorrendo os elementos por ordem, não precisas de arrays auxiliares de pertença (na realidade, nem de ciclos no teu código!).

O truque está em pensar a recursividade não posição a posição (para cada indice tentar colocar um elemento) mas elemento a elemento.

Share this post


Link to post
Share on other sites
Localhost

Se calhar não me expliquei bem.

Eu estou mesmo a falar naquele problema do clocks. Uma move no clocks não se pode repetir mais do que 3 vezes senão voltámos ao estado inicial, ou seja, o que eu queria fazer era essa verificação, daí o tm[k] < 3.

Vou tentar explicar o meu código:

Para cada elemento do set eu verifico se ele já se repetiu mais do que ou 3 vezes, senão se repetiu então eu aumento mais uma vez o número de vezes que se repete e depois aprofundo mais a pesquisa, quando uma condição se verifica e eu faço o backtrack eu reduzo o número de vezes que se repetiu visto que estou a voltar atrás na árvore e exploro outro caminho (como um dfs normal).


here since 2009

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.