这个算法解决的问题在这里写过.
亲属关系问题的大概概念是 输入: 给一个目标亲属关系 x. 以及可以使用的术语集合 S 以及它们对应的亲属关系. 输出: 用最少个数的术语描述 x. (这称之为最短的描述)
我们有 4 个可以用的生成元. f,m,s,d. 各自代表父, 母, 儿, 女.
输入 目标关系: ffffm 可用术语: {父亲 =f, 爷爷= ff, 奶奶 = fm, 母亲=m}
输出 爷爷的父亲的奶奶
Qian Zhang和我给出了个算法. 这是算法
当然, 现在还缺一个程序员实现这个算法.
 |
1
xiaozhizhu1997 Nov 21, 2017
身在小家庭的感觉小家庭有小家庭的好...
|
 |
2
Xs0ul Nov 21, 2017
这个半群的思路很风骚（
有几个小问题（没仔细看论文，要是问的比较蠢见谅） 1. 最后给出的复杂度是最差情况的还是平均意义下的？ 2. 传统的算法，动态规划或者分治之类的，能否解这个问题？能的话复杂度怎么样，不能的话主要问题在哪儿？ |
 |
3
chaoxu OP  1
|
 |
4
Libby520 Nov 21, 2017 3
不如花一块硬币去坐小超市门口的摇摇：爸爸的爸爸叫爷爷，爸爸的妈妈叫奶奶......
|
 |
5
forestyuan Nov 21, 2017
还少一个夫妻关系吧
|
 |
6
nneedd Nov 22, 2017 1
@forestyuan 儿子的妈妈&儿子的爸爸
|
|
7
forestyuan Nov 22, 2017
@nneedd 没这么简单，从夫妻关系可以延伸出离婚再婚，继父继子等等
|
 |
8
wzy44944 Nov 24, 2017
有个很难的问题：表妹的舅舅叫什么？
|
 |
9
mumuy Nov 24, 2017
哈哈哈，这个是我写的！！！文章还有程序： http://passer-by.com/relationship/
|
|
10
mumuy Nov 24, 2017
|
|
11
mumuy Nov 24, 2017
|
|
12
mumuy Nov 24, 2017
大哥，我突然发现……我写的文章比你早半年，你还发表成了论文
|
 |
14
edsheeran Nov 24, 2017
妹妹的妻子不能计算
|
 |
15
laoyuan Nov 25, 2017
LS 亮了
|
Select Language