Antes de tudo, é uma afirmação e não estou procurando respostas diretas, mas a complexidade da melhor solução, como você pode estar pensando.

Este é o problema conhecido do caminho mais curto entre 2 pontos em uma matriz (Início e Fim), enquanto há obstáculos no caminho. Move aceitáveis é para cima, baixo, esquerda e direita. Digamos que ao mover eu carrego sth e o custo de cada movimento é 2. Existem pontos na matriz (vamos chamá-los de pontos B) onde eu posso deixar esse sth em um ponto B e buscá-lo em outro ponto B. O custo do dumping sth no ponto B é 1 e o custo da retirada do sth de um ponto B é 1 novamente. Sempre que me movo sem esse padrão, meu custo agora é de 1. O que penso da solução é transformar a matriz em uma árvore e aplicar um BFS. No entanto, isso funciona sem os pontos B.

Sempre que levo em conta, a complexidade dos pontos B chega ao pior cenário N ^ 2. Aqui está um exemplo :

S - - -
- - - -
B - - B
- - O E

S = Início, E = Fim, B = B ponto para largar sth, O = obstáculo Então, eu começo com S descendo até o ponto B (2 * 2 = 4 pontos) deixo sth no movimento do ponto B (1 ponto) direita direita (2 * 1 = 2 pontos), pegue-a (1 ponto), desça 2 pontos = total de 10 pontos.

O que eu pensei foi construir a árvore com nós todos os pontos B, no entanto, isso criaria um gráfico cíclico muito denso de quase (V-1) * (V-1) arestas que leva o algoritmo nos limites de N ^ 2 apenas para criar o gráfico . Esse é o pior cenário, como acima:

S b b b
b b b b
b b b b 
b b b E

Outra opção que pensei foi a de calcular primeiro os caminhos mais curtos sem os pontos B. Em seguida, faça as iterações em cada iteração: Primeiro, faça bfs em S e o mais próximo de B tenha BFS em E e o mais próximo B. Verifique se há um caminho entre B mais próximo de S e B mais próximo de E. Se houver, eu veria se o caminho é menor do que o caminho mais curto comum, com obstáculos. Se isso for maior, não haverá um caminho mais curto (nenhum teste ganancioso). Se não houver caminho entre os 2 pontos B, tente o segundo mais próximo de S e tente novamente. Se não houver um caminho novamente, o segundo mais próximo de E e mais próximo de S. No entanto, não sou capaz de calcular a complexidade deste no pior cenário, além de não haver um teste ganancioso que avalie isso. Qualquer ajuda para calcular a complexidade ou até mesmo apontar a melhor solução de complexidade (não a solução, mas apenas a complexidade) seria muito apreciada