A carregar...
Publicação
Estudo preliminar de restarts para algoritmos de CSP
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 87.43 KB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
O uso de técnicas de restarts para resolver problemas de satisfação de restrições (CSPs),
utilizando algoritmos de procura com retrocesso, é considerado pouco importante. Neste artigo
propomos conduzir um estudo preliminar sobre o impacto da utilização de restarts nestes
algoritmos. Mostramos que o conhecido problema da n-rainhas tem uma distribuição heavy-tail.
Apresentamos evidências empíricas de que os restarts podem efectivamente melhorar o tempo
necessário para encontrar a solução das n-rainhas. Implementamos ainda uma heurística de
decisão baseada em conflitos e mostramos empiricamente que esta heurística, em conjunto com
os restarts, melhora ainda mais o tempo de execução dos algoritmos.
Descrição
Palavras-chave
procura restrições restarts aleatório heurística