將分支和綁定循環轉換爲使用Java Stream API

我有一個簡單的分支和綁定算法，適用於Traveling Salesman問題的變體，我認爲嘗試將其轉換爲使用Java 8 Stream API 。然而，我很難搞清楚如何去做，而不依賴副作用。將分支和綁定循環轉換爲使用Java Stream API

初始代碼

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

我拍了第一張照片，在將其轉換爲流API並具有以下想出了：

的Java 8版本

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;

主要問題是nodeConsumer必須引用bestPath和bound，它們是不是最終的變數。我可以讓它們成爲最終的AtomicReference變量來解決這個問題，但是我覺得這種做法違反了流API的精神。任何人都可以幫助我將最初的算法提煉成更加慣用的實現嗎？

來源

2015-09-30 Alex Pritchard

我不認爲你可以得到更好的東西，而不濫用API。 Stream API不適用於此類算法。不過，這個問題很有趣。 –

@TagirValeev感謝您的回覆。我仍然習慣了可用的新選項，並且難以確定事情是否困難，因爲我做錯了，或者因爲它不是一個理想的用法而困難。 –

我不知道是否使用reduce是解決這個問題的方法，因爲它允許您在不需要外部變量的情況下跟蹤值。

類似於以下內容（我不得不猜測上面的代碼的一些細節，但希望我在正確的軌道上）。

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

或者，你可以看看使用jOOλSeq（順序擴展流），並使用foldLeft代替。

來源

2015-10-18 10:24:17 lukens

將分支和綁定循環轉換爲使用Java Stream API

回答

相關問題