| 4 damas escalada | 4 damas genético |

4 Damas, Escalada do Monte

Até este momento, os algoritmos apresentados exploraram o espaço de estados, em que uma solução vai sendo construída passo a passo. Ao obter o estado objectivo, obtêm-se a solução pretendida através do caminho desde o estado inicial ao estado objectivo. A procura desenrola-se no espaço das soluções parciais, dado que cada estado representa uma solução parcial do problema. Estes algoritmos chamam-se algoritmos construtivos, dado que tentam construir a solução.

Os algoritmos melhorativos desenrolam-se no espaço das soluções completas, em vez do espaço das soluções parciais, dado que cada estado representa uma solução completa do problema. Ao movimentarem-se de solução completa em solução completa, tentam melhorar a solução obtida, daí o nome atribuído de algoritmos melhorativos.

A escalada do monte começa num estado aleatório, e com base numa vizinhança definida, move-se para o estado vizinho que tiver melhor valor que o estado atual. Se todos os vizinhos forem iguais ou inferiores, então está-se num óptimo local: a procura pára caso já se tenha atingido o critério de paragem, ou recomeça novamente num outro estado aleatório. Na implementação há que optar por forçar a geração de todos os vizinhos, de forma a mover a procura para o vizinho mais promissor, ou mover a procura imediatamente assim que encontrar um vizinho melhor que o atual.

Vamos ver o caso das 4 Damas. Vamos considerar um estado, uma linha para cada dama de uma coluna, ou seja, em cada coluna colocar uma dama numa das linhas. Uma possível solução seria as damas todas na primeira linha. Nesse caso essa solução violaria a restrição das damas não se atacarem mutuamente. Para que o algoritmo procure uma solução sem essa restrição violada, o valor de cada solução considerada, é o número de pares de damas que se atacam mutuamente.

Este estado, há 6 pares de damas a atacarem-se mutuamente. Portanto o valor da solução é 6, e pretende-se achar uma solução que minimize o número de pares de damas atacadas, ou seja, zero. Para gerar uma solução aleatória, basta gerar 4 números entre 1 e 4 para as posições de cada dama. Por exemplo, a sequência 3, 2, 4, 1 iria gerar o estado:

Neste estado apenas um par de damas está atacado.

Falta agora definir a vizinhança. Esta função tem de permitir a navegação pelo espaço de estados, permitindo em teoria que o algoritmo possa navegar entre dois pares de estados arbitrários. No entanto, se um estado tiver muitos vizinhos, tal pode ser também prejudicial ao algoritmo, pelo que vamos considerar os vizinhos que trocam apenas a posição de uma dama, mas apenas se a dama estiver atacada. Vamos iniciar o algoritmo desse estado:

Os vizinhos todos do estado 1 foram analisados, no entanto apenas um dos vizinhos tem o mesmo valor, não existindo nenhum vizinho melhor, portanto estamos num óptimo local. O algoritmo poderia acabar aqui, ou então reiniciar, no caso do critério de paragem não ter sido atingido. Vamos reiniciar, e os 4 números aleatórios seguintes são: 3, 3, 4, 2.

Ficheiro de Excel, passo a passo:

Foram gerados 17 estados, os quais foram avaliados, e obteve-se a solução óptima. Notar que o algoritmo adoptado, explorou-se toda a vizinhança antes de decidir move o algoritmo para um estado melhor. Caso se tivesse optado por mover o algoritmo assim que encontre um melhor vizinho, na geração 11, parava-se a geração dos vizinhos do estado 8, e iniciava-se a geração dos vizinhos do estado 11.

Para ter uma melhor noção de como funciona esta procura, execute a procura novamente com outros valores aleatórios: imprima da template de resolução a folha "Melhorativas (4x4)", e utilize os números aleatórios à direita. 

| 4 damas escalada | 4 damas genético |