t***e
发帖数: 291 | 1 灌水灌烦了，看看这篇文章吧：
http://www.cs.indiana.edu/mit.research.how.to/section3.13.html
Research is hard. It is easy to burn out on it. An embarrassingly small
fraction of students who start PhD programs in AI finish. AT MIT, almost all
those who do not finish drop out voluntarily. Some leave because they can make
more money in industry, or for personal reasons; the majority leave out of
frustration with their theses. This section tries to explain how that can
happen and to give some heuristics that may h |
|
p**k
发帖数: 241 | 2 哪位校友帮我下载一下这篇文章：
Worst Case Performance for Lot Sizing Heuristics,
By Sven Axsäter
European Journal of Operational Research, Vol. 9, No. 4, 1982, pp 339-343.
My email: p********[email protected]
多谢！ |
|
h*d
发帖数: 19309 | 3 发信人: strong (大拿~恭祝清华百年华诞), 信区: TsinghuaCent
标 题: 清华大学的2010
发信站: 水木社区 (Sun Apr 24 14:46:09 2011), 站内
清华大学的2010
注：本文由水木社区BBS世纪清华版（TsinghuaCent）整理，各项资料来自清华大学网
站、清华大学新闻网、北京协和医学院（清华大学医学部）网站和水木社区BBS世纪清
华版等。
正文：
本文系统总结2010年度清华大学、北京协和医学院（清华大学医学部）师生校友荣获的
各类学术和社会荣誉、学科竞赛成绩以及学校在教学科研领域中获得的各类成果和进展
。限于篇幅，在关于各类获奖成果的统计中，本文仅统计获得过一等奖、金奖（国家科
学技术奖除外）以上的成果（绩）。
*********************
一．最高荣誉
●清华大学数学科学中心主任丘成桐教授获得2010年沃尔夫（Wolf）奖，以表彰他在几
何分析领域的贡献，以及在几何和物理的多个领域都产生的“深刻而引人注目的影响”
。这是丘成桐继1982年获得菲尔茨奖后，再... 阅读全帖 |
|
p*****h
发帖数: 3 | 4 【 以下文字转载自 CS 讨论区 】
【 原文由 peterzh 所发表 】
I am reviewing a paper.
The paper said:
Given an autonomous system including edge routers and core routers.
Each edge router knows the network topology and link state by OSPF protocol.
Now for each egress edge router a sink tree needs to be found, where
each leaf is an ingress edge router and each link in the tree satisfies
some conditions, such as bandwidth and delay constraints.
It can be proved the problem is NP-complete.
Then in reality some heuristic a |
|
L*********y
发帖数: 347 | 5 再加个heuristic, 有点儿清晰了
★ 发自iPhone App: ChineseWeb 7.8 |
|
p*********g
发帖数: 9527 | 6 He is indeed an admirable inventor.
PAT. NO. Title
1 8,032,843 Full-Text User interface for providing consolidation
and access
2 D645,860 Full-Text Computing device
3 D645,037 Full-Text Handheld portable computing device
4 D644,218 Full-Text Electronic device with cover
5 D643,403 Full-Text Media player
6 D643,402 Full-Text Media device
7 8,000,736 Full-Text User programmable switch for portable data
p... 阅读全帖 |
|
x***u
发帖数: 336 | 7 oh, me too. :)
maybe my words earlier were a little strong. But indeed I think there are
misunderstandings between systems people and theory people. Both sides kind of
look down the other side. :( Some theory people work on artificial problems
and publish papers that stay in library forever. On the other hand, system
people just use simple heuristics without any rigorous analysis. This is not
surprising though, because firstly the theory are not powerful enough to
analyze everything, and nobody |
|
f*****r
发帖数: 229 | 8 I have some questions about scheduling for RAID storage devices, can anyone
give some comments/suggestions?
I want to explore good scheduling heuristics external to RAID controller(or
above soft RAID layer if it is a softraid system). Basically, I think that
there is no specific shceduler above RAID logic, for example, CSCAN/SSTF
should be done below RAID logic, since we have no enough knowledge about IO
request positions above RAID logic.
But I still wonder if there are any works about scheduli |
|
y***u
发帖数: 101 | 9 实际中的code一般都加上一些heuristics,应该更快,n^3 是worst-case |
|
h***n
发帖数: 276 | 10 What is the most efficient heuristic algorithm for such a well-known NPC problme
until now?
Any distributed solution for such a problem?
Thanks!
Also, how about one of the related problems - Maximum coverage problem?
I really appreciate any of your comments! |
|
S******o
发帖数: 111 | 11 I am not sure if there is any overview or survey on this topic as it's still
kinda new and not much work has been done. (I could be wrong as I haven't kept
track of this topic for a long time). As far as I know some research groups in
Umass(Brian Levine) and Gatech(Liu, Ling?) have some work on this topic. I
would say most recent works are pretty much heuristics based. Again, that's
just my impression and only for ur reference.
方
放在多个servers上 |
|
c******n
发帖数: 4965 | 12 papers fall into these areas
(1) assume an abstract model, describe it as
some theoretical problem, formalize it.
prove it's NPC.... give approximation alg, give
heuristics
show some simulations results
(2) small implementation project,
adding a particular component into the framework,
improve upon existing ones, such as resource discovery ....
(3) a particular application, for example, in medicine, in oceanography ....
(4) a lot of work on resource dis |
|
x*g
发帖数: 68 | 13 mobihoc的文章是最不'ad hoc'的了，与其他这个领域的文章比。大多数mobihoc文章都是
严格的理论方法(虽然可能毫无用处).很多其他ad hoc
network的会议，只要简单的heuristic，加上看的过去的模拟结果就能发。
that
given |
|
p*****h
发帖数: 3 | 14 I am reviewing a paper.
The paper said:
Given an autonomous system including edge routers and core routers.
Each edge router knows the network topology and link state by OSPF protocol.
Now for each egress edge router a sink tree needs to be found, where
each leaf is an ingress edge router and each link in the tree satisfies
some conditions, such as bandwidth and delay constraints.
It can be proved the problem is NP-complete.
Then in reality some heuristic algorithms can be used to find such a
tr |
|
f*****p
发帖数: 235 | 15 SA is basically a combination of random search and greedy search. At high
temperature it behaves more like random. When temperature is down, it is
closer to greedy. It's a good heuristic. But for global optimum there's no
guarantee. Also whether SA is effective depends on the solution space's
structure.
I don't use GA a lot. But I assume it shouldn't outperform SA much, as they
are often mentioned together. |
|
b*****d
发帖数: 62 | 16 【 以下文字转载自 EE 讨论区 】
发信人: bandaid (bandaid), 信区: EE
标 题: 请教一个概率问题
发信站: BBS 未名空间站 (Tue Jun 28 16:33:51 2005)
有这样一段代码：
if(A < B)
x = C;
else
x = D;
但是A和B并不是deterministic的数，而是
A = a0+a1*e1+a2*e2
B = b0+b1*e1+b3*e3,
e1, e2, e3都是random variable with mean=0 and variance=1.
C和D没什么限制。
说到底，就是如何比较两个pdf，然后根据结果执行不同的代码。
有没有什么好办法？heuristic也行。 |
|
k*****e
发帖数: 152 | 17 In SAT problem, when the number of negative literals is much less than the num
ber of all literals, does the problem become polynomial. Is there any SAT alg
. (not heuristic) exponential to the number of negative literals? Thanks! |
|
j*****h
发帖数: 62 | 18 假如我现在有n个bit string. (每个string由m个非0即1的bit组成)。任意两个
bit string之间的距离定义为他们xor以后结果的bit string中出现1的次数。
多个bit string可以通过bit or操作聚成一个bit string cluster.请问如何
设计一个算法，给定n个这样的bit string，以及给定k个cluster数目限制，
找到最优的聚类，使得所有的n个bit string到他们各自的聚类以后，对应的
bit string cluster的距离之和最小。
我想到用bottom up的用贪婪算法heuristic。初始的时候，每个bit string代表一个
cluster. 然后每一步迭代，找出距离最近的两个cluster，or成一个新的
cluster,这样cluster数目减少一个。迭代直到cluster 总数等于k结束。
可是数学上我不知道如何证明这个算法得到的是否是最优解，如果不是，这
个approximation离最优解有多大差距。 |
|
p********e
发帖数: 91 | 19 Recently I feel desparate about my research progress, overloaded by many
different methodologies and techniques. If I were to implement every theory
and experiment them, another year or two would go away...
How to find a promising research problem and stay focused on it?
How to build my own research framework?
How to selectively read theory references?
It is a search problem. I must find good heuristics. But how?
I am lost... I am in despair... I am searching totally in the darkness...
Who can g |
|
|
s****d
发帖数: 56 | 21 这个problem似乎不管怎么做都是heuristic的，没有一种方法能work for any dataset
吧。。。
有人用过minimum description length principle来决定cutoff threshold吧。。。 |
|
j**********s
发帖数: 132 | 22 你这个题目就是病态的，和维数相比较样本数目太少，大部分降维算法都不会
太有效。建议先用 domain knowledge/heuristics 把维数降低两个数量级再说,
或者把样本数量加大一百倍 |
|
D*******y
发帖数: 366 | 23 真是隔行如隔山啊。B 类在计算机已经算不好了吗？
好像计算机杂志分类比较细了。
正在做一个东西，一篇paper引用了ICML里面一个multi-agent reinforcement
learning的文章。
我想知道有没有 比较 reinforcement learning, genetic algorithm, particle
swarm optimization 算法在动态环境的文章。
是不是后两个算 evolotionary ，前一个算heuristic? |
|
n****y
发帖数: 106 | 24 最近碰到一个问题，关于dijkstra的，呵呵
dijkstra是用来解决最短路径的，graph上面只有一种weight,比如distance,找到一个
从source到destination的最短路径
现在有个问题就是，假设graph上每条edge都有两种weight,say distance and time,
现在要
用一种算法也是minimize 的distance, 但是subject to total time < T
也就是说，原来的dijkstra找出的路径可能不行了，因为总时间可能>T
我看了点文献，这个问题是NP-Hard, 有一些用heuristic来减少complexity的
谁能推荐个比较经典的算法，不需要性能最好，保证对的就可以了。刚看了一个“专利
”，研究到最后发现根本就是错的，sigh.
多谢。 |
|
D*******a
发帖数: 3688 | 25 Hansson, O., A. Mayer, and M. Yung, Criticizing solutions to relaxed models
yields powerful admissible
heuristics, Information Sciences, Vol 63, No 3, 1992 pp. 207-227
Please email to d*******[email protected]
Thanks!!! |
|
w**********s
发帖数: 291 | 26 这个问题比较有意思。我觉得现在大家不是说不想做深一点，是不知道该怎么弄。完全
没有谱，heuristic
都没有。
根本原因还是人对自身的认识不够。比如知识在人脑里面的存储，和现在的计算机信息
存储肯定不是一
回事。运算模式也是有根本的不同。CS的人是无力独自取得根本突破的。 |
|
d*****u
发帖数: 17243 | 27 我当然也没法指出谁谁谁在吵这个
但是前一阵看了Christiansen和Chater写的connectionist pscycholinguistics
2001年出版的
里面谈到了大量的争论
真正做研究的人一般不会过于争论这些heuristic的东西
因为没多大意义，也很难发表
但是你从每个人做的东西就能看出差别了
but |
|
j*****j
发帖数: 201 | 28 这是标准的subset sum problem. NP-complete的。
网上能找到些heuristic algorithm，上规模基本不可能很快算出来的 |
|
d******e
发帖数: 7844 | 29 个人觉得，人脸里的PCA已经和统计本身没啥关系了，就剩下一个heuristic的方法了。
反而从几何角度来解释就足够了。
统计里认为如果p>>n的话，PCA找到的eigenvector根本没有统计意义... ...
但从实际性能来看，PCA的表现并不差。 |
|
i*i
发帖数: 918 | 30 我的HTPC就是i3-3220, shuttle xh61v, 120G SSD, 8G RAM, Win 7, 挂两个USB3 3T硬
盘，用windows share。不过windows 7的网络管理很坑人，需要用Fixed IP，disable
heuristics，autotuning （network interface)，和 Large Send Offload v2 （
network card)，否则我千兆的网只能有100k/s，air video断断续续的。
然后用30min sleep power management，wake-on-lan on patten，机器平时休眠，
network share (需要用IP地址)的时候自动启动（几秒的事），超级省电。（好像NAS
无法休眠，server和硬盘是一直开着的？）
不过除了file server，PPS, video play, air video server 等，这个server还能派
什么用场呢？有心搞个dynamic DNS，用它当http和ftp server，但家里cable 的上行
速度一般，从外... 阅读全帖 |
|
i*i
发帖数: 918 | 31 这个话就比较长了。以前架过一个http server，但从外面下载个mp3都需要几分钟，没
什么用处。不过我当时网络的上行速度只有几百k，现在下行30Mbps，上行3.7Mbps，可
能还可以忍受。
关于那个win 7 网络，据说是加了一些高级功能，真正害人啊。我原来用一个非常老的
机器，windows XP, USB2，windows share的速度一般是20 - 30MBps。升级了后，赫然
100-200KBps，task manager->network utilization 只有0.2%，怎么查也没发现有什
么问题。google 了一下 windows 7 network share slowness，发现是一个老问题，谁
也不知具体是什么回事。各种解决方案有十几种，没一个好用。最后从一个地方发现有
人说要用static IP address，改了之后立马network utilization 高于80%，速度到了
100 - 120MBps。之前根据他人推荐还设置了(cmd.exe下)
netsh interface tcp set global heuristics=... 阅读全帖 |
|
y****e
发帖数: 1012 | 32 在一个机器上写一个jar，用eclipse配置了native library~但是在另外一个机器上却跑
不了……
/usr/lib/jvm/jdk1.7.0/bin/java -Djava.library.path=./lib -Dfile.encoding=UT
F-8 -classpath ./target/classes:./lib/gdata-core-1.0.jar:./lib/gdata-client-
1.0.jar:./lib/gdata-maps-2.0.jar:./lib/gdata-media-1.0.jar:./lib/lpsolve55j.
jar:./target/DCPlacement-jar-with-dependencies.jar:/usr/share/java/log4j-1.2
.jar DatacenterLocator -g 10,10 -l 4000 -s heuristic
报错：
Exception in thread "Thread-3" Exception in thread "Thread-0" Exception in t
h... 阅读全帖 |
|
N********n
发帖数: 8363 | 33 Sounds like a register allocation or graph coloring problem in compiler
design. It's one hard problem. There are a few heuristics for it. |
|
p***o
发帖数: 1252 | 34 It's a problem of reachability. Either you show it's reachable or
prove it's not. For the simple case of 9 boxes, there are only 9!
vertices in the graph so brute-force search will work. Otherwise
you need some heuristics like a* search. |
|
c*****t
发帖数: 1879 | 35 Bin packing is NPC. You were either looking at a more constrainted
problem, an approximation algorithm, or a heuristic one. |
|
n*******r
发帖数: 444 | 36 来自主题: Programming版 - 算法求教 Thanks for proving this is a NPC, I will apply heuristic then. |
|
n****y
发帖数: 106 | 37 最近碰到一个问题，关于dijkstra的，呵呵
dijkstra是用来解决最短路径的，graph上面只有一种weight,比如distance,找到一个
从source到destination的最短路径
现在有个问题就是，假设graph上每条edge都有两种weight,say distance and time,
现在要
用一种算法也是minimize 的distance, 但是subject to total time < T
也就是说，原来的dijkstra找出的路径可能不行了，因为总时间可能>T
我看了点文献，这个问题是NP-Hard, 有一些用heuristic来减少complexity的
谁能推荐个比较经典的算法，不需要性能最好，保证对的就可以了。刚看了一个“专利
”，研究到最后发现根本就是错的，sigh.
多谢。 |
|
S**I
发帖数: 15689 | 38 一个heuristic的算法是用distance做为weight计算K shortest paths，然后从中寻找符
合total time < T的路径，或着是反过来用time做为weight计算K shortest paths，然
后选取distance最小的那条。 |
|
w***g
发帖数: 5958 | 39 我们用nutch，很烂。主要是一旦crawl的范围放大到整个internet，大部分时间就都花
在了处理各种垃圾页面上。一个好的crawler最关键的是各种ad hoc的heuristic rules
避免抓取无用页面。据我所知没有一个open source的软件有比较好的这种rules。虽然
不少软件允许用户自己plugin，但是对于没有什么经验的人来说找到这些rules比imple
ment一个crawler还要难。 |
|
|
|
k****5
发帖数: 546 | 42 use dynamic scheduling(or similar heuristic) instead of static one |
|
c****e
发帖数: 1453 | 43 define optimal estimation first. You need a fitness function to search for
global/local optimal. If you have little knowledge of the structure, try
genetic algorithm. If you understand the problem very well, try to use tree-
based search, explore your own heuristics of variable order and higher/lower
bound optimization. |
|
d***a
发帖数: 13752 | 44 如果是一票一座，最优解恐怕是NP-hard的问题了。
可以做一些heuristic的优化，比如说选空闲区段最少的座位。不过，这样的话，用
bitmap方式的效率就会降下来不少，因为那个没法用bitmap来做。 |
|
w***g
发帖数: 5958 | 45 我考了下古。其实正确的方法上面pker已经提到了。
要在N个串里面找nearest neighbor，要找M次，问题是相似性测度计算太慢。
要是我首先会试下面的方法：
1. python并行化上多核。假设有8 core，速度直接提高8倍。
2. 我会先在前N/L个串中找nearest neighbor，L需要调，预设为100吧。
开销为整个问题的1/L。算完后对nearest neighbor的距离就有个下界了。
然后剩下所有的串先用quick_ratio/really_quick_ratio算上届，超不过
那个下界的直接扔掉，超过了再用ratio算。
3. 要还是慢，有多台机器就上多台机器吧。不需要mapreduce。
苦主那个相似性测度是一个近似edit distance的heuristic，本身就做不得准。
上面也说了苹果橘子的问题。python那段代码实现其来应该很罗嗦，想用
别的语言写一遍并不容易。用java实现同样的算法复杂度上不会更优，光靠
语言可以提高至少10倍速度吧。对N个串用倒排表建索引确实是个优化，但是
程序写起来就更罗嗦，我觉得不值得做。
可惜的是楼主的问题规模... 阅读全帖 |
|
N********n
发帖数: 8363 | 46
不深入了解优化的对编译原理只是知道点皮毛而已。只有做到优化才会涉及到图论
上一些复杂算法、HEURISTIC等。 |
|
