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 : 怎么算?有没有快速算法呢?
|