Qual é a complexidade do espaço da pesquisa abrangente?

Nov 07 2020

Ao usar o algoritmo de pesquisa em amplitude, é a complexidade do espaço $O(b^d)$, Onde $b$ é o fator de ramificação e $d$ o comprimento do caminho ideal (assumindo que realmente haja um)?

Respostas

nbro Nov 08 2020 at 04:29

A complexidade espacial do algoritmo de busca em amplitude é $O(b^d$) no pior caso , e corresponde ao maior número possível de nós que podem ser armazenados na fronteira de uma vez, onde a fronteira é o conjunto de nós (ou estados) que você está considerando atualmente para expansão.

Você pode dar uma olhada na seção 3.5 (página 74) do livro Artificial Intelligence: A Modern Approach (3ª edição, por Norvig e Russell) para obter mais informações sobre a complexidade de tempo e espaço de BFS.