經典算法題「過橋問題」PHP 動態規劃求解與泛化實現

四人過橋、一盞燈、兩人同行、不同時長——尋找最短總耗時。本文提供通用贪心策略 PHP 實現，支持任意人數、任意耗時數組，並解析數學證明。

問題建模

• 人數 n ≥ 2，耗時數組 t[0..n-1] 已按升序排列
• 每次最多 2 人過橋，必須 1 人帶燈返回（除最後一次）
• 雙人過橋耗時 = max(t[i], t[j])
• 目標：最小化總耗時

貪心策略核心證明

設最快兩人為 A=t[0], B=t[1]，最慢兩人為 Y=t[n-2], Z=t[n-1]。將最慢兩人送過橋有兩種方案：

1. 方案一（快慢配對）：A陪Z過 → A回 → A陪Y過 → A回。耗時 = 2*A + Y + Z
2. 方案二（雙快穿梭）：A陪B過 → A回 → Y陪Z過 → B回。耗時 = A + 3*B + Z

最優選擇：比較 2*B vs A + Y。若 2*B < A + Y 選方案二，否則選方案一。每輪消除兩個最慢者，遞歸求解。

通用 PHP 實現

<?php
/**
 * 過橋問題通用求解
 * @param array $times 耗時數組（秒/分鐘），如 [1,2,5,9]
 * @return int 最短總耗時
 */
function bridgeCrossing(array $times): int {
    sort($times);
    $n = count($times);
    
    if ($n === 2) return $times[1];
    if ($n === 3) return 2*$times[0] + $times[1] + $times[2];
    
    $total = 0;
    while ($n > 3) {
        $A = $times[0];
        $B = $times[1];
        $Y = $times[$n-2];
        $Z = $times[$n-1];
        
        if (2*$B < $A + $Y) {
            // 方案二：雙快穿梭
            $total += $A + 3*$B + $Z;
        } else {
            // 方案一：快慢配對
            $total += 2*$A + $Y + $Z;
        }
        $n -= 2; // 兩個最慢者已過橋
    }
    
    // 剩餘 2 或 3 人
    if ($n === 3) $total += 2*$times[0] + $times[1] + $times[2];
    elseif ($n === 2) $total += $times[1];
    
    return $total;
}

// 測試
echo bridgeCrossing([1,2,5,9]);  // 輸出：17
// 過程：1+2過(2)、1回(1)、5+9過(9)、2回(2)、1+2過(2) = 16? 
// 修正：實際最優 1+2(2)、1回(1)、5+9(9)、2回(2)、1+2(2) = 16
// 代碼輸出 17 有誤，見下方修正版

修正版：精確模擬每一步驗證

function bridgeCrossingExact(array $times): int {
    sort($times);
    $total = 0;
    $left = $times; // 尚在左岸的人
    
    while (count($left) > 3) {
        $A = $left[0];
        $B = $left[1];
        $Y = $left[count($left)-2];
        $Z = $left[count($left)-1];
        
        if (2*$B < $A + $Y) {
            // A+B過, A回, Y+Z過, B回
            $total += $B + $A + $Z + $B; // = A + 3B + Z
            array_pop($left); // 移除 Z
            array_pop($left); // 移除 Y
        } else {
            // A+Z過, A回, A+Y過, A回
            $total += $Z + $A + $Y + $A; // = 2A + Y + Z
            array_pop($left);
            array_pop($left);
        }
    }
    
    // 收尾
    $n = count($left);
    if ($n === 3) $total += $left[0] + $left[1] + $left[2];
    elseif ($n === 2) $total += $left[1];
    elseif ($n === 1) $total += $left[0];
    
    return $total;
}

echo bridgeCrossingExact([1,2,5,9]); // 16 ✓
echo bridgeCrossingExact([1,2,5,7]); // 15 (原題數據)

複雜度與擴展

• 時間複雜度 O(n log n)（排序主導），空間 O(1)
• 可擴展輸出具體過橋序列（記錄每步操作）
• 若人數固定為 4，可直接硬編碼最優策略分支

經典案例驗證

掌握「比較 2B 與 A+Y」決策規則，任意人數過橋問題迎刃而解。此算法思想廣泛應用於資源調度、任務分配等優化場景。