g*******y
发帖数: 1930 | 1 你有一张购物单上有N个不同的东西，你家位于(0,0),你家周围有S家超市（超市的位置
坐标已知），每家超市有你购物单的上一个或者多个物品出售，并且你知道每家超市的
价格表。并且你的购物清单中有某些东西（比如冰淇淋牛奶等）很容易腐败，所以买到
这些东西后必须立刻回家一趟，再继续购物。
input：购物单(某些物品可能是容易腐败的)，S家超市的地址，每家超市有卖的购物单
上的一样或多样东西&价格，单位距离开车花费的汽油价
问一个算法，找一个最低的价格，买到购物单上全部的东西。 |
g*******y
发帖数: 1930 | 2 这个应该至少是NP的，补充一下问题规模，购物单上最多有15样东西，你家周围最多有
50家超市。 |
c*****t
发帖数: 1879 | 3 这题应该不是 NP ，因为距离是靠坐标来弄的。也就是说，可以利用 delaunay
triangle 之类的缩减搜索范围。
【在 g*******y 的大作中提到】
: 这个应该至少是NP的，补充一下问题规模，购物单上最多有15样东西，你家周围最多有
: 50家超市。
|
h*******e
发帖数: 225 | 4 这题显然是NPC的。。。很容易把TSP规约到这个这个问题。
【在 c*****t 的大作中提到】
: 这题应该不是 NP ，因为距离是靠坐标来弄的。也就是说，可以利用 delaunay
: triangle 之类的缩减搜索范围。
|
c*****t
发帖数: 1879 | 5 难说。因为 TSP 是指 general graph 。但是，这个问题是通过坐标。也就是说
A B
C
D E
的话，任何考虑要去 C 的 path，只需要考虑 C 在 delaunay triangle 里相邻
的几个就是了。
也就是说，可以证明，如果 A, B, D, E 不是买了以后马上就回去的点，那么任
何解里面，去 C 的前一个点，必定是 A, B, D, E 之中一个。这道题稍微麻烦点
就在于有些店买了以后必须马上回去。
比如极端点，如果所有的商店都在 x axis 上，这问题就很 trivial 。
【在 h*******e 的大作中提到】
: 这题显然是NPC的。。。很容易把TSP规约到这个这个问题。
|
g*******y
发帖数: 1930 | 6 我开始也是这么想，不过经coconut提醒后发现应该不是NP的。不过貌似还是很难写出
来。
【在 h*******e 的大作中提到】
: 这题显然是NPC的。。。很容易把TSP规约到这个这个问题。
|
f******k
发帖数: 297 | 7 显然是NPC。特殊情况等价于Euclidean TSP。
【在 g*******y 的大作中提到】
: 你有一张购物单上有N个不同的东西，你家位于(0,0),你家周围有S家超市（超市的位置
: 坐标已知），每家超市有你购物单的上一个或者多个物品出售，并且你知道每家超市的
: 价格表。并且你的购物清单中有某些东西（比如冰淇淋牛奶等）很容易腐败，所以买到
: 这些东西后必须立刻回家一趟，再继续购物。
: input：购物单(某些物品可能是容易腐败的)，S家超市的地址，每家超市有卖的购物单
: 上的一样或多样东西&价格，单位距离开车花费的汽油价
: 问一个算法，找一个最低的价格，买到购物单上全部的东西。
|
f******k
发帖数: 297 | 8 其实Euclidean TSP也是NPC。
【在 c*****t 的大作中提到】
: 难说。因为 TSP 是指 general graph 。但是，这个问题是通过坐标。也就是说
: A B
: C
: D E
: 的话，任何考虑要去 C 的 path，只需要考虑 C 在 delaunay triangle 里相邻
: 的几个就是了。
: 也就是说，可以证明，如果 A, B, D, E 不是买了以后马上就回去的点，那么任
: 何解里面，去 C 的前一个点，必定是 A, B, D, E 之中一个。这道题稍微麻烦点
: 就在于有些店买了以后必须马上回去。
: 比如极端点，如果所有的商店都在 x axis 上，这问题就很 trivial 。
|
b***e
发帖数: 1419 | 9 Reduction to TSP:
* N = S
* there's exactly 1 target at each store
* there's no ice cream |
v****s
发帖数: 1112 | 10 ft, this one is from Google code jam..... please reference.
【在 g*******y 的大作中提到】
: 你有一张购物单上有N个不同的东西，你家位于(0,0),你家周围有S家超市（超市的位置
: 坐标已知），每家超市有你购物单的上一个或者多个物品出售，并且你知道每家超市的
: 价格表。并且你的购物清单中有某些东西（比如冰淇淋牛奶等）很容易腐败，所以买到
: 这些东西后必须立刻回家一趟，再继续购物。
: input：购物单(某些物品可能是容易腐败的)，S家超市的地址，每家超市有卖的购物单
: 上的一样或多样东西&价格，单位距离开车花费的汽油价
: 问一个算法，找一个最低的价格，买到购物单上全部的东西。
|
