Chuyển đổi nhánh vòng lặp và giới hạn để sử dụng API Java Stream

Question

Tôi có thuật toán Branch and Bound đơn giản hoạt động trên một biến thể của vấn đề Travel Salesman và tôi nghĩ sẽ rất thú vị khi thử và chuyển đổi nó để sử dụng API Java 8 Stream . Tôi đang có một thời gian khó khăn để tìm ra cách để làm điều đó mà không dựa vào tác dụng phụ, tuy nhiên.

Mã ban đầu

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); 
     } 
    } 
} 

Tôi mất một shot đầu tiên trong việc chuyển nó vào API Stream và đã đưa ra như sau:

Java 8 Version

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; 

Vấn đề chính là nodeConsumer phải tham chiếu bestPath và bound, không phải biến cuối cùng. Tôi có thể biến chúng thành các biến AtomicReference cuối cùng để làm việc xung quanh điều này, nhưng tôi cảm thấy loại này vi phạm tinh thần của API luồng. Bất cứ ai có thể giúp tôi chưng cất thuật toán ban đầu vào một thực hiện thành ngữ hơn?

Answer 1

Tôi tự hỏi nếu sử dụng reduce là cách để giải quyết vấn đề này, vì nó cho phép bạn theo dõi các giá trị mà không cần biến bên ngoài.

Điều gì đó như sau (Tôi đã phải đoán một vài chi tiết về mã trên của bạn, nhưng hy vọng tôi đang đi đúng hướng).

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(); 

Ngoài ra, bạn có thể xem xét sử dụng Seq trong jOOλ (một phần mở rộng tuần tự để Streams), và sử dụng foldLeft để thay thế.