Algoritmos: Custos de computação e Heurísticas subseqüentes - manequins

Muitas vezes, você acha que uma abordagem heurística, que depende na auto descoberta e produz resultados suficientemente úteis (não necessariamente otimizados, mas bons o suficiente) é o método que você realmente precisa para resolver um problema. Obter o algoritmo para executar alguns dos trabalhos necessários para você economiza tempo e esforço porque você pode criar algoritmos que vêem padrões melhor do que os humanos.

Conseqüentemente, a auto descoberta é o processo de permitir que o algoritmo mostre um caminho potencialmente útil para uma solução (mas você ainda deve contar com intuição e compreensão humana para saber se a solução é a certa). As seções a seguir descrevem técnicas que você pode usar para calcular o custo de um algoritmo usando heurísticas como um método para descobrir a utilidade real de qualquer solução dada.

Representando o problema como espaço

A espaço de problema é um ambiente no qual a busca de uma solução ocorre. Um conjunto de estados e os operadores usados para alterar esses estados representam o espaço do problema. Por exemplo, considere um jogo de azulejo que tenha oito telhas em uma moldura 3-x-3. Cada telha mostra uma parte de uma imagem e as telhas começam em alguma ordem aleatória para que a imagem seja mexida. O objetivo é mover um azulejo de cada vez para colocar todos os azulejos na ordem certa e revelar a imagem.

A combinação do estado de início, das telhas randomizadas e do estado do objetivo - as telhas em uma ordem específica - é a instância do problema. Você poderia representar o quebra-cabeça graficamente usando um gráfico de espaço para problemas. Cada nó do gráfico do espaço do problema apresenta um estado (as oito telhas em uma posição específica). As bordas representam as operações, de modo a mover o número oito da telha. Quando você move a tela oito para cima, a imagem muda - ela se move para outro estado.

Ganhar o jogo, movendo-se do estado de início para o estado do objetivo, não é a única consideração. Para resolver o jogo de forma eficiente, você precisa executar a tarefa no menor número de movimentos possíveis, o que significa usar o menor número de operadores. O número mínimo de movimentos usados para resolver o quebra-cabeça é a profundidade do problema.

Você deve considerar vários fatores ao representar um problema como um espaço. Por exemplo, você deve considerar o número máximo de nós que caberá na memória, o que representa a complexidade do espaço. Quando você não pode caber todos os nós na memória ao mesmo tempo, o computador deve armazenar alguns nós em outros locais, como o disco rígido, o que pode retardar consideravelmente o algoritmo.Para determinar se os nós se encaixam na memória, você deve considerar a complexidade do tempo,, que é o número máximo de nós criados para resolver o problema. Além disso, é importante considerar o fator de ramificação,, que é o número médio de nós criados no gráfico do espaço problemático para resolver um problema.

Ir aleatoriamente e ser abençoado pela sorte

Resolver um problema de busca usando técnicas de força bruta é possível. A vantagem desta abordagem é que você não precisa de nenhum conhecimento específico do domínio para usar um desses algoritmos. Um algoritmo de força bruta tende a usar a abordagem mais simples possível para resolver o problema. A desvantagem é que uma abordagem de força bruta funciona bem apenas para um pequeno número de nós. Aqui estão alguns dos algoritmos comuns de pesquisa de força bruta:

Pesquisa de primeira linha: Esta técnica começa no nó da raiz, explora primeiro cada um dos nós filho e, em seguida, move-se para o próximo nível. Ele progride nível por nível até encontrar uma solução. A desvantagem deste algoritmo é que ele deve armazenar cada nó na memória, o que significa que ele usa uma quantidade considerável de memória para um grande número de nós. Esta técnica pode verificar se há nós duplicados, o que economiza tempo e sempre vem com uma solução.
Pesquisa em profundidade: Esta técnica começa no nó raiz e explora um conjunto de nós filhos conectados até atingir um nó de folha. Ele progride ramo por ramo até encontrar uma solução. A desvantagem deste algoritmo é que ele não pode verificar se há nós duplicados, o que significa que ele pode percorrer os mesmos caminhos do nó mais de uma vez. Na verdade, esse algoritmo pode não encontrar uma solução, o que significa que você deve definir um ponto de corte para evitar que o algoritmo faça uma busca infinita. Uma vantagem desta abordagem é que é eficiente na memória.
Pesquisa bidirecional: Esta técnica procura simultaneamente do nó raiz e do nó de objetivo até os dois caminhos de pesquisa se encontrarem no meio. Uma vantagem desta abordagem é que é tempo eficiente porque encontra a solução mais rápida do que muitas outras soluções de força bruta. Além disso, ele usa memória de forma mais eficiente do que outras abordagens e sempre encontra uma solução. A principal desvantagem é a complexidade da implementação, traduzindo-se em um ciclo de desenvolvimento mais longo.

Usando uma função heurística e de custo

Para algumas pessoas, a palavra heurística simplesmente parece complicada. Seria tão fácil dizer que o algoritmo faz um palpite e depois tenta novamente quando ele falha. Ao contrário dos métodos de força bruta, os algoritmos heurísticos aprendem. Eles também usam funções de custo para fazer melhores escolhas. Conseqüentemente, os algoritmos heurísticos são mais complexos, mas eles têm uma vantagem distinta na resolução de problemas complexos. Tal como acontece com os algoritmos de força bruta, existem muitos algoritmos heurísticos e cada um vem com o seu próprio conjunto de vantagens, desvantagens e requisitos especiais. A lista a seguir descreve alguns dos algoritmos heurísticos mais comuns:

Pesquisa heurística pura: O algoritmo expande os nós em ordem do seu custo.Ele mantém duas listas. A lista fechada contém os nós que já explorou; A lista aberta contém os nós que ainda precisa explorar. Em cada iteração, o algoritmo expande o nó com o menor custo possível. Todos os seus nós secundários são colocados na lista fechada e os custos individuais do nó filho são calculados. O algoritmo envia os nós filhos com um baixo custo de volta à lista aberta e exclui os nós filhos com um alto custo. Conseqüentemente, o algoritmo executa uma busca inteligente e baseada em custos para a solução.
A * search: O algoritmo rastreia o custo dos nós enquanto os explora usando a equação: f (n) = g (n) + h (n), onde
- n é o identificador do nó.
- g (n) é o custo de alcançar o nó até agora.
- h (n) é o custo estimado para alcançar o objetivo do nó.
- f (n) é o custo estimado do caminho de n para o objetivo.

A idéia é buscar os caminhos mais promissores primeiro e evitar caminhos caros.