s***h
发帖数: 662 | 1 我碰到一个这样的题目，
You have a map of n cities connected by routes. A route (u,v) has length
d(u,v). you are in city s now and want to go to city t in m days. additional
constraints are:
1. you have maximum travel distance f(d), d from 1 to m.
2. you have cost c(u) to stay overnight in city u.
now it asks you to come up with a plan that
1. starts from s, takes exactly m days to go to t.
2. spending exactly one night at each city you pass.
3. do not travel more than f(d) on day d.
4. minimize the total cost of staying, i.e., sum of c(u).
我的想法是，
首先构造一个新的图，用V指代所有city，
s --> V - {s,t} --> V - {s,t} --> V - {s,t} -->...--> t
任何path(s,t)的长度为m, 每一步的边加以调整，比如第一步，从s出发的边就可以去
掉那些 > f(1)的，从第一个 V - {s,t} 到第二个V - {s,t}的边就可以去掉
那些 > f(2)的，依此类推。在原来图中的(u,v)现在就生成两条有向的边，长度为
c(v), 即在v过夜的花费。
那么， 原来的问题就可以变为在这个图里面寻找一个最短路径。还有一个差别在于这
个图里面有可能会出现环路。比如，s -> v1 -> v2 -> v3 -> v1
接下来我打算这样，还是按照dijkstra那样每步选择当前最小的边，然后relax所有下
一步相邻的。但是做法有一些调整。
原来的算法里面，每步都更新节点的d(u), 现在这个d(u)除了存储最短路径长度之外，
还要存储路径上的边数，还要存储当前的路径（为了避免环路）。这样每个节点都要存
储最多m条路径（路径上的边数分别从1到m），重新标记d(u)=(len, # of edges,
edges).
在选择了当前最小的d(u)之后，relax所有和u相邻的节点。具体做法是对于每个
相邻节点v, 首先判断是否已经在路径中出现过，如有则放弃，否则的话，如果
d(u).len + (u,v)比起现在同样边数(d(u).#ofedges + 1)的那个entry小，就更新最短
路径长度和路径）。
这个算法在找到第一条(s,t)path的时候，或者是穷尽了所有边的时候停止（那么最后
输出的这个path就是结果）
这样，只要有小于即将找到的(s,t)path的partial path，总是会被check, 直到它大于
即将找到的(s,t)path。
比如说，
5 5 5 7 6
s ---- v1 ---- v2 ---- v3 ---- v4 ---- t
\
23- v5 ---- v3 ---- v6 ---- v7 ---- t
1 1 1 1
在这个情况下，在v3节点开始的时候，存储
(15, 3, [s, v1, v2, v3]),
v4: (22, 4, [s, v1, v2, v3, v4])
然后，即将找到的(s,t)path 长度为28，大于23(s-v5), 于是explore(s,v5),
之后v3就变为(15, 3, [s, v1, v2, v3]), (24, 2, [s, v5, v3]), 之后，
v6: (25, 3, [s, v5, v3, v6])
v7: (26, 3, [s, v5, v3, v6, v7])
t: (27, 3, [s, v5, v3, v6, v7, t]) 依然小于28，这样，27就是第一个找到的(s,t)
path.
如果v7--t改成3， 那么28的path还是会被找到，算法就停止了
我觉得这个想法太复杂了，而且说不定还有错误。有哪位有更好的办法吗？ | k****x
发帖数: 265 | 2 may use DP,
save costs and days at each nodes,
then start from minimum cost path, check the m days and f(d) condition,
iterate
until find the pathway
I think I am smart, but still can not get a job, hoho | y*******g
发帖数: 6599 | | s***h
发帖数: 662 | 4
你能说的详细一点吗？
【在 k****x 的大作中提到】
: may use DP,
: save costs and days at each nodes,
: then start from minimum cost path, check the m days and f(d) condition,
: iterate
: until find the pathway
: I think I am smart, but still can not get a job, hoho
| y*******g
发帖数: 6599 | 5 搜索图的时候信息本来就在node里面
你说的dp用什么subproblem?
【在 k****x 的大作中提到】
: may use DP,
: save costs and days at each nodes,
: then start from minimum cost path, check the m days and f(d) condition,
: iterate
: until find the pathway
: I think I am smart, but still can not get a job, hoho
| k****x
发帖数: 265 | 6 大致思路，
还没想清楚
【在 s***h 的大作中提到】
:
: 你能说的详细一点吗？
| k****x
发帖数: 265 | 7 不完全DP,类似DP的过程
【在 y*******g 的大作中提到】
: 搜索图的时候信息本来就在node里面
: 你说的dp用什么subproblem?
| d*******l
发帖数: 338 | 8 我觉得可以用dp。dp[i][j]表示正好用j天到达第i个city的最小代价，初始时dp[i][1]
= d(s,i)>f(1)?INF:d(s,i).
dp[i][j+1] = min{dp[k][j] + c(k) + (d(k,i)>f(j+1)?INF:d(k,i))}
最后要求的就是dp[t][m]。复杂度O(n^2m)。 | s***h
发帖数: 662 | 9
我想了一下，好像可以这样。
就是说，从s出发，比如说s可以到v1, v2, vk（假定已经check过f(1)),
那么, path(s,t,m) = min (c(v1) + path(v1,t,m-1)
c(v2) + path(v2,t,m-1)
...
c(vk) + path(vk,t,m-1))
最多有n个子问题。但是每个子问题都不一样啊。Graph of path(v1,t,m-1) does not
have s, v1, Graph of path(v2,t,m-1) does not have s, v2.
【在 k****x 的大作中提到】
: 大致思路，
: 还没想清楚
| d*******l
发帖数: 338 | 10 没要求走过的不能再走吧？那就应该没问题，见我楼上的post。
not
【在 s***h 的大作中提到】
:
: 我想了一下，好像可以这样。
: 就是说，从s出发，比如说s可以到v1, v2, vk（假定已经check过f(1)),
: 那么, path(s,t,m) = min (c(v1) + path(v1,t,m-1)
: c(v2) + path(v2,t,m-1)
: ...
: c(vk) + path(vk,t,m-1))
: 最多有n个子问题。但是每个子问题都不一样啊。Graph of path(v1,t,m-1) does not
: have s, v1, Graph of path(v2,t,m-1) does not have s, v2.
| | | s***h
发帖数: 662 | 11
1]
可是你如何确定在你的解中，每个city只走了一次。
【在 d*******l 的大作中提到】
: 我觉得可以用dp。dp[i][j]表示正好用j天到达第i个city的最小代价，初始时dp[i][1]
: = d(s,i)>f(1)?INF:d(s,i).
: dp[i][j+1] = min{dp[k][j] + c(k) + (d(k,i)>f(j+1)?INF:d(k,i))}
: 最后要求的就是dp[t][m]。复杂度O(n^2m)。
| d*******l
发帖数: 338 | 12 题目里并没有明显要求一个city只能经过一次啊。不然这题就类似于求最短哈密顿路径
(n=m时)，没什么简单办法了吧
【在 s***h 的大作中提到】
:
: 1]
: 可是你如何确定在你的解中，每个city只走了一次。
| s***h
发帖数: 662 | 13
题目不精确，看来。但是...假定不能呢？
【在 d*******l 的大作中提到】
: 没要求走过的不能再走吧？那就应该没问题，见我楼上的post。
:
: not
| s***h
发帖数: 662 | 14
恩，好像是它不够精确。我在原文里提的那个方法，没有用递归。
就是用普通的最短路径算法。如果不考虑环路，
和你的时间一样。但是我在每个节点都存储了一个当前路径，这样每
更新之前先搜索是否有环，于是每次要多O(m)，最后就是O(m^2n^2).
你看看对不对？
【在 d*******l 的大作中提到】
: 题目里并没有明显要求一个city只能经过一次啊。不然这题就类似于求最短哈密顿路径
: (n=m时)，没什么简单办法了吧
| d*******l
发帖数: 338 | 15 那应该就没太好的办法了，得把经过的点的状态加到dp中。如果n不太大的话，2^n还能
接受。你可以搜索一下最短哈密顿回路的dp算法，这个题多了一些限制，但想法类似。
我认为真要是在面试里的话，不限制经过city的次数比较合理。那样就是比较典型的dp
了。
【在 s***h 的大作中提到】
:
: 恩，好像是它不够精确。我在原文里提的那个方法，没有用递归。
: 就是用普通的最短路径算法。如果不考虑环路，
: 和你的时间一样。但是我在每个节点都存储了一个当前路径，这样每
: 更新之前先搜索是否有环，于是每次要多O(m)，最后就是O(m^2n^2).
: 你看看对不对？
| d*******l
发帖数: 338 | 16 有点长没法很快弄明白，不过觉得可能有问题。还是像上面说的，如果m=n（也可能是n
+1），就算不加别的限制，也是相当于求一个点到另一个点经过所有其他点的最短路径
，你确定只要多项式时间就能出来？
【在 s***h 的大作中提到】
:
: 恩，好像是它不够精确。我在原文里提的那个方法，没有用递归。
: 就是用普通的最短路径算法。如果不考虑环路，
: 和你的时间一样。但是我在每个节点都存储了一个当前路径，这样每
: 更新之前先搜索是否有环，于是每次要多O(m)，最后就是O(m^2n^2).
: 你看看对不对？
| s***h
发帖数: 662 | 17
是n
这个就变成hamilton cycle问题了。应该是有问题。可是我一下子又找不到问题出在哪
...
【在 d*******l 的大作中提到】
: 有点长没法很快弄明白，不过觉得可能有问题。还是像上面说的，如果m=n（也可能是n
: +1），就算不加别的限制，也是相当于求一个点到另一个点经过所有其他点的最短路径
: ，你确定只要多项式时间就能出来？
| a********m
发帖数: 15480 | 18 A* 变体吧。不取最短，但是取m天的结果，加上visited标记。。
additional
【在 s***h 的大作中提到】
: 我碰到一个这样的题目，
: You have a map of n cities connected by routes. A route (u,v) has length
: d(u,v). you are in city s now and want to go to city t in m days. additional
: constraints are:
: 1. you have maximum travel distance f(d), d from 1 to m.
: 2. you have cost c(u) to stay overnight in city u.
: now it asks you to come up with a plan that
: 1. starts from s, takes exactly m days to go to t.
: 2. spending exactly one night at each city you pass.
: 3. do not travel more than f(d) on day d.
|
|
