如果讓你來實現最近很火的「三姑六婆」應用，打算用怎樣的數據結構和演算法來做？

01-14

今天簡單想了一下。感覺首先做之前要理清所有的親屬關係，這個是肯定的。接下來可以把「自己」放在樹的中間層，每一個「的「就往上，逐層去找。一開始想用」+1「的方式去代表向上查找，但是後來一想肯定不行，因為」+2 = +1+1「，到最後肯定會亂掉。於是又想到是不是可以用指針？但是感覺這樣子也會比較混亂。。。
搜了一下網上有一張大概的樹形結構圖，是否可以使用數據結構中較為經典的某種查找演算法來實現準確找到稱呼名？或者大家有沒有其它好的實現方法，想聽聽大家的看法。

一年前我試圖解決一個理論問題: 給定可以用的詞語和兩個人的親屬關係, 用最短的語句描述兩個人之間的關係. 三姑六婆出來的時候, 想知道他們的程序是怎麼實現的. 我問了作者, 這是作者的回復.

In our program, we have a list of relations mapping. Each mapping contains 3 values. For example, the relation "父親的哥哥 = 伯父", 3 values are 父親, 哥哥, 伯父.

In each step of the calculation, the program search a relation with first 2 values equals to the current answer and the new parameter. If a relation is found, the answer will be updated to the 3rd value.
Since the number of names we found is around less than 500, we do not have any optimization to shorten the description.

能使用樹的前提是家族中無亂倫的情況

...這個問題沒有你想的那麼簡單的我轉個陳皓的鏈接你看下吧..軟體真的好難做啊

【三姑】尼姑道姑卦姑

尼姑：佛教中出家修行的女子；

道姑：女道士；

卦姑：專門給人卜卦或算命的婦人，屬宗教人士，以占卜、算命、扶乩等為業；

【六婆】牙婆媒婆師婆虔婆藥婆穩婆

牙婆：牙，拐賣人口的婦女；專門販賣人口的人口販子，專為人買賣奴婢、妾侍，販賣胭脂、花粉又居中介紹買賣；

媒婆：媒，婚姻介紹業；專為人介紹姻親的女性；

師婆：師，就是巫婆；專門畫符施咒、請神問命的巫婆；

虔婆：虔：甜言蜜語不幹正事的，如老鴇；妓院內的鴇母，開設秦樓楚院、媒介色情交易的婦人，即淫媒；

藥婆：葯，販賣假藥；專門賣葯的女人，即今捉牙蟲，賣安胎、墮胎藥之類；

穩婆：穩，為官家接生婆；專門接生的接生婆，如果發現女屍，亦會由穩婆負責驗查是否被人先奸後殺；

六婆是各種專業的名稱，有時一人可以身兼數職。

這個基本上就是模式匹配和查找替換，比如把「·的哥哥的哥哥·」換成「·的哥哥·」、把「我的父親的弟弟·」換成「我的叔叔·」。

就是個有限狀態自動機。

Deterministic finite automaton

狀態 = {我,父親，母親，伯父等全部稱謂 }

字母表 = { 兄，弟，姐，妹，夫，妻等所有直接關係}

轉移函數 = { f(父，兄) = 伯父,f(兄,兄) = 兄,按照實際情況轉移就好}

初始狀態 = {我}

沿著自動機走一遍，最後停在哪個狀態就是答案。

如果不考慮亂倫的話，各種一夫多妻之類的制度只是增加一些狀態和轉移，應該是可做的。

如果非要考慮亂倫只好變成nfa了，最後確定化一下把所有可能的稱謂都算出來。可以考慮出個專版或者加個選項。

前幾天這個應用出來的時候，我也試著模仿了一下，本來想構造一棵樹的，後來大概寫了一下，發現可以不用這樣，感覺這樣的解決方案是可行的。

1. 先計算目標人物和我在家族中的輩分差

』我，哥哥，姐姐，弟弟，妹妹，丈夫，妻子『輩分 = 0

』爸爸，媽媽『輩分 = 1

』兒子，女兒『輩分 = -1

舉個栗子：』媽媽的爸爸的哥哥『然後計算輩分差 +1 + 1 + 0 = 2 ，說明目標人物比我大了兩輩。

2. 確定目標人物的性別

舉個栗子：」哥哥的兒子的女兒「然後，目標人物只跟xxxxx的**,性別只跟**相關，於是得到目標人物性別。

3. 確定目標人物在家族中處在什麼分支中。

大概只有，和爸爸一邊，和媽媽一邊，和丈夫一邊，和妻子一邊，和女兒一邊，和兒子一邊。

舉個栗子：」哥哥的哥哥的哥哥的爸爸的爸爸「 = 」哥哥的爸爸的爸爸「

這裡就有哥哥是不是自己的親哥了？下載應用後，發現它說是親哥的設定，最後我也接受了這樣的設定。

所以再 = 」爸爸的爸爸「

最後確定目標人物和爸爸一邊。

4. 根據，1 ， 2， 3 確定的三個參數好像就能確定了吧（ps : 我是這麼想的）

=========================================================

這個應用還是有些關係確定不出來的，前幾天下載的，大概的寫了一下，後來就卸載了。記得，這個應用不接受同性戀的設定，還有一些奇怪的設定什麼的，就得要自己去發現了。

不知道為啥腦子裡第一反應是Parser。。。明天我試試

=====================腦抽暫停的分割線====================

用正經的LL1搞不定啊……LR1似乎可以……

還是自動機好了= =

森林，當然森林也是樹了。不過難保關係複雜，還是用圖安全，說不定還存在有環圖（矣，我是不是想太多了）......

典型的圖論問題，幾個鄰接矩陣關係套一下很輕鬆。