Google Foobar Doomsday Fuel问题DFS解法隐藏测试用例失败排查

问题说明 #

• 所属场景：吸收马尔可夫链应用
• 输入：n阶非负整数状态转移矩阵，元素代表状态间跳转次数
• 要求：返回初始状态（状态0）到达各终止状态的精确概率，格式为各终止概率分子按顺序排列，末尾追加最简公共分母
• 限制：所有状态均存在到终止态的路径，矩阵最大为10×10
• 当前情况：示例用例可通过，部分隐藏用例失败

现有解法思路 #

1. DFS追踪所有到终止节点的无环路径，累加每条路径的概率作为终止节点的统计值
2. 跳过包含环的路径避免无限递归
3. 所有终止节点统计值除以总和归一化，转换为要求的输出格式

现有实现代码 #

import java.util.HashMap;
import java.util.Stack;

public class Solution {
    
    // for dealing with fractions
    public static class Fraction {
        long denom;
        long numer;
        
        public Fraction(long numer, long denom) {
            // if representing zeroes, don't try to find GCD
            if (numer == 0) {
                this.numer = numer;
                this.denom = denom;
                return;
            }
            // simplify regularly
            long gcd = findGCD(numer, denom);
            this.numer = numer / gcd;
            this.denom = denom / gcd;
        }
        
        // raise to a denom without simplifying.
        // for example 1/2 -> 2/4
        // newDenom must be a multiple of current denom
        public void raiseToDenom(long newDenom) {
            if (newDenom % this.denom != 0) {
                throw new RuntimeException("Invalid Denom!");
            }
            this.numer = this.numer * (newDenom / this.denom);
        }
        
        public Fraction multiply(Fraction other) {
            return new Fraction(numer * other.numer, denom * other.denom);
        }
        
        public Fraction divide(Fraction other) {
            return new Fraction(numer * other.denom, denom * other.numer);
        }
        
        public Fraction add(Fraction other) {
            long lcm = findLCM(denom, other.denom);
            long newNumer = numer * (lcm / denom) + other.numer * (lcm / other.denom);
            return new Fraction(newNumer, lcm);
        }
        
        public static long findGCD(long first, long second) {
            if (second == 0) {
                return first;
            }
            return findGCD(second, first % second);
        }
        
        public static long findLCM(long first, long second) {
            return (first / findGCD(first,second)) * second;
        }
    }
    
    public static class Solver {
        private int states; // matrix.length
        private int[][] matrix;
        private int[] matrixToFractionArr; // map state num -> fraction arr
        private Fraction[] fractionArr; // each entry is for one terminal state
        
        public Solver(int[][] matrix) {
            this.matrix = matrix;
            this.states = matrix.length;
            this.matrixToFractionArr = new int[states];
            int terminalIndex = 0;
            for (int i = 0; i < matrix.length; i++) {
                boolean isTerminal = true;
                for (int j = 0; j < matrix[i].length; j++) {
                    // if there is any entry that is not 0, this is not a terminal node...
                    // transitions to ownself is still considered terminal I think
                    if (matrix[i][j] != 0 && i != j) {
                        isTerminal = false;
                        break;
                    }
                }
                // map to the fraction array
                if (isTerminal) {
                    matrixToFractionArr[i] = terminalIndex;
                    terminalIndex ++;
                } else {
                    matrixToFractionArr[i] = -1;
                }
            }
            // fractions for terminal states only
            this.fractionArr = new Fraction[terminalIndex];
            for (int i = 0; i < terminalIndex; i++) {
                // initial probabilty 0.
                this.fractionArr[i] = new Fraction(0,1);
            }
        }
        
        public int sumArray(int[] array) {
            int count = 0;
            for (int i = 0; i < array.length; i++) {
                count += array[i];
            }
            return count;
        }
        
        // dfs method for setting the fractionArr correctly
        // carries the current probability by multiplying as we go, then adding it to terminal states
        // path represents which states is currently on path.
        public void setFractionsRecursively(Fraction currentProbability,
            int currentState, HashMap<Integer, Boolean> path) {
                
            int fractionIndex = matrixToFractionArr[currentState];
            if (fractionIndex != -1) {
                // it is a terminal node!
                // add the probability
                fractionArr[fractionIndex] = fractionArr[fractionIndex].add(currentProbability);
                return;
            }
            
            // not a terminal node, lets count the total outgoing
            int arrayTotal = sumArray(matrix[currentState]);
            // put this state on path
            path.put(currentState, true);
            for (int i = 0; i < states; i++) {
                int nextStateProb = matrix[currentState][i];
                if (nextStateProb == 0) {
                    // skip if cannot go this.
                    continue;
                }
                if (path.containsKey(i) && path.get(i)) {
                    // ensure that next state not on current path
                    // "i" is the next state to go to
                    continue;
                }
                Fraction nextProb = new Fraction(nextStateProb, arrayTotal);
                nextProb = nextProb.multiply(currentProbability);
                // dfs search
                setFractionsRecursively(nextProb, i, path);
            }
            // remove from path
            path.put(currentState, false);
            return;
        }
        
        // only can be used once unfortunately.
        public int[] solve() {
            // dfs related solution
            setFractionsRecursively(new Fraction(1,1), 0, new HashMap<Integer, Boolean>());
            // all fractions have been placed properly...
            
            // total "terminating probability"
            // essential because my method does not add up to one.
            Fraction total = new Fraction(0,1);
            for (int i = 0; i < fractionArr.length; i++) {
                total = total.add(fractionArr[i]);
            }
            
            // change probability to be over the "total" instead of one.
            for (int i = 0; i < fractionArr.length; i++) {
                fractionArr[i] = fractionArr[i].divide(total);
            }     
            
            // look for the LCM denominator to change all fractions to.
            long bestDenomLcm = 1;
            for (int i = 0; i < fractionArr.length; i++) {
                bestDenomLcm = Fraction.findLCM(bestDenomLcm, fractionArr[i].denom);
            }
            
            long[] answerArray = new long[fractionArr.length + 1];
            // raise all fractions to LCM denom
            for (int i = 0; i < fractionArr.length; i++) {
                fractionArr[i].raiseToDenom(bestDenomLcm);
                answerArray[i] = fractionArr[i].numer;
            }
            
            // the total (last entry) is basically the denominator
            answerArray[answerArray.length - 1] = bestDenomLcm;
            
            // look for a GCD to
            // simplify it more if possible....
            // [2, 4, 6, 8] -> [1, 2, 3, 4] for example.
            long bestGcd = bestDenomLcm;
            for (int i = 0; i < answerArray.length; i++) {
                if (answerArray[i] != 0) {
                    bestGcd = Fraction.findGCD(bestGcd, answerArray[i]);
                }
            }
            
            // required because I used long...
            int[] intAnswerArray = new int[answerArray.length];
            
            // simplify here
            for (int i = 0; i < answerArray.length; i++) {
                intAnswerArray[i] = (int) (answerArray[i] /= bestGcd);
            }
            return intAnswerArray;
        }
    }
    
    // method that is called by test cases.
    public static int[] solution(int[][] m) {
        Solver solver = new Solver(m);
        int[] answer = solver.solve();
        return answer;
    }
}

问题根因分析 #

• 核心算法逻辑错误：吸收马尔可夫链中，瞬态可以经过任意次环之后再进入终止态，你仅统计无环路径会漏掉所有带环的合法路径贡献的概率。哪怕后续做归一化，也无法修正概率比值的错误——因为不同终止态的漏算比例不是完全一致的。

举个简单反例验证：

转移矩阵：
[
[0, 1, 1], // 状态0到1、2的跳转次数各为1
[1, 0, 1], // 状态1到0、2的跳转次数各为1
[0, 0, 0]  // 状态2是终止态
]

正确概率：从状态0到终止态2的概率为2/3。你的解法仅统计无环路径：0->2（概率1/2）、0->1->2（概率1/2 * 1/2 = 1/4），总和为3/4，归一化后得到概率1，和正确结果完全不符。

修正建议 #

采用吸收马尔可夫链标准求解流程，保留你现有的分数运算逻辑保证精确性即可：

1. 区分瞬态和吸收态（终止态），将转移矩阵分块为单位矩阵I、零矩阵O、瞬态到吸收态转移矩阵R、瞬态间转移矩阵Q
2. 计算基本矩阵N = (I - Q)⁻¹
3. 吸收概率矩阵为N * R，其第一行就是初始状态0到各吸收态的精确概率
4. 将概率转换为题目要求的输出格式即可

内容的提问来源于stack exchange，提问作者hkcode