w***u
发帖数: 156 | 1 版上牛多，特来请教
1. 给定一个有向图， 边是有非负权重的，找最短路径，这个简单，用Dijkstra算法
2. 如果带有约束条件，如果某两个点（这两个点不是相邻店，而是有且只隔了一个点
）不能同时出现在path中， 这时候最短路径如何求？
约束条件比如 n2不能和n5同时出现在路径中
n1----n2---n4---n5---n7
| | |
|-----n3----|---n6----| |
g*****g
发帖数: 34805 | 2 这不是很简单，分别去掉n2和n5求最短路径就完了。
【在 w***u 的大作中提到】
: 版上牛多，特来请教
: 1. 给定一个有向图， 边是有非负权重的，找最短路径，这个简单，用Dijkstra算法
: 2. 如果带有约束条件，如果某两个点（这两个点不是相邻店，而是有且只隔了一个点
: ）不能同时出现在path中， 这时候最短路径如何求？
: 约束条件比如 n2不能和n5同时出现在路径中
: n1----n2---n4---n5---n7
: | | |
: |-----n3----|---n6----|
|
w***u
发帖数: 156 | 3 思路不错，问题在于如果有好几组这样的节点限制，如果操作阿？
如果n3和n6不能放在一起
如果图大一点，限制数多一点，恐怕不行哦
【在 g*****g 的大作中提到】
: 这不是很简单，分别去掉n2和n5求最短路径就完了。
|
s*****n
发帖数: 5488 | 4 最短路径的实质是动态变成如果有约束条件不能使用公开人员的四有结果的话,我上的
问题可能就是运动车多少是时间解决的
版上牛多，特来请教1. 给定一个有向图， 边是有非负权重的，找最短路径，这个简单
，用Dijkstra算法2. 如果带有约束条件，如果某两个点（这两个点不是相邻店，而是
有且只隔了........
【在 w***u 的大作中提到】
: 思路不错，问题在于如果有好几组这样的节点限制，如果操作阿？
: 如果n3和n6不能放在一起
: 如果图大一点，限制数多一点，恐怕不行哦
|
p*****2
发帖数: 21240 | 5
DFS就可以了吧？
【在 w***u 的大作中提到】
: 版上牛多，特来请教
: 1. 给定一个有向图， 边是有非负权重的，找最短路径，这个简单，用Dijkstra算法
: 2. 如果带有约束条件，如果某两个点（这两个点不是相邻店，而是有且只隔了一个点
: ）不能同时出现在path中， 这时候最短路径如何求？
: 约束条件比如 n2不能和n5同时出现在路径中
: n1----n2---n4---n5---n7
: | | |
: |-----n3----|---n6----|
|
w***u
发帖数: 156 | 6 能具体说说么？
【在 s*****n 的大作中提到】
: 最短路径的实质是动态变成如果有约束条件不能使用公开人员的四有结果的话,我上的
: 问题可能就是运动车多少是时间解决的
:
: 版上牛多，特来请教1. 给定一个有向图， 边是有非负权重的，找最短路径，这个简单
: ，用Dijkstra算法2. 如果带有约束条件，如果某两个点（这两个点不是相邻店，而是
: 有且只隔了........
|
w***u
发帖数: 156 | 7 DFS 应该是不行的
【在 p*****2 的大作中提到】
:
: DFS就可以了吧？
|
p*****2
发帖数: 21240 | 8
为什么不行？
【在 w***u 的大作中提到】
: DFS 应该是不行的
|
k**********g
发帖数: 989 | 9
好像是正解.
A shortest path from n0 (starting point) to ny (any point) can be classified
as:
n0 ... ... ny (not touching any constrained point), OR
n0 ... n2 ... ny (touching only n2), OR
n0 ... n5 ... ny (touching only n5), OR
... (more combinations if there are additional constrains)
The best result from the first class is simply computed by removing all
constrained points from the graph.
For each of the remaining classes, the search can be broken down into:
(e.g. for the class that allows n2, rejects n5)
Find shortest path from n0 to n2;
Find shortest path from n2 to ny;
Compare the sum (n0 ... n2, n2 ... ny) with the sum (n0 ... ny) and keep
the better result.
Likewise for other cases.
To speed up search, the Dijkstra algorithm will be run multiple times, each
time using a constrain point as origin. That is, it will be run with n0 as
origin;, then re-run with n2 as origin; then re-run with n5 as origin; and
so on.
【在 g*****g 的大作中提到】
: 这不是很简单，分别去掉n2和n5求最短路径就完了。
|
w***u
发帖数: 156 | 10 如果n3 和n6也是constraints，
碰巧，n0...n2 ...ny 中包含n3 和 n6
n0...n5 ...ny 中包含n3 和 n6,
而且当iter n3或者n6的时候，都包含n2 和n5, 那这个算法就不适合了吧
classified
【在 k**********g 的大作中提到】
:
: 好像是正解.
: A shortest path from n0 (starting point) to ny (any point) can be classified
: as:
: n0 ... ... ny (not touching any constrained point), OR
: n0 ... n2 ... ny (touching only n2), OR
: n0 ... n5 ... ny (touching only n5), OR
: ... (more combinations if there are additional constrains)
: The best result from the first class is simply computed by removing all
: constrained points from the graph.
|
s*****n
发帖数: 5488 | 11 最短路径算法是dynamic programming。 就是用sub-optimal solution递归的算。
如果最优解不是有两个sub 最优解构成，那么不能用DP.
例如，TSp问题就是NPC的。你举得例子的极端情况。
那么只有指数时间复杂度的naive algo可以用了。例如bfs,dfs.
【在 w***u 的大作中提到】
: 能具体说说么？
|
