Algoritmos de Procura Informada

Functions
int	TProcuraConstrutiva::MelhorPrimeiro (int nivel=0)
	Executa a procura melhor primeiro, algoritmo informado.
int	TProcuraConstrutiva::AStar (int limite=0)
	Executa a procura A*, algoritmo informado.
int	TProcuraConstrutiva::IDAStar (int upperBound=0)
	Executa a procura IDA*, algoritmo informado.
int	TProcuraConstrutiva::BranchAndBound (int upperBound=0)
	Executa o algoritmo Branch-and-Bound, um algoritmo informado.

Detailed Description

Métodos que executam algoritmos de procura utilizando heurística para orientar a procura.

Function Documentation

AStar()

int TProcuraConstrutiva::AStar

(

int

limite = 0

)

Executa a procura A*, algoritmo informado.

Parameters

limite

Com valor 0, executa sem limite. Se maior que 0, limita o número de estados gerados não expandidos.

Returns

Retorna o valor da solução, ou -1 em caso de falha.

Este algoritmo é semelhante ao Custo Uniforme, mas os estados são ordenados pelo lower bound, definido como o custo acumulado somado à heurística, ou seja, o mínimo custo ótimo da instância. Dessa forma, os estados com menor lower bound são expandidos primeiro, o que preserva a propriedade de optimalidade.

Note

Se o limite do número de estados for atingido, os estados gerados com maior lower bound serão removidos.

O parâmetro parametro[pesoAStar].valor, com valor padrão 100, indica o peso (em percentagem) que a heurística terá no cálculo do lower bound. Se esse valor for reduzido, a heurística terá menor peso (pode chegar a 0, fazendo com que o algoritmo se comporte como o Custo Uniforme). Se for aumentado acima de 100, a heurística terá mais influência, aproximando a estratégia do Melhor Primeiro. Dessa forma, esse parâmetro permite modelar uma gama de estratégias entre Custo Uniforme, A* e Melhor Primeiro, o que pode resultar em melhor desempenho para determinados problemas.

Se a procura for interrompida, é possível extrair um lower bound, embora isso não permita a obtenção de uma solução.

See also

CustoUniforme(), MelhorPrimeiro(), EAlgoritmo, ExecutaAlgoritmo();

Definition at line 518 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

BranchAndBound()

int TProcuraConstrutiva::BranchAndBound

(

int

upperBound = 0

)

Executa o algoritmo Branch-and-Bound, um algoritmo informado.

Parameters

upperBound

Se 0, executa a procura sem limite. Se for um valor positivo, efetua a procura limitada por esse upper bound.

Returns

Retorna o valor da solução, ou -1 em caso de falha.

Este algoritmo opera de forma semelhante ao Melhor Primeiro, mas, após encontrar uma solução, continua a explorar, eliminando todos os ramos cujo lower bound indique que não há possibilidade de melhorar a solução atual.

Se o algoritmo iniciar com um upperBound definido, funcionará como se essa solução já tivesse sido encontrada, descartando todos os ramos que possam levar a soluções de custo igual ou superior. Embora isso possa resultar na exclusão de ramos muito longos, também podem remover ramos que eventualmente pudessem conduzir à solução. Caso o algoritmo retorne sem uma solução, não se pode afirmar com certeza que ela não exista.

Note

Se a procura for interrompida, é possível extrair um upper bound, apesar de não haver garantia de que seja o ótimo.

See also

MelhorPrimeiro(), EAlgoritmo, ExecutaAlgoritmo();

Definition at line 471 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

IDAStar()

int TProcuraConstrutiva::IDAStar

(

int

upperBound = 0

)

Executa a procura IDA*, algoritmo informado.

Parameters

upperBound

Se 0, executa a procura iterativa. Se for um valor positivo, efetua a procura limitada por esse upper bound.

Returns

Retorna o valor da solução, ou -1 em caso de falha.

Este algoritmo funciona similarmente ao Melhor Primeiro, mas limita a expansão da árvore com base no lower bound atual (custo acumulado mais heurística), em vez de limitar a profundidade. Trata-se de uma versão iterativa cuja nova limitação é determinada pelo melhor valor (mais baixo) dentre os estados descartados na iteração anterior, garantindo a obtenção da solução ótima.

A ordem de expansão dos estados é a mesma do A*, pois utiliza o mesmo critério de lower bound. Porém, por ser um algoritmo de procura em profundidade, não sofre problemas de memória.

Note

Se a procura for interrompida, é possível extrair um lower bound, embora isso não permita a obtenção de uma solução.

See also

MelhorPrimeiro(), AStar(), EAlgoritmo, ExecutaAlgoritmo();

Definition at line 417 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

MelhorPrimeiro()

int TProcuraConstrutiva::MelhorPrimeiro

(

int

nivel = 0

)

Executa a procura melhor primeiro, algoritmo informado.

Parameters

nivel

Se 0 ou menor, efetua a procura em profundidade sem limite. Se um valor positivo, efetua a procura limitada a esse nível de profundidade.

Returns

Retorna o valor da solução, ou -1 em caso de falha.

Este algoritmo funciona similarmente à procura em profundidade primeiro, mas os sucessores são ordenados de acordo com o valor da heurística. Assim, os estados com menor valor de heurística em cada nível são explorados primeiramente. Note que não garante a solução ótima e a implementação é recursiva.

See also

ProfundidadePrimeiro(), EAlgoritmo, ExecutaAlgoritmo();

Definition at line 388 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function: