JavaストリームAPIを使用するためにブランチとバウンドループを変換する

Question

私はTraveling Salesmanの問題の変形で動作する単純なブランチアンドバウンドアルゴリズムを使用しています。これを試してみて、Java 8 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の精神に違反しているような気がします。初期のアルゴリズムをより慣用的な実装に汲み上げるのを誰かが助けてくれますか？

Answer 1

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を使用しています。