图/树表示和递归

Question

我目前正在用MATLAB编写一个优化算法，我在这方面做得非常糟糕，因此我真的需要你的帮助。我真的在努力寻找一种表示图的好方法(或者更像是一棵有几个根的树)，它或多或少看起来像这样：

alt text http://img100.imageshack.us/img100/3232/graphe.png

基本上11/12/13是我们的根(阶段0)，2x是stage1，3x stage2和4x stage3。正如您所看到的，来自stageX的节点只连接到来自stage(X+1)的几个节点(因此它们不必连接到所有节点)。

重要提示:每个节点必须包含多个值(至少3-4个)，其中一个是它的编号，至少还有两个其他变量(用于优化决策)。

我确实有一个使用矩阵的简单表示，但它真的很难维护，所以我想知道有没有好的方法来做它？

第二个问题:当我完成这个表示时，我需要计算每条路径(从根到尾)的好坏(比如，我需要比较的是11-21-31-41是最好的，或者是11-21-31-42更好)，为此，我将使用每个节点持有的变量。但是这些值必须进行递归计算，假设我们从11开始，但要计算11- 21 -31-41有多好，我们首先需要转到41，进行一些计算，转到31，进行一些计算，转到21进行一些计算，然后我们可以使用之前的所有计算来计算11。与11-21-31-42相同(我们从42开始，然后是31->21->11)。我需要检查所有可能的路线。这里有一个问题，如何做到这一点？也许是BFS/DFS？但我不太确定如何存储所有的结果。

这些都是一些冗长的问题，但我希望我没有要求你做我的家庭作业(因为我得到了所有的算法，只是因为我不太擅长matlab，而且我的老师不让我用java做)。

Answer 1

诚然，这可能不是最有效的解决方案，但如果您可以访问Matlab 2008+，则可以定义一个节点类来表示您的图形。

Matlab documentation有一个关于链表的很好的示例，您可以将其用作模板。

基本上，一个节点将有一个属性'linksTo'，它指向它所链接的节点的索引，以及一个计算每个链接的成本的方法(可能还有一些描述每个链接的附加属性)。然后，您所需要的是一个向下移动每个链接的函数，并在它向上移动时带来成本。