language-agnostic - 给定图中的游走列表确定边权重

Question

这些问题涉及一组数据，其中包含连续执行的任务列表以及完成这些任务所需的总时间。我一直想知道是否有可能确定有关任务长度的有用信息，无论是按原样还是基于适当的领域知识进行一些初步猜测。我开始认为图论将是抽象地解决这个问题的方法，并且对这些东西有一个不错的基本掌握，但我无法确定我是否在正确的轨道上。此外，我认为这是一个非常有趣的问题。所以我们开始:

是否有可能确定有向加权图中边的权重，给定该图中的游走列表以及所述游走的长度(总权重)？我承认步行路线上排列的数量和质量将决定任何可能答案的质量，但让我们假设所有可能的步行及其长度都已给出。如果不可能有明确的答案，可以通过图表得出什么样的结论？你将如何得出这些结论？

如果给定的长度可能不同的几个类似的步行怎么办？考虑到不同路线上的足够排列，您能否为每条边计算一个合适的平均值(或其他说明性的度量)？从可用数据集中打折一些排列将如何影响计算的准确性？

最后，如果您对权重有一组初始猜测，并且必须使用给定的游走来改进那些呢？这会提高你的猜测能力吗，你如何应用额外的信息？

编辑:澄清简单线性代数方法的困难。考虑以下一组步行:

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

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

Answer 1

似乎是线性代数的应用。

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

例如，如果 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 < s_i < 0.0001 并最小化 s_i 的总和)的新方程选择解)，使用 Linear Programming技巧。