Как я могу получить кратчайший путь с алгоритмом BFS, используя карту в Java? - PullRequest
Новая
       23

Как я могу получить кратчайший путь с алгоритмом BFS, используя карту в Java?

0 голосов
/ 06 апреля 2019

Я играл с BFS, как описано здесь:

https://tutorialedge.net/artificial-intelligence/breadth-first-search-java/

Однако алгоритм, предложенный в руководстве, может только определить, был ли найден целевой узел. Кроме того, это позволяет иметь только 2 смежных узла.

Поэтому я сделал некоторые изменения в исходном алгоритме, однако я не могу заставить его работать так, как предполагалось.

Я безуспешно пытался объединить предложение от @ sandeepraj-tandon.

Подсчет уровней при поиске по ширине (расстояние между начальным узлом и целевым узлом)

РЕДАКТИРОВАТЬ: согласно вашему запросу я напишу здесь полный минимальный пример 

package davide.pugliese.v2;

import lombok.AllArgsConstructor;
import lombok.Data;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

@SuppressWarnings("Duplicates")
@Data
@AllArgsConstructor
public class DirectorV2 {

  public static void build() {
    Node station1 = new Node("1", new ArrayList<>());
    Node station2 = new Node("2", new ArrayList<>(Collections.singleton(station1)));
    Node station3 = new Node("3", new ArrayList<>(Arrays.asList(station1, station2)));
    Node station4 = new Node("4", new ArrayList<>(Arrays.asList(station2, station3)));
    Node station5 = new Node("5", new ArrayList<>(Arrays.asList(station4, station3)));
    Node station6 = new Node("6", new ArrayList<>(Arrays.asList(station5, station4)));
    new Bfs(station5 , station1).getShortestDistancePath();

  }
}


package davide.pugliese.v2;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.*;

@AllArgsConstructor
@NoArgsConstructor
@Data
public class Bfs {

  private Node startNode;
  private Node endNode;

  public void getShortestDistancePath() {

    List<Path> pathLists = new LinkedList<>();
    Queue<Node> sameLevelNodes = new LinkedList<>();

    if (startNode.equals(endNode)) {

      var path = Path.builder().startNode(startNode).endNode(endNode).distance(0).build();
      System.out.println(path);

    } else {

      sameLevelNodes.offer(startNode);

      var distance = 0;

      while (!sameLevelNodes.isEmpty()) {

        var current = sameLevelNodes.poll();
        if (current.equals(endNode)) {

          var newPath = new Path(startNode, current, distance);
          Set<Path> tempSet = new LinkedHashSet<>(pathLists);
          tempSet.add(newPath);
          pathLists = new LinkedList<>(tempSet);
          distance = 0;
        }

        if (!current.getNeighborList().isEmpty()) {
          sameLevelNodes.addAll(current.getNeighborList());
        }

        distance++;
      }
    }
    System.out.println(keepPathWithShortestDistance(pathLists));
  }

  private List<Path> keepPathWithShortestDistance(List<Path> paths) {

    List<Path> pathsCopy = new LinkedList<>(paths);

    for (Path path : paths) {
      for (Path path2 : paths) {
        if (path.getDistance() < path2.getDistance()) {
          pathsCopy.remove(path2);
        }
      }
    }
    return pathsCopy;
  }
}


package davide.pugliese.v2;

import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.List;

/**
 * The Node class represents a station in this tutorial and will as such have a string representing
 * the station's name. As well as an ArrayList of nodes that will store any instantiated nodes
 * children.
 */
@Data
@AllArgsConstructor
@NoArgsConstructor
@Builder
public class Node {

  public String name;
  private List<Node> neighborList;
}


package davide.pugliese.v2;

import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Data;
import lombok.NoArgsConstructor;

@Data
@Builder
@AllArgsConstructor
@NoArgsConstructor
public class Path {

    private Node startNode;
    private Node endNode;
    private Integer distance;

}

Алгоритм на данный момент возвращает: 

[Path(startNode=Node(name=5, neighborList=[Node(name=4, neighborList=[Node(name=2, neighborList=[Node(name=1, neighborList=[])]), Node(name=3, neighborList=[Node(name=1, neighborList=[]), Node(name=2, neighborList=[Node(name=1, neighborList=[])])])]), Node(name=3, neighborList=[Node(name=1, neighborList=[]), Node(name=2, neighborList=[Node(name=1, neighborList=[])])])]), endNode=Node(name=1, neighborList=[]), distance=1)]

Расчетное расстояние равно 1, тогда как оно должно быть 2 для выбранной пары узлов "5" и "1".

Что, очевидно, не правильно.

Graph illustration

Что не так в моем коде?

На графике показаны станции, ориентированные в произвольном порядке, отражающем выбранную при создании каждого узла со своим соседом.

Моя цель - рассчитать расстояние для каждого пути и выбрать тот, у которого кратчайшее расстояние.

Заранее благодарю за помощь.

РЕДАКТИРОВАТЬ: теперь я понимаю, что Path на самом деле не лучшее имя для этого класса, но у меня нет лучшего названия в данный момент ... Может быть, NodeCouple ...

...