k****f
发帖数: 3794 | 1 图上两点的最短路径，要求此路径至少经过k个node
怎么算？有没有快速算法呢？ |
s****u
发帖数: 118 | 2 正权？简单路？
【在 k****f 的大作中提到】
: 图上两点的最短路径，要求此路径至少经过k个node
: 怎么算？有没有快速算法呢？
|
k****f
发帖数: 3794 | 3 嗯，正权，简单的，
写出公式来，好像不是TUM的, nnd
【在 s****u 的大作中提到】
: 正权？简单路？
|
s****u
发帖数: 118 | 4 我觉得没有多项式解法
多少个点？
【在 k****f 的大作中提到】
: 嗯，正权，简单的，
: 写出公式来，好像不是TUM的, nnd
|
k****f
发帖数: 3794 | 5 30k左右的点。要求的path最少10－20个
没法全部枚举的。
【在 s****u 的大作中提到】
: 我觉得没有多项式解法
: 多少个点？
|
r*******y
发帖数: 290 | 6 在objective function里面加上一个penalty function
当nodes
然后optimize吧，比如用genetic algorithm
复杂度嘛，就不知道了
【在 k****f 的大作中提到】
: 图上两点的最短路径，要求此路径至少经过k个node
: 怎么算？有没有快速算法呢？
|
c********x
发帖数: 84 | 7
The question ask you how to use a depth search to navigate a tree, you can
do the rest.
【在 k****f 的大作中提到】
: 图上两点的最短路径，要求此路径至少经过k个node
: 怎么算？有没有快速算法呢？
|
