Loading...
Publication
Estudo preliminar de restarts para algoritmos de CSP
| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 87.43 KB | Adobe PDF |
Authors
Advisor(s)
Abstract(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.
Description
Keywords
procura restrições restarts aleatório heurística