代码之家 › 专栏 › 技术社区 › Ezku

给定一个图中的游动列表来确定边权重

graph-theory graph language-agnostic

Ezku · 技术社区 · 16 年前

在有向加权图中,给定一个带游程长度(加权和)的游程列表,可以确定边的权重吗?我知道行走路线上排列的数量和质量将决定任何可能答案的质量,但让我们假设所有可能的行走及其长度都已给出。如果一个明确的答案是不可能的,什么样的事情可以
如果有几次类似的散步,可能给出了不同的长度呢?如果在不同的路线上有足够的排列,你能为每条边计算一个合适的平均值(或其他说明性的度量)吗?对可用数据集的某些排列进行折扣将如何影响计算的准确性?
最后,如果你有一组关于权重的初始猜测,并且必须使用给定的行走来细化这些猜测呢?这会提高你的猜测能力吗?你如何应用这些额外的信息?

编辑:关于普通线性代数方法的困难的澄清。考虑以下一组行走:

a = 5
b = 4
b + c = 5
a + b + c = 8

有这些值的矩阵方程是不可解的,但我们仍然想估计这些项。可能有一些有用的初始数据可用,例如在场景3中,并且在任何情况下,我们都可以应用真实世界的知识-例如任务的长度不能是负数。我想知道你们是否有办法确保我们得到合理的估计,我们也知道我们不知道的东西——例如,当没有足够的数据来区分a和b的时候。

3 回复 | 直到 16 年前

Aryabhatta Aryabhatta 16 年前

似乎是线性代数的应用。

你需要解一组线性方程组。变量是任务的长度(或边权重)。

例如,如果3个任务的任务长度为t1、t2、t3。

你被给予

t1 + t2 = 2  (task 1 and 2 take 2 hours)

t1 + t2 + t3 = 7 (all 3 tasks take 7 hours)

t2 + t3 = 6   (tasks 2 and 3 take 6 hours)

t1 = 1, t2 = 1, t3 = 5 .

http://en.wikipedia.org/wiki/Gaussian_elimination )要解决这些问题,它会告诉你是否有唯一的解决方案,没有解决方案或无限多的解决方案(没有其他可能性是可能的)。

如果发现线性方程组没有解,可以尝试向矩阵的某些任务权重/系数中添加一个非常小的随机数,然后再次尝试求解(我相信他会被 Perturbation Theory

或者,您可以尝试在每次行走中引入一些“松弛”任务(即添加更多变量),并尝试在松弛任务满足某些线性约束(如0<<0.0001并最小化s_i)之和,使用 Linear Programming

TaslemGuy 16 年前

w是所有行走的列表,形式为0、a、b、c、d、e等(0将在后面解释)

i=1

将w[2]替换为长度w[i],减去w中的所有其他值。

例子:

0,a,b,c,d,e 50

0,c,e 10

所以:

a是第一个。将“a”的所有实例替换为50、-b、-c、-d、-e。

新数据:

50, 50

0,c,e 10

ZXX 16 年前

我忘记了图形,把任务列表当作向量——每个任务都表示为一个组件,其值等于它的成本(在本例中是完成时间)。

在任务中,最初的顺序是不同的,如果领域知识告诉你成本的比率会受到顺序/时间的同步影响,那么就可以使用领域知识将它们变成一个cannonic形式并分配乘数。时间安排是隐含的初始顺序,但你可能需要把时间作为调整因素的函数(比如午餐时间开车和午夜开车)。函数可能是表格/离散的。一般来说,评估比率和相对偏差总是容易得多。你可能需要一种函数语言来反复重写你的向量,直到没有更多的知识和规则可以改变。

当你达到最小的不可约状态-没有更多的差异-所有向量都有相同的剩余任务,然后你可以做一些基本的统计,如方差,均值,中位数和寻找大的离群值和方法,以改善初始领域知识为基础的估计,导致cannonical形式。如果你发现了很多,并且能推断出新的规则,那么就接受它们,从头开始整个过程。

是的,这要花很多钱:-)