Wie kann ich die Größe der Warteschlange in BFS Suche begrenzen ~ Java

Question

Hier ist meine BFS-Suchmethode:

private void doBfs(HiRiQ node, ArrayList<HiRiQ> queue, ArrayList<HiRiQ> path, ArrayList<HiRiQ> visited) { 


     while(!queue.isEmpty()){ 

      HiRiQ current = queue.remove(0); 


      if(current.IsSolved()){ 
      current.print(); 
      System.out.println("Path found !"); 

      return; 

      } else { 

      if(current.getAllNextStates().isEmpty()){ return; } 

      else { 


       if(queue.contains(current)){ continue; } 

       else if (visited.contains(current)){ continue; } 


       else{ queue.addAll(current.getAllNextStates()); } 



      } 
       visited.add(current); 
      } 
     } 
     } 

Dieser Algorithmus beginnt angeblich von einer zapfen Solitär Puzzle Konfiguration und prüft alle Nachbarn-Konfigurationen, bis sie feststellt, die gelöste Konfiguration. Es scheint zu funktionieren, aber für jede Konfiguration braucht es wirklich lange Zeit, um die Lösung zu finden und zu finden. Eine Möglichkeit diesen Suchalgorithmus zu optimieren wäre, die Warteschlangengröße zu begrenzen, da ich nach einem gewissen Punkt die meiste Zeit damit verbringen würde, mehr Knoten in die Warteschlange zu stellen und sehr wenig Zeit für die Verarbeitung von Knoten zu haben. Irgendwann sollte ich aufhören, die Warteschlange zu füllen und einfach überprüfen, ob ich eine Lösung in der Warteschlange habe.

Wie könnte ich das erreichen? Danke

Answer 1

Ich würde vorschlagen, dass Sie iterative deepening depth-first search verwenden. Es wurde entwickelt, wenn Speicher eine große Sache war und naive BFS-basierte Lösungen einiger Grafikprobleme leicht den gesamten verfügbaren RAM auffressen konnten. Aber es tut, was Sie erreichen wollen, begrenzt die Größe der Warteschlange, garantiert die Suche nach dem kürzesten Pfad und ist schneller als BFS, wenn der Verzweigungsfaktor hoch ist.

Eine andere Möglichkeit, die Leistung Ihrer Lösung zu verbessern, wäre es, eine gute Heuristik zur Lösung des Rätsels zu finden. Sobald Sie die Heuristik haben, die Sie programmieren können, können Sie Ihr Glück mit A* algorithm

versuchen