java - 如何在 Java 中处理分支计算？

Question

我试图根据一个变量有多少个连接来找到最长的可能路径，而不需要重复连接。我想到的方法是创建一个列表，其中包含已经经过的所有点，但是当路径结束并且我需要检查新路径时，所有这些旧连接都保留在列表中。如何从初始点重新启动我的列表？

将其放入递归函数本身只会每次都清除列表。有比使用列表更好的选择吗？

相关代码:

package testapp;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.io.IOException;
import java.util.List;

class TestApp {   
    // Store list of objects we have already matched with
    static List<NumberObject> holdingList = new ArrayList<NumberObject>();
    
    //Test objects
    static int[] array1 = {2,2};
    static int[] array2 = {3,1};
    static int[] array3 = {2,1};
    static int[] array4 = {1,1};
    
    static NumberObject eight = new NumberObject(array1, 8);
    static NumberObject two = new NumberObject(array2, 2);
    static NumberObject three = new NumberObject(array3, 3);
    static NumberObject four = new NumberObject(array4, 4);
    // Test objects ^^
    
    public static int longestSequence(int[][] grid) {
        // TODO: implement this function
        // Code exists here not relevant to the problem

        //Setting up a new numberList array for testing
        NumberObject[] newNumberList = {eight, two, three, four};
        NumberObject[] connections1 = {two, four};
        NumberObject[] connections2 = {two, three};
        //Adding connections
        eight.connections = connections1;
        four.connections = connections2;
        
        for (NumberObject s: newNumberList){
          recursive(s);
        }
        return 0;
    }

    public static void recursive(NumberObject object){
            for (NumberObject x: holdingList){
                System.out.println(x);
            }
            
            if (!holdingList.contains(object)){
                holdingList.add(object);
                
                if (object.hasConnections()){
                    NumberObject[] newobject = object.getConnections();
                    
                    for(NumberObject y: newobject){
                        recursive(y);
                    }
                }
                else {
                    System.out.println(holdingList.size());
                    return;
                }
            }
            else {
                System.out.println(holdingList.size());
                return;
            }
        }
    

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int numRows = 0;
        int numCols = 0;
        String[] firstLine = reader.readLine().split("\\s+");
        numRows = Integer.parseInt(firstLine[0]);
        numCols = Integer.parseInt(firstLine[1]);

        int[][] grid = new int[numRows][numCols];

        for (int row = 0; row < numRows; row++) {
            String[] inputRow = reader.readLine().split("\\s+");

            for (int col = 0; col < numCols; col++) {
                grid[row][col] = Integer.parseInt(inputRow[col]);
            }
        }
        int length = longestSequence(grid);
        System.out.println(length);
    }
}

class NumberObject {
    int[] id;
    int value;
    NumberObject[] connections;
    //Constructor
    public NumberObject(int[] id, int value){
        this.id = id;
        this.value = value;
    }
    //print statement
    public String toString(){
        return ("NumberOject: Id = " + id + "\nValue = " + value);
    }
    //Check if it has connections
    public boolean hasConnections(){
        if (connections == null){
            return false;
        }
        else if (connections.length != 0){
            return true;
        }
        else 
            return false;
    }
    //Return the connections it has
    public NumberObject[] getConnections(){
        return connections;
    }
}

理想情况下，图像显示我想要发生的情况。相反，所有旧的分支连接都保留在 holdingList 上。应该注意的是，路径可以分支到两个以上的其他对象。

Answer 1

您可以将列表副本的实例作为参数传递给函数，而不是将列表存储在字段中。所以你的函数recursive的签名看起来像:

public static void recursive(NumberObject object, List<NumberObject> visited)

为了隐藏此实现细节，我建议编写两个函数，其中第二个函数仅将空列表传递给另一个函数。

<小时/>

但是，我会选择不同的方法，因为您的新列表获取的新列表与树中的条目一样多。在以下实现中，每个“树端”只有一个列表。此外，就像前面的建议一样，这使您的类(class)保持无状态。

static List<NumberObject> findLongestPath(NumberObject currentNode) {
        if (currentNode.getConnectedNodes().isEmpty()) {
            List<NumberObject> result = new ArrayList<>();
            result.add(currentNode);
            return result;
        }

        List<NumberObject> longestPath = currentNode.getConnectedNodes().stream()
                .map(PathFinder::findLongestPath)
                .max(Comparator.comparing(List::size))
                .get();

        longestPath.add(currentNode);
        return longestPath;
    }