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

owenwilder 发表于 2018-4-26 07:07
感覺類似leet 七八起 飛機票

飞机票不需要再飞回来。而且那题就是简单的最短路径，都没有要求你经过所有的点

问没有问可不可以approximate？如果可以，可以用nearest neighbour来greedy的扫

论坛匿名用户 发表于 2018-4-25 10:50
求思路 自顶

先用 floyd 算出点与点之间最短距离，然后用这个距离构造新图，在这个图上跑 TSP

复杂度 O(n2^n)

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

aunom 发表于 2018-4-26 07:26
先用 floyd 算出点与点之间最短距离，然后用这个距离构造新图，在这个图上跑 TSP

复杂度 O(n2^n)

这个可以证明是最优解么？

idatascience 发表于 2018-4-26 08:11
这个可以证明是最优解么？

证明不了，你要是能证明你就可以拿图灵奖了

idatascience 发表于 2018-4-26 07:59
多谢楼主。想问一下楼主暴力DFS的答案，结束条件就是所有点都被访问过了，然后最后停在了Target上，我想 ...

楼主后来跟面试官沟通之后写了一个每个节点只能访问一次的解法

我这种onsite都没考dp，没考图，没考树的且拿到offer的，是不是太幸运了。。。