分享一个亲属关系的算法

2017 年 11 月 20 日
 chaoxu

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

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

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

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

输出 爷爷的父亲的奶奶

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

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

4535 次点击
所在节点    分享创造
15 条回复
xiaozhizhu1997
2017 年 11 月 21 日
身在小家庭的感觉小家庭有小家庭的好...
Xs0ul
2017 年 11 月 21 日
这个半群的思路很风骚（

有几个小问题（没仔细看论文，要是问的比较蠢见谅）
1. 最后给出的复杂度是最差情况的还是平均意义下的？
2. 传统的算法，动态规划或者分治之类的，能否解这个问题？能的话复杂度怎么样，不能的话主要问题在哪儿？
chaoxu
2017 年 11 月 21 日
@Xs0ul
1. 最差.
2. 这个算法就是传统的算法啊. 里面求最短满足一个 context-free language 的 path 就是动规.
Libby520
2017 年 11 月 21 日
不如花一块硬币去坐小超市门口的摇摇：爸爸的爸爸叫爷爷，爸爸的妈妈叫奶奶......
forestyuan
2017 年 11 月 21 日
还少一个夫妻关系吧
nneedd
2017 年 11 月 22 日
@forestyuan 儿子的妈妈&儿子的爸爸
forestyuan
2017 年 11 月 22 日
@nneedd 没这么简单，从夫妻关系可以延伸出离婚再婚，继父继子等等
wzy44944
2017 年 11 月 24 日
有个很难的问题：表妹的舅舅叫什么？
mumuy
2017 年 11 月 24 日
哈哈哈，这个是我写的！！！文章还有程序： http://passer-by.com/relationship/
mumuy
2017 年 11 月 24 日
我的文章在这里： http://www.jianshu.com/p/74290f1ae838
mumuy
2017 年 11 月 24 日
@wzy44944 有很多种关系，看是什么表妹？姑表，舅表还是姨表，还有她外婆有几个儿子：
通过我的计算机可以算出以下都有可能：
叔叔、
伯父、
爸爸、
姻世伯、
舅舅、
mumuy
2017 年 11 月 24 日
大哥，我突然发现……我写的文章比你早半年，你还发表成了论文
chaoxu
2017 年 11 月 24 日
@mumuy 因为我们实际上解决的并不是同一个问题. 你可以看看整个文章.
edsheeran
2017 年 11 月 24 日
妹妹的妻子不能计算
laoyuan
2017 年 11 月 25 日
LS 亮了

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://study.congcong.us/t/408080

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX