Caminho mais curto em matrizes 2D

*...*..D .G..*..... **...**. .S....*. ........ ...G**.. ........ .G..*... 

Aqui está a matriz 2D onde
S-Source
Destino-D
O ponto G deve ser visitado
“.” Caminhos gratuitos
“*” Bloquear Caminhos
Você pode me ajudar qual seria o algoritmo eficiente para encontrar o comprimento do pathi mais curto em java
Somente movimentos horizontais e verticais são possíveis

Para encontrar a distância mais curta desde o ponto start até todos os outros pontos no mapa, você pode usar um BFS . Código de amostra:

 public void visit(String []map , Point start){ int []x = {0,0,1,-1};//This represent 4 directions right, left, down , up int []y = {1,-1,0,0}; LinkedList q = new LinkedList(); q.add(start); int n = map.length; int m = map[0].length(); int[][]dist = new int[n][m]; for(int []a : dist){ Arrays.fill(a,-1); } dist[start.x][start.y] = 0; while(!q.isEmpty()){ Point p = q.removeFirst(); for(int i = 0; i < 4; i++){ int a = px + x[i]; int b = py + y[i]; if(a >= 0 && b >= 0 && a < n && b < m && dist[a][b] == -1 && map[a].charAt(b) != '*' ){ dist[a][b] = 1 + dist[px][py]; q.add(new Point(a,b)); } } } } 

O segundo caminho do problema é na verdade um problema de vendedor ambulante , então você precisa converter do gráfico original para um gráfico que only contains G,D and S points , com o weight de cada borda neste gráfico sendo o shortest path between them in original path . Daí em diante, se o número de G for pequeno (menos de 17), você pode usar dynamic programming and bitmask para resolver o problema.

Aqui há muitos algoritmos como dijkstra ou BFS, mas se você precisa aprender um algoritmo de localização de caminhos, sugiro o algoritmo A * , pois é mais rápido que dijkstra ou BFS e pode ser facilmente implementado em uma matriz 2D. Como no caso do nó must visit, você pode tentar todas as seqüências nas quais você visita os nós, por exemplo, dizer S->G1->G2->G3->D encontrar o mínimo para este caminho como min(S,G1)+min(S,G2)+min(G3,D) . tente todas as permutações do G's e obtenha o mínimo de todas.

Este é um problema simples de algoritmo de pesquisa de Breadth First. Isso é chamado de técnica de preenchimento, que é um tipo de algoritmo de pesquisa Breadth First. Leia a partir daqui. Você também pode aprender o primeiro algoritmo básico da Breadth daqui. Isso também poderia ser resolvido por outras técnicas como Dijkstra ou Floyd warshal. Mas a primeira pesquisa da Breadth é mais fácil de entender.