Représentation de graphe/arbre et récursion

Question

Je suis en train d'écrire un algorithme d'optimisation dans MATLAB, dans lequel je suis complètement nul, donc je pourrais vraiment utiliser votre aide. Je suis vraiment du mal à trouver une bonne façon de représenter un graphique (ou bien plus comme un arbre avec plusieurs racines) qui plus ou moins regarder comme ceci:

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

Fondamentalement 11/12/13 sont nos racines (étape 0), 2x est stage1, 3x stage2 et 4x stage3. Comme vous pouvez le voir, les nœuds de stageX ne sont connectés qu'à plusieurs nœuds de l'étape (X + 1) (ils n'ont donc pas besoin d'être connectés à tous). Important: chaque nœud doit contenir plusieurs valeurs (au moins 3-4), l'un sera son numéro et au moins deux autres variables (qui seront utilisées pour optimiser les décisions).

J'ai une représentation simple en utilisant des matrices mais c'est vraiment difficile à maintenir, alors je me demandais s'il y avait une bonne façon de le faire? Deuxième question: quand j'ai fini avec cette représentation, j'ai besoin de calculer à quel point chaque route (des racines à la fin) est bonne (comme disons que je dois comparer est le meilleur ou le meilleur 11-21-31-42 mieux) pour faire cela, je vais utiliser les variables que chaque nœud détient. Mais les valeurs devront être calculées récursivement, disons que nous commençons à 11 mais pour calculer à quel point nous devons d'abord aller à 41, faire des calculs, aller à 31, faire des calculs, aller à 21 faire des calculs et ensuite nous pouvons calculer 11 en utilisant tous les calculs précédents. Même chose avec 11-21-31-42 (nous commençons par 42 puis 31-> 21-> 11). Je dois vérifier toutes les routes possibles de cette façon. Et voici la question, comment le faire? Peut-être un BFS/DFS? Mais je ne suis pas sûr de savoir comment stocker tous les résultats. Ce sont de longues questions, mais j'espère que je ne vous demande pas de faire mes devoirs (comme j'ai tous les algorithmes, c'est juste que je ne suis pas très doué en matlab et mon professeur ne me laisserait pas le faire en java).

Answer 1

Certes, ce n'est peut-être pas la solution la plus efficace, mais si vous avez accès à Matlab 2008+, vous pouvez définir une classe de nœuds pour représenter votre graphique.

Le Matlab documentation a un bel exemple sur les listes chaînées que vous pouvez utiliser comme modèle. Fondamentalement, un noeud aurait une propriété 'linksTo', qui pointe vers l'index du noeud auquel il est lié, et une méthode pour calculer le coût de chacun des liens (éventuellement avec des propriétés supplémentaires qui décrivent chaque lien). Ensuite, tout ce dont vous avez besoin est une fonction qui se déplace vers le bas de chaque lien, et apporte le coût (s) avec lui quand il remonte.