Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

anolsi

Descobrir se existe um caminho

Mensagens Recomendadas

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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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).

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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..

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.