分享一个亲属关系的算法

[chaoxu]

这个算法解决的问题在这里写过.

亲属关系问题的大概概念是 输入: 给一个目标亲属关系 x. 以及可以使用的术语集合 S 以及它们对应的亲属关系. 输出: 用最少个数的术语描述 x. (这称之为最短的描述)

我们有 4 个可以用的生成元. f,m,s,d. 各自代表父, 母, 儿, 女.

输入 目标关系: ffffm 可用术语: {父亲 =f, 爷爷= ff, 奶奶 = fm, 母亲=m}

输出 爷爷的父亲的奶奶

Qian Zhang和我给出了个算法. 这是算法

当然, 现在还缺一个程序员实现这个算法.

[xiaozhizhu1997]

身在小家庭的感觉小家庭有小家庭的好...

[Xs0ul]

这个半群的思路很风骚（

有几个小问题（没仔细看论文，要是问的比较蠢见谅）
1. 最后给出的复杂度是最差情况的还是平均意义下的？
2. 传统的算法，动态规划或者分治之类的，能否解这个问题？能的话复杂度怎么样，不能的话主要问题在哪儿？

[chaoxu]

@Xs0ul
1. 最差.
2. 这个算法就是传统的算法啊. 里面求最短满足一个 context-free language 的 path 就是动规.

[Libby520]

不如花一块硬币去坐小超市门口的摇摇：爸爸的爸爸叫爷爷，爸爸的妈妈叫奶奶......

[forestyuan]

还少一个夫妻关系吧

[nneedd]

@forestyuan 儿子的妈妈&儿子的爸爸

[forestyuan]

@nneedd 没这么简单，从夫妻关系可以延伸出离婚再婚，继父继子等等

[wzy44944]

有个很难的问题：表妹的舅舅叫什么？

[mumuy]

哈哈哈，这个是我写的！！！文章还有程序： http://passer-by.com/relationship/

[mumuy]

我的文章在这里： http://www.jianshu.com/p/74290f1ae838

[mumuy]

@wzy44944 有很多种关系，看是什么表妹？姑表，舅表还是姨表，还有她外婆有几个儿子：
通过我的计算机可以算出以下都有可能：
叔叔、
伯父、
爸爸、
姻世伯、
舅舅、

[mumuy]

大哥，我突然发现……我写的文章比你早半年，你还发表成了论文

[chaoxu]

@mumuy 因为我们实际上解决的并不是同一个问题. 你可以看看整个文章.

[edsheeran]

妹妹的妻子不能计算

[laoyuan]

LS 亮了