圖/樹表示和遞歸

Question

我目前正在寫在MATLAB的優化算法，在這我完全吸，所以我真的需要你的幫助。我真的在努力尋找代表圖（或好更像是幾個根樹），這看起來或多或少像這樣的一個好辦法：

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

基本上11/12/13是我們的根（第0階段），2x是第1階段，第3階段2和第4階段3。正如你可以看到stageX的節點只連接到來自stage（X + 1）的幾個節點（所以它們不必連接到它們的所有節點）。

重要的：每個節點都具有保持多個值（至少3-4），一將它的數量和至少兩個其它的變量（其將被用來優化的決定）。

我有使用矩陣的簡單表示，但它真的很難維持，所以我想知道有沒有做到這一點的好辦法？

第二個問題：當我與我的表示需要計算每條路線（從根部到末端）有多好（比如假設我需要比較做的是11-21-31-41最好還是是更好的11-21-31-42），我會使用每個節點所擁有的變量。但值必須遞歸地計算，假設我們從11開始，但是要計算出我們首先需要去41的好處，做一些計算，到31，做一些計算，去到21做一些計算，然後我們可以使用所有以前的計算來計算11。與11-21-31-42相同（我們從42開始，然後31-> 21-> 11）。我需要檢查所有可能的路線。這就是問題，怎麼做？也許是BFS/DFS？但我不太清楚如何存儲所有結果。

這些是一些冗長的問題，但我希望我不要求你做我的功課（因爲我得到了所有的算法，這只是我不擅長matlab，我的老師不會讓我在java中完成）。

Answer 1

當然，它未必是最有效的解決方案，但如果你有機會到Matlab的2008+，你可以定義一個節點類來表示你的圖表。

的Matlab documentation對鏈表，它可以作爲一個模板使用一個很好的例子。

基本上，一個節點會有一個屬性'linksTo'，它指向它所鏈接的節點的索引，以及一種計算每個鏈接成本的方法（可能帶有一些描述每個鏈接的附加屬性）。然後，你需要的是一個能夠向下移動每個鏈接的功能，並在它恢復時帶上它的成本。