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  
anolsi

Descobrir se existe um caminho

Recommended Posts

anolsi

Supondo que tenho uma matriz n*n, onde cada célula pode ter dois estados: X ou Y.

Preciso de verificar se existe um caminho entre todas as X, de modo a que os Y não interfiram. Exemplo:

X X X X Y

X X Y X X

X Y X Y X

X X Y X X

Reparem que o X a negrito está isolado (o caminho não pode ser percorrido na diagonal), como tal estra matriz não seri válida.

Uma informação, que eu sei antes de verificar é que duas células Y nunca podem estar juntas (só horizontal ou verticalmente).

O algoritmo que desenvolvi foi contar todos os X (com um ciclo), e depois pegar e percorrer recursivamente e ir marcando as células para as quais conseguia ir a partir da primeira, algo do género:

Z Z Z Z Y

Z Z Y Z Z

Z Y X Y Z

Z Z Y Z Z

E assim sei que uma falha, porque não ficou marcada. O problema é que preciso de executar esta função m vezes sobre estados diferentes, e isso demora-me muito tempo. Não existirá um algoritmo mais eficiente que me permita chegar ao mesmo resultado?


"Nós somos o que fazemos repetidamente, a excelência não é um feito, e sim, um hábito."
Não respondo a questões por PM que possam ser colocadas no fórum!

Share this post


Link to post
Share on other sites
fnds

Eu fazia assim, na matriz considerava X o valor 1 e Y 0.

Agarras no primeiro X que aparece na matriz e depois vais verificar recursivamente todos os X que estão à volta desse X.

A cada X que visitas colocas-lo a 0 (como se fosse Y), assim evitas que ele seja visitado várias vezes.

Depois quando acabar é só verificar se existe algum X (1) na matriz. Se existir é porque não existe um caminho que ligue todos.

Share this post


Link to post
Share on other sites
anolsi

Eu fazia assim, na matriz considerava X o valor 1 e Y 0.

Agarras no primeiro X que aparece na matriz e depois vais verificar recursivamente todos os X que estão à volta desse X.

A cada X que visitas colocas-lo a 0 (como se fosse Y), assim evitas que ele seja visitado várias vezes.

Depois quando acabar é só verificar se existe algum X (1) na matriz. Se existir é porque não existe um caminho que ligue todos.

Mas é essa a técnica que eu estou a utilizar. Repara que os X por onde consigo passar recursivamente são marcados (para lá não voltar) como Z, assim eu sei que os Z, são os X onde passei e os X são os que não passei (o Y não são alterados, porque a função não é sequer chamada para eles).


"Nós somos o que fazemos repetidamente, a excelência não é um feito, e sim, um hábito."
Não respondo a questões por PM que possam ser colocadas no fórum!

Share this post


Link to post
Share on other sites
fnds

Também não estou a ver melhor solução.

Podes tentar é ver se é mais fácil agarrares nos Y e verificar se fazem alguma barreira.

E depois dependendo do número de X optares por uma solução.

Share this post


Link to post
Share on other sites
Warrior

Isso parece-me um http://en.wikipedia.org/wiki/Hamiltonian_path, portanto é NP-Completo, não há solução polinomial.

Acho que a ideia não é arranjar um caminho que percorra todos os nós, simplesmente saber se os X estão todos interligados.

Se assim for, então não existe solução mais eficiente. Já estás a percorrer cada nó somente 1 vez, menos do que isso é impossível.

Onde talvez dê para optimizar é nessas várias chamadas. Talvez seja possível re-calcular só as alterações, depende da sua natureza.

Share this post


Link to post
Share on other sites
Cynary

Não tenho a certeza se percebi completamente a forma como resolveste o problema, mas este parece-me muito semelhante ao problema das nuvens da classificação para as ONI.

Basicamente, o que faria era começar com um BFS na primeira célula, colocar as células em redor numa fila, e fazer o mesmo para cada uma dessas células, e assim sucessivamente, exceptuando células com o valor Y. Isto seria feito depois de se contar o nº de X.

Ao longo do BFS contavas o números de células percorrido, e vias no final se era igual ao número de X.

Share this post


Link to post
Share on other sites
Warrior

Estive a ler melhor e de facto acho que é necessário saber se de facto pretendes um CAMINHO através dos X (em que não repitas X) ou se o que tu queres é saber se os X estão todos conectados.

De resto, já forneceram soluções para os dois problemas:

caso pretendas um caminho, então queres um ciclo de Hamilton e o problema é NP: tens que testar todas as permutações de X e verificar se tens um ciclo. Isto pode ser optimizado se pesquisares com um DFS porque fazes muito pruning, mas continuas com uma solução não polinomial.

Se a ideia é saber se os X estão todos unidos, DFS ou BFS com uma flag que te impeça de visitar repetidos são a mesma solução, DFS é talvez mais straight-forward para implementar (recursivamente, claro).

Share this post


Link to post
Share on other sites
anolsi

O que eu pretendo saber é mesmo se os X estão todos ligados entre eles...

Bem, se não há melhor para verificação geral, será que há alguma maneira de eu validar esse quadro primeiro (com o meu algoritmo), e depois para cada alteração fazer uma verificação menor que apenas verifique isso? Porque um Y pode passar X e vice-versa, simplesmente não podem existir dois Y juntos (a função de alteração já faz essa validação), mas eu sei sempre que células foram alteradas, só que não vejo nenhuma maneira de aproveitar isso.


"Nós somos o que fazemos repetidamente, a excelência não é um feito, e sim, um hábito."
Não respondo a questões por PM que possam ser colocadas no fórum!

Share this post


Link to post
Share on other sites
Warrior

Qual o número esperado de alterações em relação às dimensões totais da matriz?

Share this post


Link to post
Share on other sites
anolsi

Qual o número esperado de alterações em relação às dimensões totais da matriz?

Por cada alteração eu tenho que fazer uma verificação... Era isso que querias saber?

As alterações podem ser 500 ou mais, para uma matriz de 26*26 (tamanho máximo)


"Nós somos o que fazemos repetidamente, a excelência não é um feito, e sim, um hábito."
Não respondo a questões por PM que possam ser colocadas no fórum!

Share this post


Link to post
Share on other sites
Warrior

Por cada alteração uma verificação?

Eu diria que podes fazer isso em tempo praticamente constante, mas deixa-me pensar no problema..

De qualquer modo, numa matriz de 26*26, O(N) é praticamente instantâneo.

Por alto, podes fazer ~200 conjuntos de 500 alterações nessa matriz 26*26 por segundo..

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.