BFS - Implementação

[Localhost 3]

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.

[Localhost 3]

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. 

[Warrior 68]

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()

[mogers 14]

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;
}

[Warrior 68]

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.

[Localhost 3]

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++.

[Warrior 68]

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

[Localhost 3]

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

[Warrior 68]

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.

[Localhost 3]

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).

[Warrior 68]

Continua esta discussão no tópico do clocks então.