钢笔论坛

标题: 数学工程理科好的进~~有个小问题 [打印本页]
作者: Edinburgh    时间: 2011-1-14 19:54
标题: 数学工程理科好的进~~有个小问题
最近在想着一个问题，如果知道了身边人与人之间的关系信息，我怎么才能把相关人员聚合在一起？？？
也就是说，如果我已经知道了一组元素 以及对应的这些元素的关系，那我怎么才能把凡是有关连到的元素聚合在一起呢？

比如，若 a 喜欢 b  那么a和b就产生了联系，我标记成<a,b> ，同时 b 和 c 是好朋友  那么同理有<b,c> 的关系存在，于是间接的，a和c 也就会有一定的联系，于是便产生了<a,c>.  这叫“传递闭包”。

在比如

我喜欢用pelikan写字: <我，pelikan>.
pelikan讨厌万宝龙公司: <pelikan, 万宝龙>
于是就会有潜在的我跟万宝龙的关系<我，万宝龙>


那我现在的目的是 如果我知道两两元素的关系， 我怎么才能把这些集合最终聚集起来呢？
我爱你， 你爱他， 最后的结果是产生一个{我，你，他}。


我回忆了一下以前学过的传递闭包的概念比如

有 A这么个7个元素集合， 然后里面两两元素的关系写在R里面
A={a,b,c,d,e,f,g,h} ;R={<a,b>,<b,c>,<d,g>,<e,g>} ;

我现在能够利用传递闭包的数学计算得到：
t(R)={<a,b>,<a,c>,<b,c>,<d,g>,<e,g>}      

那我怎么才能进一步得到我想要的下面这几个集合呢？

{a，b，c} {d,e,g} {f}
作者: rubanth    时间: 2011-1-14 20:49
很h很暴力
作者: aqua2001    时间: 2011-1-14 20:55
本帖最后由 aqua2001 于 2011-1-14 21:12 编辑

从数学上说，首先你的“关系”必须给出明确的定义，而且这个关系至少要有传递性。事实上常用的是等价关系，这样能够很容易地把全集分成等价类。但我没完全听懂你的意思，你是想要算法呢还是什么别的？要是算法的话，最直观的方法是把关系用图表示出来以后，搜索（强）连通分支。
作者: Edinburgh    时间: 2011-1-14 22:45
从数学上说，首先你的“关系”必须给出明确的定义，而且这个关系至少要有传递性。事实上常用的是等价关系， ...
aqua2001 发表于 14/1/2011 12:55



    从A, R 到 t(R)={<a,b>,<a,c>,<b,c>,<d,g>,<e,g>} 我可以用现成的算法（比如wallshell）得到。
那从t(R)到 {a，b，c} {d,e,g} {f} 有没有什么方法可以快速得到？
因为t(R)里面现在只有5个二元关系对儿， 所以眼睛一看就可以写出来那3个集合了。如果t(R)里面存在海量比如1000万个关系对儿的话，那就得有个方法呀。
作者: nil    时间: 2011-1-14 22:46
program relation;
const
n=20;
var
rc:packed array[1..n]of integer;
k,m:integer;

procedure init;
var
  i:integer;
  st:string;
begin
  readln(st);
  assign(input,st);reset(input);
  readln(k,m);
  for i:=1 to k do rc[i]:=i;
end;

procedure main;
var
  i,j,p1,p2,t:integer;
begin
  for i:=1 to m do
   begin
    read(p1,p2);
    t:=rc[p2];
    for j:=1 to k do
      if rc[j]=t then rc[j]:=rc[p1];
   end;
end;

procedure print;
var
  i,t,a,b:integer;
begin
  read(t);
  for i:=1 to t do
   begin
    read(a,b);
    if rc[a]=rc[b] then writeln('YES') else writeln('NO');
   end;
  close(input);
end;

begin
init;
main;
print;
end.
作者: nil    时间: 2011-1-14 22:46
program relation;
const
n=20;
var
rc:packed array[1..n]of integer;
k,m:integer;

procedure init;
var
  i:integer;
  st:string;
begin
  readln(st);
  assign(input,st);reset(input);
  readln(k,m);
  for i:=1 to k do rc[i]:=i;
end;

procedure main;
var
  i,j,p1,p2,t:integer;
begin
  for i:=1 to m do
   begin
    read(p1,p2);
    t:=rc[p2];
    for j:=1 to k do
      if rc[j]=t then rc[j]:=rc[p1];
   end;
end;

procedure print;
var
  i,t,a,b:integer;
begin
  read(t);
  for i:=1 to t do
   begin
    read(a,b);
    if rc[a]=rc[b] then writeln('YES') else writeln('NO');
   end;
  close(input);
end;

begin
init;
main;
print;
end.
作者: nil    时间: 2011-1-14 22:47
中学时代写的Pascal小程序，解这个问题的。献丑
作者: zenima123    时间: 2011-1-15 00:11
这玩意是不是离散数学？
作者: Edinburgh    时间: 2011-1-15 01:08
这玩意是不是离散数学？
zenima123 发表于 14/1/2011 16:11


那个闭包传递是离散数学里的。。。
    今天突然幻想了一个现实中的问题，然后就想来想去，想到了貌似以前学习过的离散数学它可以帮上这个忙。。。
作者: lacsylle    时间: 2011-1-15 04:15
[attach]287809[/attach]

连线代表关系，节点上的所有元素构成了一个集合，还有许多其他这样的“树”，每一棵树都代表了一个符合lz要求的集合。
作者: anderson997    时间: 2011-1-15 09:31
本体？语义网？
作者: Edinburgh    时间: 2011-1-16 06:18
研究了一晚上终于搞定了。嘻嘻~~
[attach]288147[/attach]
作者: 笔谈    时间: 2011-1-19 15:26
看到这种很头痛。。。
作者: gutiwen    时间: 2011-2-5 08:14
喜欢数学，喜欢与喜欢数学的人打交道。
上面这些对我来说是“天书”。
作者: linrenzhi911    时间: 2011-2-8 06:07
树的集合的传递性
作者: 大大小小    时间: 2011-2-10 00:00
看着就头大
作者: 夕阳草0104    时间: 2011-2-10 00:28
数学白痴路过，啥是离散数学？



欢迎光临 钢笔论坛 (http://penbbs.com/) Powered by Discuz! X3.2