原地爆炸没见过这么难得Google电面

cchongwen73

面试就是刷人品只能多拜拜了＠＠

kevinxw

jt345 发表于 2018-4-25 14:53
是graph里面的经典算法吧，第一个是求minimum span，第二个是shortest path（greedy algorithm)

你也得凉。要经过所有点。

AugLily

byrlhb 发表于 2018-4-25 19:21
旅行商问题是只访问一次这个不是可以访问多次所以应该是欧拉环问题？

Eulerian cycle 是访问每条边，LZ这个问题是 Hamiltonian path. 这个问题是NP complete的。
http://mathworld.wolfram.com/EulerianCycle.html
https://en.wikipedia.org/wiki/Hamiltonian_path

AugLily

byrlhb 发表于 2018-4-25 19:21
旅行商问题是只访问一次这个不是可以访问多次所以应该是欧拉环问题？

噢不对，如果可以访问多次的话也不是 Hamiltonian path，后者是每个点只能访问一次……欧拉环是每条边只能用一次……这个感觉是更加 general 的图的问题了

c2issy

摸摸楼主。做hardware的表示长见识了。

csehao

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

csehao

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

csehao

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

dreamoffer17

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

csehao

原地爆炸 没见过这么难得Google电面