Problema da perda na floresta

Problema de matemática: em aberto:

Qual é o melhor caminho a se seguir quando perdido em uma floresta?

O problema da perda na floresta de Bellman é um problema de optimização não resolvido em geometria, originado em 1955 pelo matemático americano Richard E. Bellman . O problema é frequentemente formulado da seguinte forma: “Um caminhante se perde em uma floresta cujas formas e dimensões são precisamente conhecidas por ele. Qual é o melhor caminho para ele seguir para escapar da floresta? " Normalmente, presume-se que o caminhante não sabe o ponto de partida ou a direção que está olhando. O melhor caminho é aquele que possui a menor distância em seu pior caso a percorrer antes de chegar à orla da floresta. Outras variações do problema também foram estudadas.

Uma solução comprovada só é conhecida para alguns formatos ou classes de formatos de floresta. Uma solução geral seria na forma de um algorismo que recebe o formato da floresta e devolve o caminho a se seguir. Embora as aplicações do mundo real não sejam aparentes, o problema cai em uma classe de problemas de optimização geométrica, incluindo estratégias de busca que são de importância prática. Uma motivação maior para o estudo foi a conexão com o problema da minhoca de Moser . Ele foi incluído em uma lista de 12 problemas descritos pelo matemático Scott W. Williams como "problemas de um milhão de dólares" porque ele acreditava que as técnicas envolvidas em sua resolução valeriam pelo menos um milhão de dólares para a matemática.