Ich arbeite zur Zeit an einem Algorithmus, der u.A. sehr oft eine Graphensuche aufrufen muss. Eingelesen wird eine Adjazenzmatrix (logical, sparse) und ein Anfangsknoten, herauskommen soll der Untergraph, der von dem Knoten aus erreichbar ist.
Momentan sieht das Programm so aus:
ifany(find((Adj_in(current,:))))% gehe nur in die Schleife, wenn überhaupt ein Knoten erreichbar ist while ~isempty(current)% so lange es Randknoten in der Liste gibt [a,b]=find(Adj_in(current,:));
iflength(a)>1% hat ein Knoten mehr als einen Nachfolger, ist der resultierende Subgraph kein Pfad
d=false;
end ifany(a)% wenn es Nachfolger von Randknoten gibt for i=1:length(a)
Adj_out(current(a(i)),b(i))=1; % Kante eintragen end
current=setdiff(b,total); % Randknoten anpassen
total=union(total,b); % Liste der erreichbaren Knoten erweitern else
current=[]; % gibts keine Nachfolger, bricht der Algorithmus ab end end else return end
extrem viel Zeit beansprucht, da die Variable current ja immer größer wird. Wenn ich das Suchen von Nachfolgern in eine Schleife packe, dauert es noch länger. Wie kann ich den Algorithmus beschleunigen?
Vielen Dank für eure Antworten!
Gruß Timo
Einstellungen und Berechtigungen
Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
RSS