0

那么这个问题更多的是关于一种有效的算法而不是实现，所以我不会发布代码。（不会真正帮助您理解问题）

向您介绍这个问题：我正在开发一个程序来计算 automovilistics 崩溃报告。它为您提供了一系列“方程式”（Eq从现在开始，Eqs 表示复数），您可以在其中输入数据并通常得到 n 个结果。

例如：您选择覆盖的空间（x），并输入时间（t），加速度（a）和初始速度（v），然后x =（a * t）+（（a * t ^ 2）/ 2）。问题是这个 Eqs 在一个对象内部，其中包含比 vars 和 ecuation 本身更多的东西，让我们称之为Bo（我正在谈论的 busssines 对象。

所以 BO 相当大（并且需要），除其他外，1 Bo 可以有 N 个 Eqs，并且不止一个结果，此外，每个 Eq 都可以将值范围作为输入，这会让你康复。 . （假设您只能在 2 个变量上使用范围，实际上这不受限制）因此您将获得每个结果的结果表（一些 Bos 有 4 个不同的结果）。范围的步数有上限，第一个范围为 20 个，第二个范围为 10 个。（在一个有 4 个结果的 Bo 中，将映射到 1 个 Bo 的 800 个结果）。

顺便说一句，我必须将这个 Bos 及其各自的结果存储（保存在文件中），并且 Var 输入每次都无法在运行时计算它们（我可以只保存 ecuation 和 var 输入并计算每次我的结果需要他们），因为博斯可以改变他们的评价，而用户需要保留以前的结果，不要问..

此外，您可以将 Bo 的一个结果导入另一个 Bo 的 Eq 输入。所以在前面的例子中（我们称之为 Bo1）加速度可能来自另一个计算它的 Bo (Bo2)，并采用其他参数来计算它，如果你改变 Bo2 的输入，结果会改变，所以至少 1 Bo1 的 var 会发生变化，从而使 Bo1 的结果发生变化。这可以级联（B2 从 B3 导入等等）。一个 Bo 可以从其他 N 个 Bos 导入其所有 N 个变量。

我不能使用指针或引用类型（也许可以使用引用类型，无论如何这将是很多工作，必须处理来自不同用户的先前保存的数据，以及对象缺少引用等）。

我决定只使用数组的集合，在每个数组中存储，{Id_of_Bo_Exporting, Id_Bo_importing,Id_Variable_of_Bo_Importing,..(ohters ids to map the especific result exporting)} 数组是 int 的（对于前 2 个来说很长）。

我真的不喜欢它，但代码工作得很好。（感谢阅读）问题即将到来，我保证。

问题是，我必须检查循环进口，如果 B3 从 B2 进口和 B2 从 B1 进口，我不应该允许从 B3（或 B2）进口 Bo1。这将导致无限循环，（我可以停止循环，但从数学角度来看，这不是允许导入的逻辑）。

和进口清单，最终可能真的很长，

我想到了一个 ArrayList< ArrayList< long>> 所以每次我添加一个导入时，我都会在这个我不喜欢的“东西”上添加 Id。(arraylist的arraylist)

每个长数组将在第一个位置具有“Bo id 标头”，并且每次 Bo 导入时，新 Id 都会添加到其列表中，并且每个其他 Bo 都会导入 Bo（进行导入的那个）。

因此，如果我的用户尝试从 B1 制作 B9，该方法将检测到，B1 被添加到自己的列表中并且不允许。

实施很容易。（让我们使用 java，不，我使用的是 .net，我自己没有启动项目）

例子 {{}}

B1 从 B2 导入：{ {B1,B2} }

B1 从 B6 导入：{{B1,B2, B6 }}

B2 从 B4 导入： {{B1,B2,B6, B4 }, {B2,B4} }

B4 从 B9 导入： {{B1,B2,B3,B4, B9 },{B2,B4, B9 }, {B4,B9 }}

B3 从 B10 导入： {{B1,B2,B3,B4,B9, B10 },{B2,B4,B9},{B4,B9}, {B3,B10} }

每个长数组将在第一个位置具有“Bo id 标头”，并且每次 Bo 导入时，新 Id 都会添加到其列表中，并且每个其他 Bo 都会导入 Bo（进行导入的那个）。

因此，如果我的用户尝试从 B1 制作 B9，该方法将检测到，B1 被添加到自己的列表中并且不允许。

实施很容易。（让我们使用 java，不，我使用的是 .net，我自己没有启动项目）

private boolean checkCircularity(long ida,long idb){
//ida importing, idb exporting
// asume List is public and called iL
// Clone il to restore it in case}
for (int i = 0 ; i < iL.size() ;i++)  
    // Each arraylist of long in the big array iL
{    
    // I would use some kind of SetUniqueList, dont know in c#
    // but i could check it if needed and add it if it doesnt exist
    if (iL.get(i).contains(ida))
    {
        if (((iL.get(i)).get(0)) == idb)
        {// Circiut, breaks for's restore the original list and returns false
        }
        else{
            if (!iL.get(i).contains(idb)) {iL.get(i).add(idb);}
        }
    }
}       return true;    }

现在的问题（使用 ListSet 或其他什么）你能想出一种更有效的方法来做到这一点吗？两个列表（导入和 iL 可以很快变大，具体取决于用户）。字幕是速度。

4

1 回答 1

0

如果我正确理解了这个问题，那么您对“循环”的检查实际上是图中循环检测的一个示例。换句话说，如果每个“导入”都被建模为有向图边，那么您正在尝试检测一个循环。

如果这是正确的，那么这是一个很好理解的问题。我建议将您的导入建模为直接节点引用，然后使用一种标准算法来检测循环，请参阅循环检测。

于 2015-01-28T07:49:06.377 回答