avatar
打听ucsd一位pi# Biology - 生物学
x*p
1
平面上有随机2000个点,其中1000蓝点,1000红点。但任何三点都不同线。
要求寻找一种最优化的算法,生成1000条互不相交的连接蓝点和红点的线段。换句话说
,让任何蓝点去连接任何红点,但各不相交。
avatar
d*g
2
上午去preschool,下午睡2小时,然后醒来就不知道干点什么了。
现在颜色都认识,数字,字母大小写也都认识了,汉字能认识将近100个吧。不知道该
教她点什么了,挺喜欢唱歌的,有时候我就放flash给她看,不过看时间长乐,她自己
就知道眼睛疼,对电视不是很有瘾。一直我们也没给她看动画片,前一阵看天线宝宝后
来也想不起来了。挺喜欢让我跟她认字的,可认一遍也才10几分钟而已。
大半天的时间都不知道干点什么,现在这么大玩什么玩具啊,我家玩具都是小时候的了
,她已经不感兴趣了,无非就是认颜色字母之类的益智的。
请有经验的妈妈给点建议
avatar
m*7
3
替国内同学打听的,他想去dennis carson 实验室做访问学者。
请问老板人品,实验室课题情况。有了解的请告知我呗。十分感谢!
avatar
g*s
4
一定存在解吗?

【在 x*****p 的大作中提到】
: 平面上有随机2000个点,其中1000蓝点,1000红点。但任何三点都不同线。
: 要求寻找一种最优化的算法,生成1000条互不相交的连接蓝点和红点的线段。换句话说
: ,让任何蓝点去连接任何红点,但各不相交。

avatar
r*f
5
不算很益智的很多,比如play doh, 画画,coloring,doll house, play kitchen,
string beads等

【在 d**********g 的大作中提到】
: 上午去preschool,下午睡2小时,然后醒来就不知道干点什么了。
: 现在颜色都认识,数字,字母大小写也都认识了,汉字能认识将近100个吧。不知道该
: 教她点什么了,挺喜欢唱歌的,有时候我就放flash给她看,不过看时间长乐,她自己
: 就知道眼睛疼,对电视不是很有瘾。一直我们也没给她看动画片,前一阵看天线宝宝后
: 来也想不起来了。挺喜欢让我跟她认字的,可认一遍也才10几分钟而已。
: 大半天的时间都不知道干点什么,现在这么大玩什么玩具啊,我家玩具都是小时候的了
: ,她已经不感兴趣了,无非就是认颜色字母之类的益智的。
: 请有经验的妈妈给点建议

avatar
B*i
6
UCSD病理系就没有一个是好东西
avatar
x*p
7
是的,以前有一个回帖,提出一种算法,是肯定能找到解的,只是复杂度太高了。
avatar
l*k
8
羡慕呀,我女儿三岁整,字母不识几个,汉字一个也不认识。 就喜欢玩lego duplo,
puzzle, pretend play. 玩puzzle, lego, 能玩好几个小时。 看来该教她点东西了。

【在 d**********g 的大作中提到】
: 上午去preschool,下午睡2小时,然后醒来就不知道干点什么了。
: 现在颜色都认识,数字,字母大小写也都认识了,汉字能认识将近100个吧。不知道该
: 教她点什么了,挺喜欢唱歌的,有时候我就放flash给她看,不过看时间长乐,她自己
: 就知道眼睛疼,对电视不是很有瘾。一直我们也没给她看动画片,前一阵看天线宝宝后
: 来也想不起来了。挺喜欢让我跟她认字的,可认一遍也才10几分钟而已。
: 大半天的时间都不知道干点什么,现在这么大玩什么玩具啊,我家玩具都是小时候的了
: ,她已经不感兴趣了,无非就是认颜色字母之类的益智的。
: 请有经验的妈妈给点建议

avatar
f*4
9
那个vehicle pickup/deliver解法是什么样的?
二分图最大匹配好像跟这个没关系啊

【在 x*****p 的大作中提到】
: 是的,以前有一个回帖,提出一种算法,是肯定能找到解的,只是复杂度太高了。
avatar
r*f
10
这是各有所强啊,都很棒

了。

【在 l********k 的大作中提到】
: 羡慕呀,我女儿三岁整,字母不识几个,汉字一个也不认识。 就喜欢玩lego duplo,
: puzzle, pretend play. 玩puzzle, lego, 能玩好几个小时。 看来该教她点东西了。

avatar
g*s
11
我觉得这个不是简单的图论问题,而是计算几何的问题。这个两两不交的限制很强。

【在 f*******4 的大作中提到】
: 那个vehicle pickup/deliver解法是什么样的?
: 二分图最大匹配好像跟这个没关系啊

avatar
R*i
12
pretend play,让她带着你玩。
avatar
x*p
13
需要用到三点不共线这个非常强的条件。
avatar
k*b
14
作手工,画画,教唱歌,跳舞,带出去玩 (playground, 图书馆等). 约playdate或上
part time daycare 让孩子跟别的孩子玩。
avatar
g*s
15
三角化?

【在 x*****p 的大作中提到】
: 需要用到三点不共线这个非常强的条件。
avatar
d*g
16
每天下午4点有个5岁的女孩来玩,也是跟大孩子学了很多,我家娃注意力不够集中,在
幼儿园好一些了,我准备让她画画,可她一拿笔就是乱花,气的我不知道怎么教,汉字
什么就是她突然开窍,我们国内带的挂图,打出生就贴墙上了,我给她讲看图识字的书
她就自己跑去墙上找对应的字,慢慢就认识的多了。字母数字估计学校学的我在家陪她
玩字母拼图巩固了一下

【在 k******b 的大作中提到】
: 作手工,画画,教唱歌,跳舞,带出去玩 (playground, 图书馆等). 约playdate或上
: part time daycare 让孩子跟别的孩子玩。

avatar
x*p
17
缘起: 我有一个当教授的朋友,他偶然向我提到这个题目,说是和另一个美国教授聊天
的时候那个教授提出的,他也没解法。但数学上证明解的存在性是很容易的。因为我是
研究算法的,所以我这个朋友就来问我。我想了十几分钟也没思路就放弃了。一周后,
我的朋友打电话问我想的怎么样了,我本来是很羞愧的说不知道的,谁知当时灵光一闪
,想到一个复杂度为O(n^2)的算法可以解决这个问题。后来把算法整理写给我的朋友。
现在回想,恐怕有更好的O(nlnn)的算法,但不确定。这个版大牛多,上来问问,5个包
子答谢。
avatar
d*g
18
北部冬天基本不出门,我自己没有手工的天赋,娃在学校还是做一些的,还有画画

【在 k******b 的大作中提到】
: 作手工,画画,教唱歌,跳舞,带出去玩 (playground, 图书馆等). 约playdate或上
: part time daycare 让孩子跟别的孩子玩。

avatar
g*s
19
抛砖引玉一下:
解法一:
这题可以看作是二分图的最大匹配的最小值路径匹配问题。用KM算法可以知道O(N*M)=O
(N^3).
解法二:
分治法。找到两点,把所有点分成两部分,每个部分都用相同多的红点和蓝点。然后对
两部分分治。
如何找到这样的两点(先给一个nlgn的算法)
1. 找x值最小的一个点A(如果有多个x值相同,取y值最小),把它作为其中一点。
2. 把A作为原点。其它所有点对于A(都减去Ax,Ay),都相当会落入第一和第四象限。
3. 把所有点求tan,排序。
4. 从小到大进行count,一直到找到这么一条边(A->B)。(易知一定存在这么一条边)
f(n) = max{ f(k) + f(n-k) + nlgn } k=1..n-1
f(n) = O(nlgn * n) = O(n^2 * lgn)
改进找B点的算法
3. 建立一最大堆,和一最小堆
4. 轮流从最大堆最小堆来进行查找,直到找到B
f(n) = max { f(k) + f(n-k) + (n + k*lgn)} k = 1..n/2
f(n) = O(n^2)
O(nlgn)感觉很难。
avatar
t*z
20
这些早晚都会的。不要急

了。

【在 l********k 的大作中提到】
: 羡慕呀,我女儿三岁整,字母不识几个,汉字一个也不认识。 就喜欢玩lego duplo,
: puzzle, pretend play. 玩puzzle, lego, 能玩好几个小时。 看来该教她点东西了。

avatar
x*p
21
这个解法二是当时我的思路,只是上面第三步的排序,其实只需要一次排序即可,因为
以后递归的话,这个序是不会变的。
avatar
c*k
22
我娃喜欢cutting, pasting, coloring, playdoh, puzzle, kitchen, 开tea party,
doll house, blocks, 骑自行车, scooter, 听音乐, 唱歌, 跳舞,捉迷藏, 听故事. 每
天家里就看她忙忙碌碌的, 指挥我们团团转. 我们不教字母数字啥的, 反正幼儿园老师
会教, 从来不给看电视.
avatar
O*N
23
能解释一下为什么第四步一定能找到满足条件的B点?
如何保证分成的两部分中,红点和兰点的数量一定相等?

=O

【在 g***s 的大作中提到】
: 抛砖引玉一下:
: 解法一:
: 这题可以看作是二分图的最大匹配的最小值路径匹配问题。用KM算法可以知道O(N*M)=O
: (N^3).
: 解法二:
: 分治法。找到两点,把所有点分成两部分,每个部分都用相同多的红点和蓝点。然后对
: 两部分分治。
: 如何找到这样的两点(先给一个nlgn的算法)
: 1. 找x值最小的一个点A(如果有多个x值相同,取y值最小),把它作为其中一点。
: 2. 把A作为原点。其它所有点对于A(都减去Ax,Ay),都相当会落入第一和第四象限。

avatar
h*u
24
千万别教,你女儿现在做的这些是最好的了。千万别把人家王歧途上引

了。

【在 l********k 的大作中提到】
: 羡慕呀,我女儿三岁整,字母不识几个,汉字一个也不认识。 就喜欢玩lego duplo,
: puzzle, pretend play. 玩puzzle, lego, 能玩好几个小时。 看来该教她点东西了。

avatar
g*s
25
assume the A is blue, it scan from bottom to up for all the rest N-1
point.
count=1
+1 for blue point
-1 for red point.
So, there are 499 times +1 and 500 times -1. count will reach 0 at some
point.
The point that makes count = 0 is the B. the worse case is the B is the
last one. then all N-2 points are in the one side and 0 point in the other
side.


【在 O*N 的大作中提到】
: 能解释一下为什么第四步一定能找到满足条件的B点?
: 如何保证分成的两部分中,红点和兰点的数量一定相等?
:
: =O

avatar
j*a
26
这个年纪最喜欢的是protend play:做医生给你打针,做老师,做厨师,做公主,做
monster。。。
怎么可能没得玩呢?

【在 d**********g 的大作中提到】
: 上午去preschool,下午睡2小时,然后醒来就不知道干点什么了。
: 现在颜色都认识,数字,字母大小写也都认识了,汉字能认识将近100个吧。不知道该
: 教她点什么了,挺喜欢唱歌的,有时候我就放flash给她看,不过看时间长乐,她自己
: 就知道眼睛疼,对电视不是很有瘾。一直我们也没给她看动画片,前一阵看天线宝宝后
: 来也想不起来了。挺喜欢让我跟她认字的,可认一遍也才10几分钟而已。
: 大半天的时间都不知道干点什么,现在这么大玩什么玩具啊,我家玩具都是小时候的了
: ,她已经不感兴趣了,无非就是认颜色字母之类的益智的。
: 请有经验的妈妈给点建议

avatar
g*s
27
因为他们是相对与A的tan值。当递归(分治)的时候,是一个新的A。他们的tan的序还
是回变的。

【在 x*****p 的大作中提到】
: 这个解法二是当时我的思路,只是上面第三步的排序,其实只需要一次排序即可,因为
: 以后递归的话,这个序是不会变的。

avatar
m*c
28
挺牛的了。羡慕

【在 d**********g 的大作中提到】
: 上午去preschool,下午睡2小时,然后醒来就不知道干点什么了。
: 现在颜色都认识,数字,字母大小写也都认识了,汉字能认识将近100个吧。不知道该
: 教她点什么了,挺喜欢唱歌的,有时候我就放flash给她看,不过看时间长乐,她自己
: 就知道眼睛疼,对电视不是很有瘾。一直我们也没给她看动画片,前一阵看天线宝宝后
: 来也想不起来了。挺喜欢让我跟她认字的,可认一遍也才10几分钟而已。
: 大半天的时间都不知道干点什么,现在这么大玩什么玩具啊,我家玩具都是小时候的了
: ,她已经不感兴趣了,无非就是认颜色字母之类的益智的。
: 请有经验的妈妈给点建议

avatar
x*p
29
是的。但要注意的是,我们永远选择最左边的点作为新的原点。这样,所有点相当于一
个平移操作,虽然角度发生了变化,但序是不变的。这个可以做出数学证明。

【在 g***s 的大作中提到】
: 因为他们是相对与A的tan值。当递归(分治)的时候,是一个新的A。他们的tan的序还
: 是回变的。

avatar
d*g
30
原来protend play是这个意思,就是过去小时候玩的过家家之类的。
她偶尔也玩,可能我没有积极引导。
跟大家学习了很多,多谢大家的建议

【在 j*******a 的大作中提到】
: 这个年纪最喜欢的是protend play:做医生给你打针,做老师,做厨师,做公主,做
: monster。。。
: 怎么可能没得玩呢?

avatar
g*s
31
给个反例。

【在 x*****p 的大作中提到】
: 是的。但要注意的是,我们永远选择最左边的点作为新的原点。这样,所有点相当于一
: 个平移操作,虽然角度发生了变化,但序是不变的。这个可以做出数学证明。

avatar
w*t
32
我要是有个3岁女儿,就买那个厨房给她了,还有一堆配套小部件了
avatar
x*p
33
Good example.
Then the algorithm can not be improved to O(nlnn)
avatar
y*4
34
偶们家阿宝最喜欢剪纸,图颜色啊,画画啊,过家家啊
咱都没时间教她正经东西。
avatar
s*2
35
上午去preschool,下午睡2小时, 4点小姐姐来家里和孩子玩。。再除去洗澡吃饭。。
。时间安排已经挺紧凑了。。

【在 d**********g 的大作中提到】
: 上午去preschool,下午睡2小时,然后醒来就不知道干点什么了。
: 现在颜色都认识,数字,字母大小写也都认识了,汉字能认识将近100个吧。不知道该
: 教她点什么了,挺喜欢唱歌的,有时候我就放flash给她看,不过看时间长乐,她自己
: 就知道眼睛疼,对电视不是很有瘾。一直我们也没给她看动画片,前一阵看天线宝宝后
: 来也想不起来了。挺喜欢让我跟她认字的,可认一遍也才10几分钟而已。
: 大半天的时间都不知道干点什么,现在这么大玩什么玩具啊,我家玩具都是小时候的了
: ,她已经不感兴趣了,无非就是认颜色字母之类的益智的。
: 请有经验的妈妈给点建议

avatar
s*2
36
男孩也可以玩啊 :-)

【在 w********t 的大作中提到】
: 我要是有个3岁女儿,就买那个厨房给她了,还有一堆配套小部件了
avatar
b*d
37
妈妈工作自由吗?自由的话可以报个舞蹈班,游泳班什么的,三岁可以开始上了,杀时
间杀精力很好啊,回来吃晚饭胃口好。
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。