在文字冒險類遊戲中想尋求達成最優結局（即某項值最高），應使用什麼數據結構或演算法？
文字冒險類遊戲是以精彩的劇情為賣點的遊戲，以文字敘述為主，並以CG或動畫為輔演齣劇情，並設有分支和多個結局。是冒險遊戲的一個分支，簡稱ADV，也叫電子小說，甚至也有直接使用AVG來作為縮寫。
如以遊戲中某個值（常見的比如某人物好感度...）為判斷依據，探索最優結局達成路線（即每一步應選什麼選項），應該使用什麼演算法或數據結構呢？
在文字冒險類遊戲中想尋求達成最優結局（即某項值最高），應使用什麼數據結構或演算法？
文字冒險類遊戲是以精彩的劇情為賣點的遊戲，以文字敘述為主，並以CG或動畫為輔演齣劇情，並設有分支和多個結局。是冒險遊戲的一個分支，簡稱ADV，也叫電子小說，甚至也有直接使用AVG來作為縮寫。如以遊戲中某個值（常見的比如某人物好感度...）為判斷依據，探索最優結局達成路線（即每一步應選什麼選項），應該使用什麼演算法或數據結構呢？
本來看了書記的答案後我覺得沒什麼好說的。畢竟我是屬於那種開老金都沒有負罪感的人，所以我為了自己寶貴的生命，一向是查攻略的。
但是仔細看了看題主的問題之後，我覺得這個問題還是有挖掘的潛力的。首先，在不考慮玩家感想的情況下（比如製作攻略），忽略掉考驗操作的部分，只要有SAVE/LOAD大法，我們只要用ctrl鍵一路快進過去就可以了。如果慢就多弄幾台機子一起，絕對是最快的方法。當然，這得保證製作方遵循規則（比如逆轉3中的一場質疑，無論質疑哪一句都會觸發一樣的第一句對話，很容易麻痹SL黨）。所以說，數據結構也好，演算法也好，都是為遊戲服務的，是廠商要考慮的問題。如果玩家去倒騰這個，只可能是逆推演算法來實現某個目的。
（勿忘初衷）
大部分的文字冒險遊戲，都是歷遍所有選項就肯定會觸發所有對話的遊戲（比如柚子社的廢萌作們）。蛋痛一點的，多經歷幾遍就可以了（比如初音島2，將遊戲的進程劃分成為幾個章節）。我玩過的遊戲中將後一點實現的比較徹底的就是歌夜十月了，幾乎玩玩之後整個人都沉浸在對未讀文本的詛咒之中……（本文提及的文字冒險遊戲多是指日本的GAL啦……）在這些模式中，能享受自虐式探索的遊戲樂趣的類型肯定不是廢萌要素，而是解謎要素了。所以下面我就以劇本差的可以請一個潤色的國產遊戲《霧之本境》來講講自己對廠商能怎麼噁心玩家：
在這一類遊戲中（再比如CL），真正可能有效的是數據結構與演算法是推不同的妹子，如果有需要則要用不同的方法多推幾次，如果有需要的話，男人和人外也……
（說到這裡，我不知道你們想到了什麼，反正我想到了《街》——無論你寫的多麼非線性的劇本，只要沒有難度，都能寫出一個線性的解（攻略）出來。）如果玩家只對個別角色發情怎麼辦？設置謎題是個辦法，更好、更普遍的方法是設立個不能第一次攻略的角色，然後隨便弄個糊弄人的TE就行了。（羊飼，說你呢。）所以鑒於你永遠不可能知道一個廠商的流程圖是怎樣的，所以你不可能直接在已知條件下快速的算出一個可能的特解（除非你被批評家或者攻略本劇透了）；而且出於你在不同遊戲中能做的事情不一樣的原因，也不可能製作出一個面對全部遊戲的通解出來（如果不算SL大法的話）。但是說到底，除了個別有個性的廠商和劇本以外，大部分的遊戲還是遵守了共通的「遊戲規則」的。只要遵循著「遊戲規則」，自然也就不會有問題了。當然，針對具體的諸如明星志願、美少女夢工廠的包涵策略要素遊戲，或是碧之軌跡這種不以ADV為核心的遊戲中的特定要素。為了達到最優結局，自然最好的演算法就是直接逆推出遊戲公司的演算法，或者找出最優解（或者某一特解）啦。
簡單來說去Baidu/Google啦！————————————劇透到底————————————最後貼一張網上收集的《霧之本境》的「特解」：1.還是算了
2.王用斌是童玲的前男友
3.讓雪憶回來
4.挺好的
5.支持賀雲舟的看法
6.賀雲舟怎麼還不回來
7.支持揚雨晴
8.我不想提起
9.（此處存檔SAVEDATE )
先選「和他一起逃出去」，進入雨晴結局「雨淚飄零」
讀取SAVEDATE
再選「放棄逃離」，會進入雪蓮結局「斬殺推理」「桃花續緣」
兩條線通關後會開啟副篇「無恙篇」，看過一次無恙篇會開啟正篇所有選項支（實際上主要是跟雪憶有關）
在正篇所有選項開啟後注意新增選項的選擇：
New1.繼續追問
New2.索性不睡，出去走走
New3.去走走
這樣就會進入雪憶結局「自由之夢」
雪憶線通關後會開啟副篇「息心篇」，這個再看完就可以收集滿CG了（不知道還有沒有隱藏情節了……）
by 星夜月華 轉載請註明
（說實話，看完這個對比之後還會有人想倒騰演算法嗎:-D）
LZ這個問題說：是否能依據遊戲中某些參數來判斷選擇是否正確，一步步推進，好像下棋一樣，給個策略優勢的判斷標準。而事實上是沒有這種參數的，即使有往往也是假象。
大部分ADV都是沒有好感度一說的。它的真實類型是電子小說，遊戲的形式是樹狀選擇枝。你的選擇決定的是前往哪條路線，與隱含參數無關。當然也有部分遊戲的好感參數決定某個路線是否可以進入。
以好感度為核心的遊戲一般都是標準AVG，比如同級生，實際是一種解謎遊戲。它是通過事件增加好感，而事件的發生要對應地點和時間。如果要製作一個窮舉式的自動程序，那就和下棋程序差不多了。但是這類遊戲往往存在關鍵事件的概念，事件之間是連鎖的，換句話說，遊戲里只有走得通走不通，好感度的漲跌只是要素之一，光盯著它是沒有任何意義的。
也就是說，自動攻略ADV，需要的不是下棋的程序，而是走迷宮的程序。程序要做的就是遍歷所有選項，直到你最後走出迷宮為止之前一切對路線的判斷全是沒有意義的。如果狀態存的下就動態規劃存不下只能裸搜了……對於一些特定的遊戲直接貪心也可以。
樹形分支可以簡化成二叉樹，剩下就是先序中序和後序遍歷的問題了。
大部分人的做法是看攻略。
首先題主的問題比較的模糊，根據我對該問題的理解如下：
對於一個玩家僅擁有選項決策的文字冒險類遊戲，是否存在一個記憶化或啟發式的搜索策略，使得在最短時間內，獲得所有人物的最好結局（GOOD END）對於該問題的解決方法會更偏重於從玩家而非計算機的角度來進行探索，因為畢竟我相信題主問這個問題的主要目的還是玩家在玩AVG類遊戲時如何在不看攻略的情況下獲得最好結局，對於計算機來說我相信最好的方法還是直接窮舉搜索， 在後文中我也會提到為什麼通過動態規劃或貪心等搜索策略不適用於AVG遊戲的原因。我認為大多數AVG遊戲都分為公共線和人物線兩個部分，在公共線走完之後會有一個檢查點，用以檢查所有人物的好感度多少和事件的完成度來決定你進入哪一條人物線。那麼這裡就衍生出一個比較簡單的策略，即：在遊戲初期確定一個要走的人物線，在所有選項中都偏向於她，並且盡量迴避其他的人物。
但是不要忘記遊戲廠商的目的：希望最大限度的讓玩家窮盡所有的劇情、CG。這樣就會導致幾乎所有的AVG遊戲為了維持遊戲時間都會採取的一個手段——周目限制，即玩家必須通關了某些人物線之後，某一個GOOD END才會開啟。玩家因此就不可能為了某一個GOOD END而制定一個最優的策略，也許你這一周目的所有選項對於你期望的GOOD END都是正確的，但僅僅由於你某幾條人物線沒有開啟，你一樣會獲得一個BAD END。那麼是否存在一個策略，讓我能夠每次選的線至少在這一周目一定有GOOD END呢？答案也是沒有的。比如有些遊戲是要先通了女主的線才能通配角線的（fate stay night等），比如有些遊戲要先把女配的線通了次啊能通女主線的（little busters，紅樓夢之北靜王與林黛玉等）因此對於計算機而言，最好的策略其實就是窮舉，因為對於AVG遊戲而言，你很難制定一個評價指標或者記憶狀態。對於玩家而言，認準一個要走的人物線，通過每次選項後的人物對話對這次選項進行相應的調整，並且反覆想辦法進入各條人物線打破周目限制，應該是最好的策略吧。當然相信很多AVG玩家也有體會，其實難的不是GOOD END。而是你想100%收集時，那些該死的BAD END，和不知道哪些選項組合之後會出現的一些額外的劇情和CG。寬搜
推薦閱讀：
※拳皇 13 是一款成功的遊戲嗎？
※如何評價《天下》手游？
※作為一個90後，有什麼養生手游推薦？
※如何看社交遊戲（Social Game）的市場以及產品走向？
※我們在遊戲里到底殺了多少人？