给定图形中的散步列表确定边缘权重

这些问题涉及一组数据，其中包含连续执行的任务列表以及完成它们所需的总时间。我一直在想，是否可以根据适当的领域知识来确定有关任务长度的有用信息，或者是根据它们的初始猜测值进行确定。我认为图论是解决这个问题的方法，并且对这些东西有一个体面的基本把握，但我无法确定我是否在正确的轨道上。此外，我认为这是一个非常有趣的问题。所以在这里，我们去：给定图形中的散步列表确定边缘权重

是否有可能确定在向加权图边的权重，给散步的与说走长度（相加加权）以图形列表？我认识到，步行路线上排列的数量和质量将决定任何可能答案的质量，但我们假设所有可能的散步和长度都是给定的。如果一个确定的答案是不可能的，什么样的东西可以关于图的结论？你会如何得出这些结论？
如果有几条类似的步行可能会有不同的长度，该怎么办？你可以计算一个体面的平均值（或其他说明性措施）的每个边缘，给予不同的路线采取足够的排列？如何从可用数据集中减少一些排列会影响计算的准确性？
最后，如果你有一组关于权重的初步猜测，并且必须使用给定的步骤来完善这些猜测呢？这会提高你的猜测能力，你怎么能应用额外的信息？

编辑：澄清明确的线性代数方法的困难。考虑以下设置步行道：

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

与这些值的矩阵方程是不可解的，但我们仍想估计条款。可能会有一些有用的初始数据可用，如情景3，并且无论如何我们都可以应用真实世界的知识 - 例如任务的长度不能为负数。我想知道你是否有如何确保我们得到合理估计的想法，并且我们也知道我们不知道的 - 例如。当没有足够的数据来告诉b。

来源

2010-08-03 Ezku

看起来像线性代数的应用。

您有一组需要解决的线性方程。变量是任务的长度（或边权重）。

例如，如果任务长度为t1，t2，t3 3个任务。

而且您将得到

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 < S_I < 0.0001最小化s_i的总和），使用Linear Programming技术。

来源

2010-08-03 22:41:31

请原谅延迟评论此。是的，你是正确的，直接的线性代数是一种方法，但只适用于第一个，最天真的场景，并留下牛肉，场景二和三完全无人看管。这实际上是我提出的第一个解决方案，但迅速认识到这种方法的垮台使我陷入了死胡同 - 我想避免引导任何其他答案。然而，看到缺乏答案，我很快就会加上赌注。 – Ezku 2010-08-09 19:15:14

@Ezku：＃2和＃3中的问题并不十分清楚。例如，为什么线性代数方法在那里不起作用，这完全不清楚。你在谈论什么'衰落'？也许这将有助于进一步澄清问题。也许一些例子也会有所帮助。 – 2010-08-09 20:14:41

@Ezku：根据您对问题的编辑添加了一段答案。 – 2010-08-11 14:52:06

假设您有无限数量的任意字符来表示每条边。（a，b，c，d等）

w是0，a，b，c，d，e等形式的所有漫步的列表（0将在后面解释）

I = 1

如果#W [I]〜= 1然后

替换W [2]与w的长度[I]中，减去在瓦特所有其它值。

永远重复。

实施例：

0，A，B，C，d，E 50

0，A，C，B，E 20

0，C，E 10

所以：

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

新数据：

50,50

50，-b，-d，20

0，C，E 10

并且，重复，直到一个值是左，你完成了！或者，第一个数字可以简单地从每个步行的长度中减去。

来源

2010-08-09 19:52:35 TaslemGuy

我忘了图表和治疗任务的列表作为载体 - 表示为组件的每个任务与价值等于它的成本（时间在这种情况下，完成

在任务在不同orderes最初，如果领域知识告诉你，成本比率将受订单/计时的相当大程度影响，那么这就是在哪里使用领域知识将它们变为一种无用的形式并分配乘数时间是隐含的初始排序，但您可能必须做出时间函数只是为了调整因素（例如午餐时间和午夜时分驾驶）功能可能是表格式/离散式的，一般来说，评估比率和相对偏差总是容易得多（做某事的人很多），您可能需要一种功能性语言来重复d重写你的载体，直到没有更多的罗曼知识和规则可以改变。

随着cannonical矢量考虑只是存在和不存在的任务（这个iteratioon只是0 | 1）并寻找最小差异 - 单个任务差异优先 - 这将提供估计哪些少量的变量。继续递归地做这件事，准备好回溯并且对迄今为止的估计的好坏或质量有一个启发式的规则。跟踪你回溯的良好“回合”。

当您达到最小不可约状态时 - 不会有更多差异 - 所有向量具有相同的剩余任务，那么您可以执行一些基本统计数据，如方差，均值，中位数，寻找大异常值以及改进初始域的方法基于知识的估计会导致非正式的形式。如果你对他们很多并能推断出新规则，那就把他们带入并从头开始整个过程。

是的，这可以花费很多:-)

来源

2010-08-14 04:42:53 ZXX

给定图形中的散步列表确定边缘权重

回答

相关问题