f**k
发帖数: 15238 | 1 you assume too much
The heuristic function, if they are using it at all, cannot be that
simplistic,
the algorithm should be far more complicated than what you provided in your
last post. |
|
t*s
发帖数: 1504 | 2 my research is on AI...though, to be frank, ai is a broad field, and i don't
know much about computer game play.
care to educate me how could computer game players not use heuristic
functions when the game size is large? (of course, you could design a game
player that only makes dumb moves. but that is tai gang) |
|
x*****7
发帖数: 7326 | 3 电脑下棋也是通过heuristic pruning来简化算法的。
所以我看好未来电脑替我们做重要决定。 |
|
C****g
发帖数: 2220 | 4 弱智啊
他02年就发帖招博士，至少做了10年博导
这什么鸟水平?
还搞什么鸟遗传算法
搞这中所谓meta-heuristic的
基本和伪科学没区别了
土鳖就是土鳖啊 |
|
k*****r
发帖数: 21039 | 5 元首时代的德国，就有个批评犹犹把科学庸俗化，heuristic化的恶劣倾向。 |
|
g*****y
发帖数: 438 | 6 有的可以部分破解， 比如王老师的MD5 破解方法， 但不是任何情况都和可以
其实最终的方式还是穷举，或者借助 heuristic 的穷举 |
|
w********r
发帖数: 14958 | 7 又扯淡了。
人脑根本没有解决围棋的问题。 靠经验不叫完美。 要是完美了，人脑和人脑比永远
平局，就用不着比赛了。
人的经验充其量叫heuristics,算是人工智能的一种， 但只是非常低级的阶段。 |
|
w********r
发帖数: 14958 | 8 pattern match是一个办法，但是使用是有前提的。 都没有一个整体的模型，你咋知
道match的前提满不满足？你这么做有没有意义？
没有充分理由支持的decision，还是heuristics. 我上面所说了，是非常低级的一种智
能。 |
|
w********r
发帖数: 14958 | 9 跟你说了多少次了。算法不等于暴力穷举。
最简单的Ｐ问题， 让你去给一串数字排序你怎么排？
最好的算法复杂度 是O(n)至O(nlogn)之间。是暴力穷举吗？ 靠你人脑算，你能比
电脑方法好吗？
人脑这个叫Heuristics,没有任何保证能赢。 只不过是经验基础上一定的演绎。 很
多种棋局，任何人都没有见过。 人只能靠猜加蒙。这时人脑的能力等于零。
之所以围棋大师，实际上是因为他见过类似的。或者所有会下棋的只会下那几种套路。
最早都是那几个师傅教出来的。 |
|
b********n
发帖数: 38600 | 10 中医主要用heuristic的方法，西医主要用analytic的方法 |
|
g****5
发帖数: 1639 | 11 没有必要望文生义地认为现阶段的人工智能就真的是想模拟高级生物比如人的智能。就
当成是“夫妻肺片”这样的概念理解就行了。人工智能只是个学术界忽悠出来用以骗经
费的概念而已。顶多相信后面俩字“智能”就行了，跟“人工”实在没关系。其实还是
machine learning这个词比较贴切，就是让silicon machine具有一定学习的能力，做
自动的决策。
另外搞生物的也有误解，认为人工智能是去试图模拟人脑的智能。从现阶段人脑的工作
模式从生物上都没搞清楚来攻击，这也是没必要。还是那句话，跟人工无关，只是利用
现有的计算条件，做一些简单的学习模型和预测。你们去搜一搜，AI的一个经典定义是
这样的：The use of computers to solve problems that previously could only be
solved by applying human intelligence. 按照这个定义，连qq的棋牌室都算，因为
先前只有人才会下棋。另外一个定义则比较接近现在的机器学习：The use of a
specific set of programming te... 阅读全帖 |
|
a******9
发帖数: 20431 | 12 尼玛 要是给我独占一天就好了 手头上好多东西没法算 只能用heuristic搞个次优值出来
500 |
|
g******t
发帖数: 18158 | 13 heuristic algorithms in conjunction with optimization algorithms |
|
s******c
发帖数: 1920 | 14 n只要比人类所能算的步数多一就可以了。而且人在某一手棋长算了以后，未必有足够
精力体力保持同样算力。电脑则不然。
也不用找最优解，足够优就好了。其实也没有最优解，优不优都是一个heuristic.
而且人也是凭经验或直觉决定哪些路数需要算 哪些不要，这个其实就电脑算法是在决
策树里剪枝或者决定先算哪个后算哪个，当然这个也是人类最强的地方。这些依赖于让
机器来学谱，学的好不好不说，但起码绝不会出现机器不能评估没见过的棋局，那你也
太低估学cs的了。siri装在iPhone上的时候也没听过你说话，为什么还能听懂wsn的英
语？ |
|
p*******m
发帖数: 667 | 15 ________________________________________
deguoguanglong <[email protected]
/* */>
mitbbs id P235 / P245
请求加入，并祝一切顺利。
创教不如改教，模仿一贯道搞五教合一
创立新教，不如高仿现有宗教，还可以塞点私货。
一贯道搞五教合一，是个很不错的思路。五教都是神，都是道，都是天帝/上帝，都是
唯一真神,都是宇宙最大佛，都是自然神。当然现在回教徒进入疯狗模式了，暂时可以
把回教排除。
这样可以随意盗用各派教义，但实践上取那些通俗易懂的部分，行善积德，广种福田之
类的。同样也可以随意盗用各派的宗教仪式。
基础教义容易，下几本电子书综合一下就行。后面传教才困难。开山总坛设在哪里，总
坛设在大城市，才有利传教，但大城市地价又太高。弄一个总坛，从土地到建筑加各种
高仿神器，中小城市也得几十万吧。第一笔启动经费哪里来。
总坛有了，后面外地个个分坛香堂怎么管理？是搞上下级任命? 还是民主选举？
________________________________________
[ema... 阅读全帖 |
|
f*********5
发帖数: 367 | 16 像A*这些算法都需要一个heuristic function,这就是AI的直觉。如果不是直觉的话这
次围棋赛电脑还是有要穷举。就是靠着AI的“直觉”，它们才能少考虑很多步，接近甚
至打败人类。 |
|
w**********5
发帖数: 1741 | 17 坐在李世石对面的那个人: 第三位主角出现了，中国台湾的黄世杰。
黄世杰的经历就比较中国化了。
1997年，黄世杰进入台湾交通大学读本科，2001年本科毕业，同时狂热喜欢下围棋，是
业余围棋高手。
本科毕业，没找到工作（开玩笑的，：）），于是想， 考个研吧，于是考上了台湾师
范大学。
2001年-2003年，黄世杰在台湾师范大学读研，学习计算机。
硕士毕业，还是没找到工作，于是留在台湾师范大学做临时工（Research Fellow）（
2003-2004）。
2004年，他觉得这样临时工不行，开始准备考博，2004年考取师范大学博士。
2004-2011年，完成博士论文。
千年老博啊，博士读7年，估计打破很多记录，估计是读博期间下围棋太多。
不过好歹完成了博士论文。
论文题目：
New Heuristics
for Monte Carlo Tree Search Applied to the Game of Go.
博士论文：应用于计算机自动围棋的启发式的MCTS算法。
2011年，博士毕业以后，还是找不到工作（谁要一个7年博士就是研究怎么下棋的博士
呢？，呵呵），于是只能又去做临时工... 阅读全帖 |
|
发帖数: 1 | 18 比如码工，富士康员工，生物、化学千老。只要一项工作是well-defined，中国人就做
的又快又好。但是和人交流就不行了，更别说追白牛。
流水线工人这种最底端，相当于简单的有限状态机，只能反复重复做几个动作，把装配
工作做完了就回到初始状态，循环往复。
千老高端一点，具有一定的搜索功能，比如长晶体、跑胶、过柱子的时候能够筛选最佳
条件，而且会用heuristics。千老的搜索方式，一种是depth-first，比如开发合成路
线，一
步反应不成功就退回到之前一步，然后换一条路线重新搜索。一种是breadth-first，
比如搞催化。一个分子，这边加一个取代基，那边加一个氢键受体，各种过渡金属按序
号全试一遍。做出来之后试试有没有选择性，ee值够不够高。循环往复。Design space
很大，所以需要很多千老AI不断工作。
码农增加了深度学习功能，虽然比不过阿尔法狗，但是学会写if...else...else if够
用了。再增加一层的神经元处理function，一层神经元用来处理object。一层
神经元用来搞MVC，诸如此类。码农在学校里进行supervised learnin... 阅读全帖 |
|
w*******e
发帖数: 15912 | 19 退读清华、康奈尔 印第安纳大学博士 王垠:牛校生脑子貌似有病
文章来源: 王垠 于 2015-03-05
人物简介：王垠
1997年，考入四川大学计算机系97级。
2001年，保送清华大学计算机系软件所硕博连读，主要进行集成电路布线算法的研究。
2003年发表《完全用Linux 工作》、《写给支持和反对<完全用Linux工作>的人们》，
痛陈windows弊端、宣扬linux。
2004年8月，发表网络文摘《完全用linux工作》、《写给支持和反对<完全用Linux工作
>的人们》，痛陈windows弊端、宣扬linux，文章在中国的计算机和linux阵营引起极大
轰动效应，成为水木清华linuxapp版和中国多个linux社区的偶像级人物。
2005年，发表学术论文“The polygonal contraction heuristic for rectilinear
Steiner tree construction” 。
2005年9月22日在水木社区BLOG上发表了《清华梦的粉碎--写给清华大学的退学申请》
明确要求退学，痛斥国内高等教育弊端。
2006年8月，从清华退学后考G... 阅读全帖 |
|
K******i
发帖数: 530 | 20 写得不错。
退读清华、康奈尔 印第安纳大学博士 王垠:牛校生脑子貌似有病
文章来源: 王垠 于 2015-03-05
人物简介：王垠
1997年，考入四川大学计算机系97级。
2001年，保送清华大学计算机系软件所硕博连读，主要进行集成电路布线算法的研究。
2003年发表《完全用Linux 工作》、《写给支持和反对<完全用Linux工作>的人们》，
痛陈windows弊端、宣扬linux。
2004年8月，发表网络文摘《完全用linux工作》、《写给支持和反对<完全用Linux工作
>的人们》，痛陈windows弊端、宣扬linux，文章在中国的计算机和linux阵营引起极大
轰动效应，成为水木清华linuxapp版和中国多个linux社区的偶像级人物。
2005年，发表学术论文“The polygonal contraction heuristic for rectilinear
Steiner tree construction” 。
2005年9月22日在水木社区BLOG上发表了《清华梦的粉碎--写给清华大学的退学申请》
明确要求退学，痛斥国内高等教育弊端。
2006年8月，从... 阅读全帖 |
|
w****5
发帖数: 46 | 21
王垠那篇“The polygonal contraction heuristic for rectilinear
Steiner tree construction” 在ASP-DAC 2005会议上灌了个best paper award.
想知道虎肉专职灌水多年，灌出过几篇这种量级的paper？ |
|
s***h
发帖数: 487 | 22 应该是 meta heuristics 领域的哲学问题 。。。
: 其实这是个哲学问题，也就是工业界求可行解，到底是用逻辑严密干净的解决方
案，还
: 是 come on whatever works 就上 。。。更上一层次，人工智能的智力，本身
也可能
: 就是不那么逻辑严密干净的 。。。 忘了那个讨论相关学术名词了 。。。
|
|
s***h
发帖数: 487 | 23 查了一下，坑爹术语没查出来，忘了。算了不找了。
: 应该是 meta heuristics 领域的哲学问题 。。。
: 案，还
: 也可能
|
|
|
c****x
发帖数: 6601 | 25 请原谅我使用了算命先生爱说的一句话作本期文章标题……
信命不认命
其实咱们谈论的都是严肃的事儿。
今天我们继续说罗伯特·弗兰克的Success and Luck: Good Fortune and the Myth of
Meritocracy （成功与运气：好运和精英社会的神话）这本书。
一个人的命运啊，当然要靠自我奋斗，但是也要考虑到历史的行程……
以及完全随机、根本不受你左右的“运气”。
前面我们说到，在高水平竞争中，运气非常非常重要，可以说世界上那些特别成功的人
也都是运气特别好的人。我感觉弗兰克这本书，最主要就是写给运气好的人看的，他想
教会这帮人怎么正确认识“运气”，他认为这样对大家都有好处。
那么一般人都是怎么对待运气的呢？如果想要做个智者，我们又应该怎么对待运气呢？
咱们先说一个真实的故事。
这件事发生在西班牙。有个人去投注站买彩票，说一定要选个尾数是48的号码。可能当
时的技术比较落后，没有电脑选号和现场打印，他只能在现有的彩票中反复找，好不容
易找到一张尾数是48的彩票买下。结果，几天后开奖，他果然中了大奖！
记者就问他中奖的秘诀是什么。他说：“当然有秘诀。买48是... 阅读全帖 |
|
s***h
发帖数: 487 | 26 AI 是真的。AI 并不限于 neuro netowk，其实也包括 trainable solver , 甚至传统
的 meta-heuristics 加 data science。
不过鳖不太容易搞出来，分配体制鼓励抄不鼓励创新。分配体制不支持底层系花孩子热
炕头工程师。 |
|
y****g
发帖数: 36950 | 27 你觉得你说的AI需要考虑伦理道德嘛？
我相信到这个世纪末也不可能出现所谓需要考虑伦理道德的AI。
：AI 是真的。AI 并不限于 neuro netowk，其实也包括 trainable solver , 甚至传统
：的 meta-heuristics 加 data science。 |
|
发帖数: 1 | 28 ...dijkastra连负value都不行
然鹅我也没问你di算法有什么缺陷
: 涉及微分几何的路径，就不是纯粹的 Dijkstra，不能保证多项式时间，
如果不
加 meta
: -heuristic 的话。因为问题本身不是 well-posed，well-conditioned 。
|
|
发帖数: 1 | 29 ...dijkastra连负value都不行
然鹅我也没问你di算法有什么缺陷
: 涉及微分几何的路径，就不是纯粹的 Dijkstra，不能保证多项式时间，
如果不
加 meta
: -heuristic 的话。因为问题本身不是 well-posed，well-conditioned 。
|
|
s***h
发帖数: 487 | 30 对数函数换元和三角函数换元，确实是计算科学里改善数字积分时的 condition
number 的巧妙办法。
不过还是有很多情况不容易。
Well-condition ill-posed problem 也是实用数学里的 meta-heuristics 的一个重要
且实用的事情。
: 继续。Zeta函数或者Gamma函数Alpha函数在z虚部不为零的情况下如何计算，这
个还没
: 有进展。回头再补一些已知的gap。其中一个是还没有证明Zeta函数的级数定义
与积分
: 定义等价。
: Zeta函数的级数定义是
: Zeta(z)=1/1^z 1/2^z 1/3^z ...
: Zeta函数的积分定义是Zeta(z)=Alpha(z)/Gamma(z)，
: Alpha(z)=integration from 0 to infinity of x^(z-1)/(e^x-1) dx，
: Gamma(z)=integration from 0 to infinity of x^(z-1)/e^x dx，
: 这两个的... 阅读全帖 |
|
发帖数: 1 | 31 http://theprepared.com/blog/no-the-2019-ncov-genome-doesnt-actually-seem-engineered-from-hiv/
2019-nCoV genome doesn’t really seem engineered from HIV
A group of bioinformaticians at two prestigious universities in Delhi, India
, published a preprint scientific manuscript on the bioRxiv preprint server
Friday has led many to speculate wildly that 2019-nCoV may have been
deliberately engineered using HIV protein sequences.
The paper, entitled “Uncanny similarity of unique inserts in the 2019-nCoV... 阅读全帖 |
|
发帖数: 1 | 32 有similarity matrix后就是个找minimum cost spanning tree
similarity matrix怎么定义就需要生物学知识了。。举个例子，可以基于Levenshtein
上加点heuristics |
|
发帖数: 1 | 33 王同学是看人家不顺眼总换。
我是看得差不多换一个，不会认为人家不行， 而是觉得美国博士就那么回事， 也就跟
我们农民种地差不多， 你认真做肯定错不了。
1997年，考入四川大学计算机系97级。
2001年，保送清华大学计算机系软件所硕博连读，主要进行集成电路布线算法的研究。
2003年发表《完全用Linux 工作》、《写给支持和反对<完全用Linux工作>的人们》，
痛斥windows弊端、宣扬linux。
2004年8月，发表网络文摘《完全用linux工作》、《写给支持和反对<完全用Linux工作
>的人们》，痛斥windows弊端、宣扬linux，文章在中国的计算机和linux阵营引起极大
轰动效应，成为水木清华linuxapp版和中国多个linux社区的偶像级人物。
2005年，发表学术论文“The polygonal contraction heuristic for rectilinear
Steiner tree construction” [2] 。
2005年9月22日在水木社区BLOG上发表了《清华梦的粉碎--写给清华大学的退学申请》
明确要求退学，痛斥国内高等教育... 阅读全帖 |
|
l****z
发帖数: 29846 | 34 For years now the climate campaign and the politicized science community has
been complaining that it has a “communications problem,” which can be
solved if only they shout louder, or get the human car alarm former Vice
President Al Gore to make an Oscar-winning documentary film or something.
Because, after all, it’s just so easy for a billion-dollar effort at
pushing the climate crisis to be undone by a handful of discredited “
skeptics” with only at tiny fraction of the resources environmenta... 阅读全帖 |
|
k****g
发帖数: 1509 | 35 I decided to support Barack Obama pretty early in the Democratic primary,
around spring of 2007. But unlike so many of his supporters, I never
experienced a kind of emotional response to his candidacy. I never felt his
election would change everything about American politics or government, that
it would lead us out of the darkness. Nothing Obama did or said ever made
me well up with tears.
Possibly for that same reason, I have never felt even a bit of the crushing
sense of disappointment that at... 阅读全帖 |
|
d******e
发帖数: 7844 | 36 Decon的结论其实是有一定道理的。只不过他未必明白更深层的含义，至少我下面说的
本科的统计大都不会提及，美国的硕士统计课程也比较少提及。读PhD的话，修过
Advnaced的Inference课程的话，应该明白我在说什么。
因为是五年前修的课了，所以个别地方可能说的不准确，但是思路应该基本正确。
当一个Bernoulli r.v.的参数(分布均值)非常接近0的时候，想要同时准确估计样本的
参数和样本方差是很难的。现在可以看到p肯定是非常小的，很可能是在1e-5~1e-6的数
量级上。这时想用MLE的Asymptotic normality来做近似就很成问题了，因为对分布的
方差的估计的方差对比分布的方差本身还要大，导致你对方差的估计十分不可靠，最后
testing的结果非常不准，CI也十分不可靠。
解决办法我说两种，感兴趣的可以去看。第一种是去做exact testing，不做近似，但
鉴于样本量大，计算量会非常大。第二种是在推导Asymptotic ditribution时做高阶泰
勒展开，这样可以获得更精确的近似。
当然，也可以Heuristic的去直接拿mean比或者用norm... 阅读全帖 |
|
d******e
发帖数: 7844 | 37 Decon的结论其实是有一定道理的。只不过他未必明白更深层的含义，至少我下面说的
本科的统计大都不会提及，美国的硕士统计课程也比较少提及。读PhD的话，修过
Advnaced的Inference课程的话，应该明白我在说什么。
因为是五年前修的课了，所以个别地方可能说的不准确，但是思路应该基本正确。
当一个Bernoulli r.v.的参数(分布均值)非常接近0的时候，想要同时准确估计样本的
参数和样本方差是很难的。现在可以看到p肯定是非常小的，很可能是在1e-5~1e-6的数
量级上。这时想用MLE的Asymptotic normality来做近似就很成问题了，因为对分布的
方差的估计的方差对比分布的方差本身还要大，导致你对方差的估计十分不可靠，最后
testing的结果非常不准，CI也十分不可靠。
解决办法我说两种，感兴趣的可以去看。第一种是去做exact testing，不做近似，但
鉴于样本量大，计算量会非常大。第二种是在推导Asymptotic ditribution时做高阶泰
勒展开，这样可以获得更精确的近似。
当然，也可以Heuristic的去直接拿mean比或者用norm... 阅读全帖 |
|
c*********7
发帖数: 7607 | 38
haha, dude I am serious, it is kind of interesting to see why and how people
are persuaded by others, group heuristics, instead of their own observations |
|
j******u
发帖数: 1968 | 39 俺是作stochastic／convex optimization的，现在这个领域有很好的课题，呵呵。
写proposal的时候不发愁idea，但是对education这方面就抓瞎了，我教过几门
optimization的课程，
学生感觉很慢，根本不能follow，很郁闷，听别的学校同事说也都这个德行，于是想行
为艺术一把，弄个
survey，放在proposal里面装一装酷，其实主要是了解学生的需要，这样说话更有分量
一些。
http://www.uncertaintylab.com/survey/index.html
主要想弄清如下几点（下面的问题仅仅是中文的摘要，英文原文看上面的link）
1。在engineering里面optimization到底有多重要
2。当你碰到一个非常恶心的model的时候是用heuristic还是试图找到最优解？
3。你对现在的optimization package满意不？
4。如何才能提高学习效率？
5。你有没有想过用convex的方法来model你的问题？
6。你知不知道现在的内点算法已经非常成熟了，大规模的问题可以用内点来解决？
刚刚设计了一 |
|
t**********t
发帖数: 12071 | 40 我正好下个学期要教convex optimization
1。在engineering里面optimization到底有多重要
灰长灰长重要。我们处理问题一般是MODEL成优化问题，下面就是纯优化问题了。
2。当你碰到一个非常恶心的model的时候是用heuristic还是试图找到最优解？
这要看我晚饭吃饱了没有
3。你对现在的optimization package满意不？
还好吧
4。如何才能提高学习效率？
晚饭少吃点
5。你有没有想过用convex的方法来model你的问题？
经常使用。不过stochastic control如何进行decomposition似乎还很难？如果能够
decompose，我们这一行里用处大大地有。
6。你知不知道现在的内点算法已经非常成熟了，大规模的问题可以用内点来解决？
知道。 |
|
j*********g
发帖数: 153 | 41 optimization
是精确的那种，不带heuristic的，呵呵 |
|
g********r
发帖数: 8017 | 42 那倒不是，大概是我比喻不当。
只顾抓耗子的通常做很多heuristic的东西，在谷仓里能抓耗子，换个环境到了公寓里
就未必抓的到耗子了。
有理论的未必只是为了漂亮光鲜，有的理论确实让这猫长得雄壮有力，到了哪里都能抓
到耗子。只是这样的东西太难做到了。 |
|
n**********o
发帖数: 1016 | 43 https://www.nae.edu/MediaRoom/178117.aspx
Abadi, Martín, principal scientist, Google Inc., Palo Alto, Calif. For
contributions to the formal theory of computer security.
Abrahamson, Norman A., chief engineering seismologist, Pacific Gas &
Electric Co., Piedmont, Calif. For contributions to seismic hazard
assessment and for leadership in engineering seismology and earthquake
engineering.
Adams, Robert W., senior fellow, Analog Devices Inc., Acton, Mass. For
contributions to digital storage and... 阅读全帖 |
|
b****e
发帖数: 460 | 44 对于FA的理解
首先，FA只管分析股市背后的每一个公司的状况，跟股价没有关系，一个公司有没有股
价照样运转。
其次，FA就像一个医生诊断病人的状况，是从小到大，从下而上的一点一点的看的。
500个公司10年的年报都看过的人也就巴菲特这样人能干。这才是系统细致的FA。
另外，FA从来不考虑股价，就像医生从来不看病人的身价来决定病情一样。我还是那个
观点，股价就像一片叶子随风飘动，根据FA这片叶子一定会最终落地，但是叶子的下一
秒钟的走向我不知道，多少时间会落地我不知道。所以，最后我只赌叶子会落地。
当然，整体来讲，看看负债状况，现金状况，盈利状况，整体的经济状况，500个大公
司的整体情况也是可以粗略的估计出来。不是说有什么heuristic rule吗？
跟大公司比较，只要你我认真做FA，不一定做得比一般大公司差的。原因很简单，官僚
结构的不同，奖励机制的不同。 |
|
m*********y
发帖数: 1890 | 45 Dca 是王道。
Backtest 的heuristic基本不灵的。类似的ivy portfolio 就是。
Move: |
|
s********g
发帖数: 28 | 46 CS方向，希望对大家准备面试有帮助
1. 用stack class来实现queue，具体用几个stack不限。完了以后问怎么实现thread
safety，然后是怎么测试。
2. 实现strstr(str1, str2)，如果str2是str1的子串，返回true，否则返回false。实
现完了以后问如何测试。
3. 给定一个integer array with both positive and negative numbers，return a
contiguous subarray with the largest sum. 我本来想用dynamic programming实现
，但面试官希望按照他的一个更heuristic的思路来解，最后勉强搞定。
4. 给定一个排好序的linked list，删除其中所有的重复元素。比如给定1->2->3->3->
4->4->5，返回1->2->5。给定1->1->1->2->3，返回2->3。看起来简单，一边写一边发
现许多细节需要小心应对，好在最后搞定。
5. 给你三个烤箱，每个烤箱可以同时烤两片面包，需要的时间分别是3分钟，4分钟和3 |
|
n******r
发帖数: 1247 | 47 如果要找最优解greedy肯定不行。heuristics解法中 B.W. Kernighan(就是K&R的那个K）
和S.Lin在73年给出一个动态k-opt的算法，称为L-K算法，基本100左右city的问题能找到
最优解，（当时的计算能力只能验证50左右个city的最优解）
L-K算法用到的动态opt的idea在此后20年基本unbeatable，面试能说到这个idea应该可
以了
http://www.crema.unimi.
it/~righini/Didattica/Algoritmi%20Euristici/MaterialeAE/Lin%20Kernighan%
20TSP.pdf
L-K算法无数人企图改进但效果都不大，直到98年丹麦人Keld helsgaun提出LKH算法（
除了保留动态opt的idea，其他基本改的面目全非）。目前能用branch&bound计算出最
优解的问题（大概10万city的level），LKH都能找到最优解。所有未知最优解的问题（
超过百万city，）最好解的记录也都由LKH保持。LKH的复杂度大约在O(N^2.3)。
其中最牛的idea是 |
|
s******e
发帖数: 841 | 48 什么公司会问这个啊，google一下吧，有很多heuristics的算法，但是至今好像还没有
很好的找的optmial solution的算法，如果# of nodes比较大的话 |
|
g*******y
发帖数: 1930 | 49 对
DP只是解决问题的一种方法，跟问题的计算复杂度没有直接关系。
NP-hard的问题的DP解法多了去了，举个例子就是背包问题，还有什么subset sum
我以前纠结的是这个题到底有没有多项式解，总隐隐的感觉能通过一些数论的东西找到
漂亮的快速解。后来
尝试不成功所以感觉很难。如果这个题真是NP-hard，难怪我当时觉得这么难...
greedy in general处理这个问题是不能得到正确解的，heuristic搜索解或者剪枝的回
溯可能平均性能
好些。 |
|
l******o
发帖数: 144 | 50 嗯，TSP还能用DP做呢。
对
DP只有解决问题的一种方法，跟问题的计算复杂度没有直接关系。
NP-hard的问题的DP解法多了去了，举个例子就是背包问题，还有什么subset sum
我以前纠结的是这个题到底有没有多项式解，总隐隐的感觉能通过一些数论的东西找到
漂亮的快速解。后来
尝试不成功所以感觉很难。如果这个题真是NP-hard，难怪我当时觉得这么难...
greedy in general处理这个问题是不能得到正确解的，heuristic搜索解或者剪枝的回
溯可能平均性能
好些。 |
|
