Java Stream API'sini kullanmak için Branch ve Bound döngüsünü dönüştürün

Question

Traveling Salesman sorununun bir varyantı üzerinde çalışan basit bir Branch ve Bound algoritmasına sahibim ve Java 8 Stream API'sini kullanmaya çalışıp bunu dönüştürmenin eğlenceli olacağını düşündüm. . Bununla birlikte, yan etkilere dayanmadan nasıl yapılacağını bulmakta zorlanıyorum.

İlk Kod

int bound = Integer.MAX_VALUE; 
List<Location> bestPath = null; 

while(!queue.isEmpty()) { 
    Node curr = queue.poll(); 
    //bound exceeds best, bail 
    if (curr.getBound() >= bound) { 
     return bestPath; 
    } 
    //have a complete path, save it 
    if(curr.getPath().size() == locations.size()) { 
     bestPath = curr.getPath(); 
     bound = curr.getBound(); 
     continue; 
    } 
    //incomplete path - add all possible next steps 
    Set<Location> unvisited = new HashSet<>(locations); 
    unvisited.removeAll(curr.getPath()); 
    for (Location l : unvisited) { 
     List<Location> newPath = new ArrayList<>(curr.getPath()); 
     newPath.add(l); 
     Node newNode = new Node(newPath, getBoundForPath(newPath)); 
     if (newNode.getBound() <= bound){ 
      queue.add(newNode); 
     } 
    } 
} 

Ben Stream API dönüştürerek bir ilk ateş etti ve aşağıdaki ile geldi:

Java 8 Sürüm

Consumer<Node> nodeConsumer = node -> { 
    if(node.getPath().size() == locations.size()) { 
     bestPath = node.getPath(); 
     bound = node.getBound(); 
    } else { 
     locations.stream() 
      .filter(l -> !node.getPath().contains(l)) 
      .map(l -> { 
       List<Location> newPath = new ArrayList<>(node.getPath()); 
       newPath.add(s); 
       return new Node(newPath, getBoundForPath(newPath)); 
      }) 
      .filter(newNode -> newNode.getBound() <= bound) 
      .forEach(queue::add); 
    } 
}; 

Stream.generate(() -> queue.poll()) 
    .peek(nodeConsumer) 
    .filter(s -> s.getBound() > bound) 
    .findFirst(); 

return bestPath; 

Asıl sorun, nodeConsumer'ın bestPath'a başvurması ve son değişkenler değil. Bu konuda çalışmak için son AtomicReference değişkenlerini yapabilirim, ancak bu tür akış API'sinin ruhunu ihlal ediyor gibi hissediyorum. İlk algoritmayı daha aptalca bir uygulamaya dönüştürmeme yardım eden var mı?

Answer 1

reduce'u kullanmanın, dışsal değişkenlere ihtiyaç duymadan değerleri izlemenize izin verdiğinden emin olmanızın yolu budur.

Aşağıdaki gibi bir şey (yukarıdaki kodunuzun ayrıntılarından birkaçını tahmin etmek zorunda kaldım, ancak umarım doğru yolda olduğumu umuyorum).

final BiFunction<Entry<Integer, List<Location>>, Node, Entry<Integer, List<Location>>> accumulator 
     = (identity, node) -> { 
      if (node.getPath().size() == locations.size()) { 
       return new SimpleEntry<>(node.getBound(), node.getPath()); 
      } else { 
       locations.stream() 
        .filter(l -> !node.getPath().contains(l)) 
        .map(l -> { 
         List<Location> newPath = new ArrayList<>(node.getPath()); 
         newPath.add(l); 
         return new Node(newPath, getBoundForPath(newPath)); 
        }) 
        .filter(newNode -> newNode.getBound() <= identity.getKey()) 
        .forEach(queue::add); 
       return identity; 
      } 
     }; 

    final BinaryOperator<Entry<Integer, List<Location>>> combiner 
     = (left, right) -> left.getKey() < right.getKey() ? left : right; 

    final Entry<Integer, List<Location>> identity 
     = new SimpleEntry<>(Integer.MAX_VALUE, null); 

    final List<Location> bestValue = Stream.generate(queue::poll) 
     .reduce(identity, accumulator, combiner) 
     .getValue(); 

Alternatif olarak, jOOλ içinde Seq (Akışları için sıralı uzantısı) kullanarak bakmak olabilir ve bunun yerine foldLeft kullanın.