Jump to content
agarcao

Algoritmo de Pesquisa - Que utilizar?

Recommended Posts

agarcao

Olá a todos,

Bem tenho visto alguns algoritmos de pesquisa na internet mas nenhum se adequa muito bem ao meu problema. Vou tentar especificar aqui o problema de forma simples: dão me como input duas strings; depois tenho que ir procurar numa lista de estruturas X a estrutura com nome igual à da primeira string; depois de encontra-la tenho de ir à lista de strings(nomes de estruturas X) que a estrutura possui para ver se a segunda string fornecida está lá; se não estiver tenho de ir fazer para cada string dessa lista a mesma coisa..

Ora como devem perceber isto vai crescer a um ritmo alucinante mas não consigo encontrar maneira de resolver o problema de forma mais simples até porque nenhuma das listas (a de estruturas X e a de strings) está ordenada.

Que pensam que devo fazer? Ordenar ambas as listas? Qual o melhor algoritmo para aplicar?

Obrigado desde já a todos,

Share this post


Link to post
Share on other sites
agarcao

Ordenar ambas as listas? Mas faço como? À medida que insiro ou quando já lá estão todas? Talvez a primeira opção não?

Share this post


Link to post
Share on other sites
KiNgPiTo

Se fores tu a controlar a inserção, o melhor é inserir ordenadamente.. já não precisas de ordenar nada e podes usar pesquisas ordenadas...

Share this post


Link to post
Share on other sites
Localhost

Se isto é por causa do problema B das ONI, não achas que há outra solução menor do que organizar por arrays alfabeticas? É que isso pode dar erro num caso em que a letra alterada seja a primeira. Talvez LD, e não vou dizer o que significa a sigla. Quem souber, talvez tenha um flash.

xtrm0: vais parar de fazer esse tipo de posts? Pah, não estou a perceber a tua ideia mas não gosto deste tipo de coisas. Por favor, apaga o post - quando o fizeres eu edito o meu e elimino a citação.


here since 2009

Share this post


Link to post
Share on other sites
blackburn69

Para clarificar o post do xtrm0 para o agarcao, tens uma alternativa relativamente simples de encontrares a "string mais parecida" que será utilizando Levenshtein Distances. Na Wikipédia tens a explicação e o algoritmo em pseudo-código.

Share this post


Link to post
Share on other sites
agarcao

Mas estes algoritmos parecem ser para procurar uma string num texto ou assim. O que eu quero é encontra la numa lista de strings[3] que é alocada dinamicamente então pode ter um tamanho muito grande. Por isso é que preciso da maneira mais rapida possivel para descobri-la. E além disso pode ou não estar lá..  :thumbsup:

EDIT: ah, a lista está ordenada. um algoritmo de dividir para conquistar talvez e quando só já tivermos reduzido a uns poucos percorre los para ver se existe ou não na lista.. não sei, é uma ideia.

Share this post


Link to post
Share on other sites
Localhost

@agarcao: depende dos conhecimentos que tenhas... se o tamanho máximo das strings for muito grande compensa mais implementar um trie.

Com uma trie a complexidade de pesquisa em worst case é O (max_len) em que max_len é o tamanho máximo das strings.

Com uma pesquisa binária seria O (log n * max_len). Vais dividindo em duas partes e escolhes a parte (esquerda ou direita) onde se encontra a tua resposta. Atenção, não fazes isto apenas uma vez; fazes isto sempre até encontrares a tua resposta (até restar apenas um elemento).


here since 2009

Share this post


Link to post
Share on other sites
agarcao

Pois, mas não dá para implementar isso. É que não tenho um lista de strings, mas sim uma lista de estruturas que cada uma tem uma string. E como só tenho um apontador para o primeiro elemento da lista nunca posso ir logo buscar o elemento do meio sem percorrer a lista. Eu se calhar nem me estou a explicar muito bem. Vou postar aqui as duas estruturas que tenho:

/* Voo_element */

typedef struct Voo_element{
int nVoo;
char depAero[4];
char arrAero[4];
char VooCode[7];
char depTime[5];
char arrTime[5];
float price;
int canTemp; /* Para os voos que tem um dos seus aeros encerrados*/
struct Voo_element* nextVoo;
} Voo;


/* Aero_element */

typedef struct Aero_element {
char name[4];
int nCheg;
int nPart;
char disp;
struct Aero_element* next;
struct Voo_element* part;
struct Voo_element* cheg;
} Aero;

Vou explicar agora o problema melhor. Dão por exemplo duas strings: "LIS" e "LON". Como só tenho um apontador de Aero first tenho de começar sempre pelo inicio para ver se encontro a primeira string ("LIS"). Se não encontrar a fc irá acabar logo ai, mas se encontrarmos temos de ir à lista de Voos dada pelo apontador part. Ai iremos ver se encontramos a segunda string ("LON") comparando-a com a arrAero dos Voos. Se encontramos a fc devolve um numero e acaba. Senão teremos de ir a encontrar todos os arrAeros na lista de Aeros com o apontador first e verificar se na lista de voos part de cada um dos Aeros tem algum voo que tenha o seu arrAero igual à segunda string("LON").

Já estão a ver o meu problema que isto vai crescer exponencialmente. =S

Share this post


Link to post
Share on other sites
Localhost

Como estás a trabalhar com listas ligadas, a não ser que queiras ter algo à parte que te mantenha as strings, vais ter sempre uma pesquisa linear - para encontrar um determinado elemento, em worst case, tens que percorrer a lista toda.


here since 2009

Share this post


Link to post
Share on other sites
agarcao

Pois mas não sei se isto dá para mim. O tempo de execução disso vai ser brutal.. Se meter a lista duplamente ligada talvez já haja melhores opções não?

EDIT: e circular talvez..

Share this post


Link to post
Share on other sites
Localhost

Se percebi bem o problema utilizares diferentes tipos de listas não vai alterar em nada o tempo de execução visto que em worst case tu vais ter sempre que percorrer N elementos, sendo N o número de elementos na lista.

Para melhorares o tempo de execução terias mesmo de usar algo externo às listas que te armazenasse as strings e aí sim podias optimizar a pesquisa.


here since 2009

Share this post


Link to post
Share on other sites
agarcao

Como por exemplo? É que não tenho ideia nenhuma e o problema é que isto não vai passar nos teste pois o tempo de execução vai ser imenso..

Share this post


Link to post
Share on other sites
Localhost

Podes ter vectores de strings para cada tipo de strings que queres. Por exemplo, podias ter um vector de strings para guardar todas as strings arrAero e depois aplicavas uma pesquisa binária, por exemplo.


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

×
×
  • Create New...

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.