如何在棋盘游戏中找到最赚钱的路径

Question

假设我们有一个这样的棋盘： 我们想要找到从左到右最赚钱的路径，移动模式如下： 例如，在这个棋盘中，最赚钱的路径是: 即 {2, 0} -> {2, 1} -> {3, 2} -> {3, 3}

我编写了以下代码:

import java.util.*;

public final class Board {

    private final int[][] board;
    private final int n;

    public Board(int n) {
        board = new int[n][n];
        this.n = n;
        generateBoard();
    }

    public static class Node {

        public int x;
        public int y;
        public int value;

        public Node(int x, int y, int value) {
            this.x = x;
            this.y = y;
            this.value = value;
        }

        @Override
        public String toString() {
            return "{" + x + ", " + y + "}";
        }

    }

    public static class Path implements Comparable<Path> {

        private LinkedList<Node> path = new LinkedList<>();

        public Path() {
        }

        public Path(List<Node> nodes) {
            this.path.addAll(nodes);
        }

        public void addLast(Node node) {
            path.addLast(node);
        }

        public void removeLast() {
            path.removeLast();
        }

        public List<Node> get() {
            return path;
        }

        public int getProfit() {
            return path.stream().map(node -> node.value).mapToInt(value -> value).sum();
        }

        @Override
        public String toString() {
            return path.toString();
        }

        @Override
        public int compareTo(Path o) {
            return getProfit() > o.getProfit() ? 1 : -1;
        }

    }

    public void generateBoard() {
        Random random = new Random();
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < n; y++) {
                board[x][y] = random.nextInt(200) + 1 - 100;
            }
        }
    }

    public void printBoard() {
        for (int[] b : board) {
            System.out.println(Arrays.toString(b));
        }
    }

    public Path findTheMostProfitablePath() {
        TreeSet<Path> paths = new TreeSet<>();
        for (int x = 0; x < n; x++) {
            visit(new Node(x, 0, board[x][0]), paths);
        }
        return paths.last();
    }

    private void visit(Node root, Collection<Path> paths) {
        Stack<Node> stack = new Stack<>();
        stack.add(root);
        Node node;
        Path currentPath = new Path();
        while (!stack.isEmpty()) {
            node = stack.pop();
            currentPath.addLast(node);
            List<Node> children = getChildren(node.x, node.y);
            if (children == null) {
                paths.add(new Path(currentPath.get()));
                currentPath.removeLast();
            } else {
                stack.addAll(children);
            }
        }
    }

    private List<Node> getChildren(int x, int y) {
        if (y == n - 1) {
            return null;
        }
        y++;
        List<Node> children = new LinkedList<>();
        if (x == 0) {
            children.add(new Node(x, y, board[x][y]));
            children.add(new Node(x + 1, y, board[x + 1][y]));
        } else if (x == n - 1) {
            children.add(new Node(x - 1, y, board[x - 1][y]));
            children.add(new Node(x, y, board[x][y]));
        } else {
            children.add(new Node(x - 1, y, board[x - 1][y]));
            children.add(new Node(x, y, board[x][y]));
            children.add(new Node(x + 1, y, board[x + 1][y]));
        }
        return children;
    }

    public static void main(String[] args) {
        Board board = new Board(3);
        System.out.println("Board :");
        board.printBoard();
        System.out.println("\nThe most profitable path :\n" + board.findTheMostProfitablePath());
    }

}

但是它无法找到路径...

输出：

Board :
[-7, 1, 18]
[88, 56, 18]
[-18, -13, 100]

The most profitable path :
[{1, 0}, {2, 1}, {1, 1}, {2, 2}]

我的代码有什么问题吗？

我知道这不是寻找最赚钱的路径的最佳算法，而且它非常慢。在一个 n*n 的棋盘上，路径的数量为：

n * 2 ^ (n-1) < number of paths < n * 3 ^ (n-1)

在这个算法中，我们会检查所有路径，以找到最赚钱的那一条。

谢谢。

- FaNaJ

---

A) 算法不好。有一个线性时间算法（与棋盘上的方块数量成正比）。 B) 你的算法问题在于“visit”方法。它做了一些本不应该做的花哨操作。 - Ordous

Answer 1

你正在解决最长路径问题，通常情况下是NP完全问题。但是，在你的情况下，你实际上有一个有向无环图，因此可以使用以下递归公式获得有效的解决方案：

D(i,-1) = D(i,m) = -INFINITY //out of bounds
D(-1,j) = 0   [  j>=0  ]     //succesful path
D(i,j) = max{ D(i-1, j-1) , D(i-1,j),D(i-1,j+1)} + A[i][j] //choose best out of 3

通过应用动态规划技术来实现这个公式，可以达到高效的O(n*m)最优解决方案。

完成后，对最右列进行简单扫描，即可找到“最有利可图”的路径目的地，然后通过回溯上面的内容，在每一步写下每个决策，即可重构实际路径。

- amit

---

@user3767784，你有什么不清楚的吗？你是否熟悉动态规划的概念？如果不熟悉，建议你去了解一下，它是一个强大的工具。当你熟悉了它之后，你应该能够从这个答案中理解如何找到一个高效的解决方案。关于问题在一般情况下是NP-Complete的，而你的问题是DAG的这一事实，这是一个好知道的事实，但并不是理解所提出的DP解决方案所必须的。 - amit