Upload
trinhnhu
View
218
Download
0
Embed Size (px)
Citation preview
Relatório de Intel igência Artif icial
Hidato
Grupo 4
Diogo Simões - 63558
Inês Almeida - 63556
Miguel Diogo - 63567
Introdução
O objectivo deste projecto é resolver automaticamente um tabuleiro de Hidato através do melhor de
três algoritmos criados, sendo considerado o melhor aquele que realizar o maior número de tarefas
no menor tempo possível e com o mínimo de memória gasta.
Primeira Estratégia
DescriçãoA primeira estratégia consiste numa procura em profundidade auxiliada por um algoritmo que, para
além de resolver o tabuleiro enquanto conseguir determinar sem dúvidas a posição correcta de um
elemento, indica à procura quando
• o tabuleiro está resolvido (correctamente),
• o tabuleiro está inconsistente (é necessário retroceder),
• é necessário dividir a árvore de procura em 'n' estados, diferindo em todas as 'n' posições
possíveis do elemento 'x'.
Estruturas de DadosPara além das três variáveis globais (definidas para não ser necessário calcular repetidas vezes a
mesma coisa)
• n - número de linhas,
• m - número de colunas e
• num-elem - número de células/elementos
Relatório de Inteligência Artificial! 1
Estado
Trata-se de uma estrutura, definida da seguinte maneira:
Fig. 1 - Estrutura Estado
AlgoritmoPara cada posição recentemente ocupada e para cada elemento que a poderia ocupar, é retirada a
dita posição como possibilidade para o elemento ser colocado.
Se a esse elemento restar apenas uma possibilidade de posição para ser colocado e caso a posição
esteja livre, o elemento é colocado (caso não esteja, então o algoritmo retorna com a 'flag' a '-1'
significando inconsistente).
Quando já não existirem posições recentemente ocupadas na lista, o algoritmo percorre a lista de
elementos em busca do elemento com o mínimo de possibilidades para ser colocado. Se esse
elemento só tiver uma possibilidade, é colocado, se tiver mais que uma, então o algoritmo retorna
com a 'flag' sendo um par (n, elem) em que “n” é o número de possibilidades/estados diferentes a
gerar e “elem” o elemento a variar.
O algoritmo corre até o tabuleiro estar resolvido, inconsistente ou "indeciso".
Quando um elemento é colocado, é sempre verificado se isso afecta o seu sucessor ou antecessor, o
que pode resultar em inconsistência ou na colocação do sucessor e/ou antecessor.
Relatório de Inteligência Artificial! 2
Segunda Estratégia
DescriçãoEste algoritmo é uma variante do forward checking.
Os algoritmos de forward checking mantêm um registo de valores que podem ser atribuídos a cada
variável, retrocedendo assim que alguma dessas variáveis não tenha valores possíveis.
Estruturas de Dados
Variáveis Globais
À semelhança do algoritmo anterior, são definidas três variáveis globais, uma com o número de
linhas, outra com o número de colunas e outra com o total de quadrículas do tabuleiro.
EstadoEsta estrutura guarda informação apenas sobre as posições possíveis para cada número sobre a
forma de um vector unidimensional (numpos) e um booleano (livres) que indica se há posições livres
ou não.
Vector Número/Posição:
Cada posição deste vector corresponde a um dos números do tabuleiro por ordem e contém uma
lista que guarda as posições possíveis para esse número. O vector tem portanto dimensão N x M.
!Fig. 4 - Vector Número/Posição
As posições são guardadas na forma de números, em que cada número corresponde a uma
quadrícula do tabuleiro. O número 0 corresponde ao canto superior esquerdo sendo incrementado
da esquerda para a direita linhas a linhas até à posição (N x M) — 1 que corresponde ao canto
inferior direito.
Relatório de Inteligência Artificial! 5
Dado este número e o total de colunas, descobrir a coluna e a linha
dele é possível através do resto da divisão pelo total e da divisão inteira pelo total, respectivamente.
Uma vez que o input e o output do algoritmo têm que ser uma lista de
listas, são necessárias algumas funções para fazer a conversão entre
essa representação e a representação interna do algoritmo.
AlgoritmoPara realizar o “forward checking” são inseridas numa lista as
posições que podem ser atribuídas a um dado número, tendo em conta as restrições que existem
para a resolução de um tabuleiro de hidato. Sempre que uma dessas listas é alterada, têm de ser
avaliadas as posições possíveis do número seguinte e do número anterior a este. Para tal é gerada
uma lista de posições adjacentes ao número em causa que é intersectada com a lista do número
anterior. Se a intersecção das duas listas for diferente da lista do número anterior, essa lista é
alterada. Faz-se o mesmo com o número seguinte. Caso alguma lista alterada fique com apenas uma posição, é necessário também retirá-la das listas de todos os outros números.
Fig. 6 - Exemplo de Retrocesso
0 1 2
3 4 5
6 7 8
Número correspondente acada posição numa tabela 3x3
Relatório de Inteligência Artificial! 6
Fig. 5 - Exemplo de atribuição de números.
Este algoritmo faz uma procura em profundidade até encontrar um nó final ou um nó inconsistente,
deixando pendentes em memória todos os nós gerados. Caso encontre um nó inconsistente, retrocede para o nó pendente mais próximo da raiz da árvore e continua em profundidade a partir
daí.
Ao expandir um nó, o algoritmo escolhe a variável com menos posições possíveis de atribuir e gera
um nó com para cada atribuição possível. Estes nós são então tornados consistentes como descrito
anteriormente.
Terceira Estratégia
Descrição:A terceira estratégia é uma variação da anterior em que a única diferença está na forma como é
percorrida a árvore. Baseia-se nos mesmos algoritmos para realizar “forward checking”, verificar
restrições e escolher variáveis.
Estruturas de Dados:As estruturas de dados utilizadas
são as mesmas da estratégia
anterior.
AlgoritmoComo anteriormente referido, este algoritmo difere do anterior apenas
na forma como a árvore é
percorrida. Aqui, a procura é feita
em largura, não havendo portanto
retrocessos.
Esta alteração ao algoritmo anterior
parecia uma optimização
promissora, pois como existe
“forward checking” podem existir
vários nós finais (embora iguais entre si) e a diferentes profundidades pelo que uma procura em largura poderia encontrar algum mais depressa. No entanto, os resultados são ligeiramente piores do
que anteriormente, como se pode constatar analisando a secção seguinte.
Nó Expandido
Nó Expandido
Próximo Nó a Expandir
Nó Expandido
Nó Expandido
Nó Pendente Nó Pendente
Nó PendenteNó Pendente
Relatório de Inteligência Artificial! 7
Fig. 7 - Procura em Largura
Resultados Obtidos
1ª Estratégia 2ª Estratégia 3ª Estratégia
H0Real Time !"!!!#$%&'()" !"!!!**$&'()" !"!!!*+,&'()"
H0Space -.$+%&/01(' *2%,2&/01(' *2%,2&/01('
H1Real Time !"!!-,%,&'()" !"!!#+,+&'()" !"!!#%+-&'()"
H1Space -!%$-%&/01(' #,!#-2&/01(' $.-!.%&/01('
H2Real Time !"!!!.!,&'()" !"!!%2#-&'()" !"!!%2,-&'()"
H2Space $--!#&/01(' %#2#+2&/01(' %#2#+2&/01('
H3Real Time !"!!%+!*&'()" !"!!,!2#&'()" !"!!2*!#&'()"
H3Space %,!2!*&/01(' ,-2..2&/01(' ,-2...&/01('
H4Real Time !"!!$,$$&'()" !"!!#2%#&'()" !"!!#*2&'()"
H4Space $-2-.2&/01(' #.2*%#&/01(' #.2*%#&/01('
H15Real Time !"!!$+%#&'()" !"!.*!,2&'()" !"!*$#,2&'()"
H15Space $.*2,2&/01(' $+-2.2!&/01(' $+2!.+%&/01('
H16Real Time !"!2!-,*&'()" !"!+*$*2&'()" !"!+*,#-&'()"
H16Space #2!*2.%&/01(' ,-+2%**&/01(' #.+!.!#&/01('
H70Real Time !"!!,##2&'()" !"%*-2*2&'()" !"%+&'()"&
H70Space ,$#+,%&/01(' --.!#,2!&/01(' --**2*#*&/01('
H71Real Time !"%#+-2&'()" !"%*.#$*&'()" !"$!+-.2&'()"
H71Space -+.-.2#*&/01(' -%,!$,##&/01(' -%$,**#*&/01('
H125Real Time !"!,*+*.&'()" !"#%$$+.&'()" !"#**$#+&'()"
H125Space #+!$!.%&/01(' %!#,,#2#&/01(' %$-,+*$%&/01('
H126Real Time !"-+-,2-&'()" !"$$$#2,&'()" !"$#**#.&'()"
H126Space -2*#,-$2&/01(' -$.,+%%#&/01(' -$-#$!.%&/01('
H178Real Time ,"!*,-%.&'()" -",%#*-&'()" -",*,%.+&'()"
H178Space #$2%#!*$%&/01(' ,#-$.!,2&/01(' ,%!..!+2&/01('
H179Real Time !",,%%!#&'()" -"$,$,-%&'()" -"#-,.*-&'()"
H179Space #.$!#$*#&/01(' #+!%2-+%&/01(' ,!!!-#%#&/01('
Os valores foram obtidos através da instrução times. As especificações da máquina utilizada são:
• Sistema Operativo Gentoo Linux x86_64;
• Processador Core 2 Duo 2.93 GHz;
• Velocidade do Bus: 1.07 GHz
• Cache L2: 6 MB.
Relatório de Inteligência Artificial! 8
Gráficos Comparativos
Tabuleiros Menores
!"!!!!#
!"!!$!#
!"!!%!#
!"!!&!#
!"!!'!#
!"!!(!#
!"!!)!#
!"!!*!#
!"!!+!#
,!# ,$# ,%# ,&# ,'#
-./01
#2.#34.56781
#9:.;6<
21:=#
$>#3:?@A?B;CA#
%>#3:?@A?B;CA#
&>#3:?@A?B;CA#
Fig 8 - Gráfico de Tempo de Execução para primeiros cinco tabuleiros
!"
#!!"
$!!"
%!!"
&!!"
'!!"
(!!"
)!" )#" )$" )%" )&"
*+,
-./0"123/405
0"67/38
9:;+<="
#>"?<;.0;@A/0"
$>"?<;.0;@A/0"
%>"?<;.0;@A/0"
Fig 9 - Gráfico de Consumo de Memória para primeiros cinco tabuleiros
Relatório de Inteligência Artificial! 9
Tabuleiros Intermédios
!"!!!!#
!"!$!!#
!"%!!!#
!"%$!!#
!"&!!!#
!"&$!!#
!"'!!!#
!"'$!!#
(%$# (%)# (*!# (*%#
+,-./
#0,#12,3456/
#78,94:
0/8;#
%<#18=>?=@9A?#
&<#18=>?=@9A?#
'<#18=>?=@9A?#
Fig 10 - Gráfico de Tempo de Execução para os quatro tabuleiros intermédios
!"
#"
$!"
$#"
%!"
%#"
&$#" &$'" &(!" &($"
)*+
,-./"012.3/4
/"5)
*6/7
89*:;"
$<"=:9-/9>6./"
%<"=:9-/9>6./"
?<"=:9-/9>6./"
Fig 11 - Gráfico de Consumo de Memória para os quatro tabuleiros intermédios
Relatório de Inteligência Artificial! 10
Tabuleiros Avançados
!"!!!!#
$"!!!!#
%"!!!!#
&"!!!!#
'"!!!!#
("!!!!#
)"!!!!#
*$%(# *$%)# *$+,# *$+-#
./012
#3/#45/67892
#:;/<7=
32;>#
$?#4;@AB@C<DB#
%?#4;@AB@C<DB#
&?#4;@AB@C<DB#
Fig 12 - Gráfico de Tempo de Execução para últimos quatro tabuleiros
!"
#!"
$!!"
$#!"
%!!"
%#!"
&!!"
&#!"
'!!"
'#!"
#!!"
($%#" ($%)" ($*+" ($*,"
-./
0123"4562738
3"9-
.:3;
<=.>?"
$@"A>=13=B:23"
%@"A>=13=B:23"
&@"A>=13=B:23"
Fig 13 - Gráfico de Consumo de Memória para os últimos quatro tabuleiros
Relatório de Inteligência Artificial! 11
Gráficos das Médias de Tempo de Execução e Memória Utilizada
!"!!!!#
!"$!!!#
!"%!!!#
!"&!!!#
!"'!!!#
!"(!!!#
!")!!!#
$*#+,-./-012/# %*#+,-./-012/# &*#+,-./-012/#
3042/#45#-6785#46#696:;<=5#>,61;?45,@#
7042/#
Fig 14 - Gráfico de Média do Tempo de Execução
!"
#"
$!"
$#"
%!"
%#"
&!"
&#"
'!"
'#"
$(")*+,-+./0-" %(")*+,-+./0-" &(")*+,-+./0-"
1.20-"2-"1345,0-"67809-2-":13/-;<+3*="
4.20-"
Fig 15 - Gráfico de Média de Consumo de Memória
Relatório de Inteligência Artificial! 12
Conclusões
Verifica-se através dos dados obtidos que a primeira estratégia é menos constante que as outras
duas, pois em tabuleiros de tamanho igual, que à partida seriam da mesma complexidade, acaba por ter tempos de execução e consumo de memória muito discrepantes.
Nos tabuleiros mais pequenos é relativamente mais eficiente. Nos tabuleiros grandes e intermédios
tanto apresenta valores “normais” (h16, h126, h179), valores muito bons (h15, h70, 125), como
valores maus (h71 e h178). Note-se que os valores obtidos para o h178 são mesmo muito maus,
fazendo destoar completamente as médias deste algoritmo.
É possível também concluir que há resultados bastante semelhantes entre os algoritmos da primeira
e da segunda estratégia, o que é normal visto que os algoritmos são muito semelhantes. Porém,
existe uma pequena vantagem para a segunda estratégia em termos de velocidade de resolução dos
tabuleiros de hidato.
A segunda estratégia aqui apresentada parece ser a mais eficiente das três, porque comparativamente à terceira estratégia, para além de ser mais rápida a encontrar o nó objectivo,
gasta praticamente a mesma quantidade de memória e comparativamente à !primeira não oscila
muito nos resultados. Supomos que os valores discrepantes da 1ª estratégia são por a procura ser
em profundidade, mas seria necessário um conjunto maior de tabuleiros para tirar mais conclusões.
Relatório de Inteligência Artificial! 13