由於沒有打 SC (StarCraft), 不過應該和 AOC 差不多 (其實這些即時戰略遊戲應該都不大差別)
即是說, 給出一個 AOC 的局況, 判斷某一方是否能勝出
文中用的 NPC 問題是 PLANAR GRAPHS HAMILITON PATH, 把判斷 "圖 G 是否存在 HAMILITON PATH" 轉化成判斷 "此 SC 局況某方是否能勝出", 從而得出 SC 是 NP-HARD 的結論
類似的, 現在要選一個 NPC 問題, 把它轉化成 AOC 中的局況
想到的是 PLANAR GRAPHS VERTEX COVER
這個問題即使限制 degree 不大於 3 仍是 NPC 的 (見 Wikipedia)
即是說, 給出圖 G, 是否能選取不多於 k 個頂點覆蓋所有的邊
現假設有玩家 A 和 B
玩家 A 有 |E| 隻劍兵, 對應著 |E| 條邊, 而且是被困著的 (例如地圖是海, 劍兵在孤島)
玩家 B 則沒有村民和軍隊, 但有 |V| 座弓箭場 (在 |V| 個島上) 和剛好夠資源生產 k 隻茅兵
對於邊 (u, v), 要做到在島 u 生產的茅兵能射到這條邊的劍兵但又不能走到島 v
具體方法是
即是說, 在某個島生產茅兵能殺掉相鄰邊上的玩家 A 劍兵
玩家 B 能勝出的唯一方法是殺掉所有劍兵, 顯然的, 這對應著圖 G 有 size k 的 vertex cover
即是說, 如果懂得判定 AOC 的勝負問題, 則懂得判定 planar 的 VC 問題
得出 AOC 是 NP-HARD 的
ps0. 更多的遊戲
ps1. AOC 今年會更新! :D
No comments:
Post a Comment