Então, eu estava tentando implementar o BFS em um quebra-cabeça Sliding Blocks (tipo de número). Agora, a principal coisa que notei é que, se você tem um 4*4
quadro, o número de estados pode ser tão grande quanto 16!
não posso enumerar todos os estados antes.
Portanto, minha pergunta é como acompanhar os estados já visitados? (Estou usando um quadro de classe, cada instância de classe contém um padrão de quadro exclusivo e é criada enumerando todas as etapas possíveis da etapa atual).
Pesquisei na rede e, aparentemente, eles não retornam à etapa anterior recém-concluída, mas também podemos voltar à etapa anterior por outra rota e, em seguida, reenumerar todas as etapas que foram visitadas anteriormente. Então, como acompanhar os estados visitados quando todos os estados ainda não foram enumerados? (comparar estados já presentes com a etapa atual será caro).
Respostas:
Você pode usar um
set
(no sentido matemático da palavra, ou seja, uma coleção que não pode conter duplicatas) para armazenar estados que você já viu. As operações que você precisará executar sobre isso são:Praticamente toda linguagem de programação já deve ter suporte para uma estrutura de dados que pode executar essas duas operações em tempo constante ( ). Por exemplo:O ( 1 )
set
em PythonHashSet
em JavaNo pseudocódigo, esse conjunto (vamos chamá-lo
closed_set
, para ser consistente com o pseudocódigo na wikipedia pode ser usado em uma pesquisa de amplitude inicial da seguinte forma:(algumas variações desse pseudocódigo também podem funcionar e serem mais ou menos eficientes, dependendo da situação; por exemplo, você também pode
closed_set
incluir todos os nós dos quais você já adicionou filhos à fronteira e evitar completamente agenerate_children()
chamada securrent
já estiver noclosed_set
.)O que eu descrevi acima seria a maneira padrão de lidar com esse problema. Intuitivamente, suspeito que uma "solução" diferente poderia ser sempre aleatória na ordem de uma nova lista de estados sucessores antes de adicioná-los à fronteira. Dessa forma, você não evita o problema de adicionar ocasionalmente estados que já expandiu para a fronteira, mas acho que isso deve reduzir significativamente o risco de ficar preso em ciclos infinitos.
Cuidado : não conheço nenhuma análise formal dessa solução que prove que ela sempre evita ciclos infinitos. Se eu tentar "executar" isso na minha cabeça, intuitivamente, suspeito que deva funcionar e não requer memória extra. Pode haver casos extremos nos quais não estou pensando agora, portanto, também pode não funcionar, a solução padrão descrita acima será uma aposta mais segura (ao custo de mais memória).
fonte
closed_set
; seu tamanho nunca deve afetar o tempo de computação (assintótico).A resposta de Dennis Soemers está correta: você deve usar um HashSet ou uma estrutura semelhante para acompanhar os estados visitados na Pesquisa de gráficos do BFS.
No entanto, isso não responde à sua pergunta. Você está certo, que, na pior das hipóteses, o BFS exigirá que você armazene 16! nós. Mesmo que os tempos de inserção e verificação no conjunto sejam O (1), você ainda precisará de uma quantidade absurda de memória.
Para corrigir isso, não use BFS . É intratável para todos, exceto o mais simples dos problemas, porque requer tempo e memória exponenciais à distância do estado objetivo mais próximo.
Um algoritmo muito mais eficiente em memória é o aprofundamento iterativo . Ele possui todas as propriedades desejáveis do BFS, mas usa apenas memória O (n), onde n é o número de movimentos para alcançar a solução mais próxima. Ainda pode demorar um pouco, mas você atingirá os limites de memória muito antes dos limites relacionados à CPU.
Melhor ainda, desenvolva uma heurística específica do domínio e use a pesquisa A * . Isso deve exigir que você examine apenas um número muito pequeno de nós e permita que a pesquisa seja concluída em algo muito mais próximo do tempo linear.
fonte
Embora as respostas dadas sejam geralmente verdadeiras, um BFS nos 15 quebra-cabeças não é apenas viável, mas foi feito em 2005! O documento que descreve a abordagem pode ser encontrado aqui:
http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf
Alguns pontos-chave:
Há muito mais a ser dito aqui, mas os artigos acima fornecem muito mais detalhes.
fonte
Ironicamente, a resposta é "use o sistema que desejar". Um hashSet é uma boa ideia. Entretanto, suas preocupações com o uso de memória são infundadas. O BFS é tão ruim nesses tipos de problemas que resolve esse problema para você.
Considere que seu BFS exige que você mantenha uma pilha de estados não processados. À medida que você avança no quebra-cabeça, os estados com os quais você lida se tornam cada vez mais diferentes, então é provável que você veja que cada camada do seu BFS multiplica o número de estados a serem observados em aproximadamente 3.
Isso significa que, ao processar a última camada do seu BFS, é necessário ter pelo menos 16! / 3 estados na memória. Qualquer que seja a abordagem que você usou para garantir que o ajuste na memória seja suficiente para garantir que sua lista visitada anteriormente também se encaixe na memória.
Como outros já apontaram, este não é o melhor algoritmo a ser usado. Use um algoritmo que seja mais adequado ao problema.
fonte
O problema dos 15 quebra-cabeças é jogado em um tabuleiro 4x4. A implementação disso no código-fonte é feita passo a passo. A princípio, o próprio mecanismo de jogo deve ser programado. Isso permite jogar o jogo por um operador humano. O jogo de 15 quebra-cabeças tem apenas um elemento livre e, nesse elemento, as ações são executadas. O mecanismo do jogo aceita quatro comandos possíveis: esquerda, direita, cima e baixo. Outras ações não são permitidas e é possível controlar o jogo apenas com estas instruções.
A próxima camada para jogar o jogo é uma GUI. Isso é muito importante, pois permite testar o mecanismo do jogo e tentar resolvê-lo manualmente. Além disso, uma GUI é importante porque precisamos descobrir heurísticas em potencial. E agora podemos falar sobre a própria IA. A IA precisa enviar comandos para o mecanismo do jogo (esquerda, direita, cima e baixo). Uma abordagem ingênua para um solucionador seria um algoritmo de busca por força bruta, o que significa que a IA está enviando comandos aleatórios até que o estado do objetivo seja atingido. Uma idéia mais avançada é implementar algum tipo de banco de dados de padrões que reduz o espaço de estados. A primeira pesquisa de largura não é diretamente uma heurística, mas é um começo. É igual criar um gráfico para testar possíveis movimentos de maneira cronológica.
O rastreamento de estados existentes pode ser feito com um gráfico. Cada estado é um nó, possui um ID e um ID pai. O AI pode adicionar e excluir nós no gráfico, e o planejador pode resolver o gráfico para encontrar um caminho para a meta. Do ponto de vista da programação, um mecanismo de jogo do quebra-cabeça 15 é o objeto e a lista de muitos objetos é uma lista de matrizes. Eles são armazenados em uma classe de gráfico. Perceber isso no código fonte é um pouco complicado, geralmente a primeira tentativa falha e o projeto produz muitos erros. Para gerenciar a complexidade, esse projeto geralmente é realizado em um projeto acadêmico, ou seja, é um tópico para escrever um artigo sobre ele, que pode ter 100 páginas ou mais.
fonte
Abordagens para o jogo
No entanto, esses fatos triviais não são pertinentes se o objetivo é concluir o quebra-cabeça no menor número de ciclos de computação. A primeira pesquisa de largura não é uma maneira prática de concluir um quebra-cabeça de movimento ortogonal. O custo muito alto de uma primeira pesquisa de largura só seria necessário se o número de movimentos for de suma importância por algum motivo.
Descida da sub-sequência
A maioria dos vértices que representam estados nunca será visitada, e cada estado visitado pode ter entre duas e quatro arestas de saída. Cada bloco tem uma posição inicial e uma posição final e a placa é simétrica. A maior liberdade de escolha existe quando o espaço aberto é uma das quatro posições intermediárias. O mínimo é quando o espaço aberto é uma das quatro posições de canto.
Uma função de disparidade razoável (erro) é simplesmente a soma de todas as disparidades x mais a soma de todas as disparidades y e um número que representa heuristicamente qual dos três níveis de liberdade de movimento existe devido ao posicionamento resultante do espaço aberto (meio, borda) , canto).
Embora os blocos possam se afastar temporariamente de seus destinos para apoiar uma estratégia em direção à conclusão que exija uma sequência de movimentos, raramente há um caso em que essa estratégia exceda oito movimentos, gerando, em média, 5.184 permutações para as quais os estados finais podem ser comparados usando a função disparidade acima.
Se o espaço vazio e as posições do bloco 1 a 15 forem codificados como uma matriz de petiscos, apenas operações de adição, subtração e bits serão necessárias, tornando o algoritmo rápido. Repetir as oito estratégias de força bruta de movimento pode ser repetido até que a disparidade caia para zero.
Sumário
Esse algoritmo não pode alternar porque sempre há pelo menos uma das permutações de oito movimentos que diminui a disparidade, independentemente do estado inicial, com exceção de um estado inicial que já está completo.
fonte