Program Assignment 1 — 主題樂園最佳遊園計畫

Spring 2026 演算法作業：以 DFS + Branch-and-Bound 搜尋多重權重圖上的限制式最佳遊園路線。

📋 專案說明

本系統將主題樂園模型化為一張多重權重圖 G = (V, E)，其中：

• 頂點 (V)：代表樂園設施（V1 入口廣場、V2~V6 五個遊樂設施）
• 邊 (E)：代表兩點之間的可通行路線
• 頂點權重：遊玩時間 Wt、金額 Wc、體力 We、偏好 Wp
• 邊權重：移動時間 wt、曝曬指數 ws

🎯 問題定義 (P1)

在時間、預算、體力與曝曬限制下，找出從 V1 出發並回到 V1、可遊玩設施數最多的路線。

評分順序：

1. 最大化可遊玩設施數
2. 若設施數相同，最大化偏好分數
3. 若仍相同，選擇總時間、花費與曝曬較低的路線

🧮 演算法

• 核心：DFS (深度優先搜尋) + Branch-and-Bound (分支界限法)
• 剪枝策略：
  • 限制剪枝：時間/預算/體力/曝曬超限即停止
  • 界限剪枝：樂觀上界無法超越最佳解即停止
  • 狀態支配：相同位置/選擇但資源更差的狀態直接捨棄

📂 檔案結構

├── index.html           # 互動式 Demo 頁面（含所有報告視覺化內容）
├── Running_Instance.md  # 文字版執行實例說明
└── README.md            # 本文件

🚀 使用方式

1. 直接雙擊 index.html 或用瀏覽器開啟
2. 選擇案例 1 / 2 / 3（或手動輸入限制條件）
3. 按下「▶ 執行 Demo」
4. 觀察最佳路線、執行紀錄與統計數據

📊 Demo 包含的報告章節

章節	內容
1-2	主題樂園範例地圖（含邊權重標註）
1-3	頂點資料與邊資料表
1-5.1	資料模型圖
1-7	使用者介面設計說明
2-4	範例推導（搜尋樹 + 步驟詳解）
3-1~3-3	互動式 Demo + 程式碼展示
3-4	三組測試案例結果
3-5	案例手算驗證
3-6	三組測試結果比較表
3-7	AI 工具協助項目
4-3	結論與反思

🔬 三組測試案例

案例	時間	預算	體力	曝曬
案例 1	70 min	300 元	20	不限
案例 2	90 min	300 元	20	20
案例 3	120 min	450 元	25	25