Verfasst am: 01.12.2009, 20:39
Titel: kürzeste Gesamtstrecke zwischen Punkten
Hallo,
ich habe mir eine neue Funktion vorgenommen, die ich in Matlab programmieren will.
Es geht um folgendes Problem:
Man hat beliebig viele Punkte (in meiner Funktion erst mal nur 5) die man abfahren will. Dazu gibt es n! Möglichkeiten. Die Funktion soll einem die Möglichkeit mit der kürzeste Gesamtstrecke zwischen den Punkten ausgeben, wobei der Anfangspunkt egal ist.
Die Vektoren werden in eine Matrix eingelesen.
Dann werden die Vektoren vom Vektor i zu den übrigen Vektoren berechnet und in einen Array B{i} geschrieben.
Als nächstes werden die Beträge der Vektoren gebildet und in einen Array D{i} geschrieben. Nun werden durch mehrere For-Schleifen alle möglichen Abfahrmöglichkeiten der Punkte gebildet.
Am Ende soll dann der maximale Wert aus der Matrix mit den Gesamtstrecken ausgelesen und zurückgegeben werde.
Das ist in meinem Code noch nicht zu finden, was daran liegt, dass ich ein Problem habe.
Bis zum Array D{i} mit den Beträgen läuft alles gut, doch dann bekomm ich bei der Ermittlung der Gesamtwege folgende Fehlermeldung:
??? Bad cell reference operation.
Error in ==> weg at 34
weg=weg+D{j}(1,k);
Kann mir jemand sagen was damit gemeint ist?
Hab dazu gegoogelt aber bin nicht wirklich schlau daraus geworden.
Ich bedanke mich schon mal,
Also ich weiß, dass der Befehl bedeutet, dass ich mich auf ein nicht existentes Element des Arrays beziehe, aber ich weiß nicht warum das so ist, der Aray hat 5 Spalten und die Schleifen gehen auch nur bis 5.
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 03.12.2009, 00:37
Titel:
Hmmm hört sich für meinen geschmack nach dem "travelling salesman" problem an. ACHTUNG: dies is für den allgemeinen fall (das heisst n-> inf # Städte) NICHT lösbar, weil die Rechenzeit exponentiell steigt!!!!
Such doch mal in Google nach "travelling Salesman problem" es gibt je nach Problem(-stellung) einigermassen effiziente Algorithmen die auch grosse Probleme in vernünftiger Zeit lösen.
Ja ich hab nen Freund der Informatiker ist (und dummerweise keinen Plan von Matlab hat), der hat gesagt ich sollte mal versuchen das zu programmieren. Er hat mich auch drauf hingewiese, dass das Programm wegen der n! ne imense laufzeit für hohe n's bekommt. Aber genau das wollte ich mal austesten.
Mein Problem liegt jetzt aber eher genau in dem angezeigten Fehler, weniger in dem Programm.
Mir geht es mehr darum, dass der Debugger sagt, ich finde das Element in der Matrix bzw dem Array nicht. Irgendwie muss er sich auf was beziehen, was nicht da ist, aber ich habs schon sehr oft mit dem Kulli durchexerziert und bin nicht auf das Problem gestoßen, muss also eher was syntaxmäßiges sein als denktechnisch.
Mir ist klar, dass du damit meinst, dass j die Werte von 1 bis p-1 und dann p+1 bis m nehmen soll. MATLAB interpretiert das aber anders und liefert logische 0 und 1, wodurch es dann zu Problemen kommt.
Danke für den Hinweis.
Prinzipiell ist das die Lösung des Problems.
Ich kann bei setdiff aber nur einen Wert eigeben, der nicht in der ersten Menge sein soll. Die Lösung dazu wäre die einzelnen Zählparamter in eine Menge zu setzen, doch leider klappt das auch nicht, ich bekomme nämlich 5^5 ergbnisse. Das heißt, dass wirklich alle Kombinationen mit zurücklegen und reihenfolge ausgegeben werden, was ich ja eigentlich durch das setdiff aussschließen wollte.
So sieht jetzt meine Idee aus, aber wie gesagt, sie läuft nicht.
Code:
p=[];
r=[];
k=[];
l=[];
o=[];
E=[];
F=[p;r;k;l;o]
for p=1:m %Kombination aller möglichen
%Wege zwischen den Punkten
for r =setdiff(1:m,F)
weg=D{p}(1,r);
for o=setdiff(1:m,F)
gesamtweg=weg+D{l}(1,o);
E=[E;gesamtweg]; %Auflistung aller Gesamtwege in Matrix
end end end end end
strecke=E;
elsedisp('Nur 2 oder 3 dimensionale Vektoren');
end
So, Entschuldigung, hatte ein Brett vorm Kopf, wenn nicht sogar zwei.
Also die Funktion läuft jetzt endlich wie es soll, es kommen 120 Ergebnisse (5!) raus, und am Ende wird das Minimum bestimmt.
Viele Dank für die Hilfe.
So wie es jetzt geschrieben ist geht es erst für 5 Punkte, ich könnte ja mal versuchen das auf n Punkte umzuschreiben.
Aber was ich gerade gemerkt habe ist, dass ich noch nciht genügend mit der Matlab-Syntax klar komme, bzw zu wenige Befehle drauf habe.
Vielleicht sollte ich erst mal etwas mehr lesen bevor ich weiter programmiere.
Obwohl mein Informatik-Kollege mir immer den äußerst intelligenten Satz sagt, "Programmieren lernt man nur durch Programmieren" =)
Was würdet ihr mir raten, wenn ihr meine Programmierkünste anschaut?
Hier der Quellcode der laufenden Funktion, leider gibt er nur maxstrecke eaus, nicht minstrecke, was mir auch rätselhaft ist:
for o=setdiff(1:m,[p,r,k,l])
gesamtweg=weg+D{l}(1,o);
E=[E;gesamtweg]; %Auflistung aller Gesamtwege in Matrix
end end end end end
minstrecke=min(E);
maxstrecke=max(E);
elsedisp('Nur 2 oder 3 dimensionale Vektoren');
end
Was würdet ihr mir raten, wenn ihr meine Programmierkünste anschaut?
MATLAB ist array-/ matrixbasiert. Das sollte man nutzen. Bei vier oder mehr ineinander geschachtelten for-Schleifen sollte man sich überlegen, ob das nicht besser hinzubekommen ist. Hier ein Vorschlag:
Die Funktion PERMS verwenden und dann die Kombinationen aus den Zeilen herausziehen. Das geht allerdings nur, wenn brute force (alle Kombinationen ausprobieren) noch sinnvoll ist.
Du kannst dir ja auch die Implementation davon in der MATLAB-Demo TRAVEL ansehen.
Hmm, ok, das werde ich mir auf jeden Fall mal anschauen.
Mein Informatikkollege hat auch über die 5 verschachtelten for-schleifen gemeckert. Das echte Problem ist ja auch dann erst da wenn ich n for-schleifen haben will. Er hat mir gesagt, er würde das über Rekursion machen und mit irgend einem "Deijsler-Algorithmus" von dem ich noch nie was gehört habe, hab ihn denke ich auch falsch geschrieben.
Aber werde erst mal die Funktion PERMS nachsehen.
Ich habe in meinem Programm doch zwei Rückgabeargumente oder nicht?
Im Programm ja, aber nicht im Aufruf des Programms. Dieser muss wie in meinem Beispiel vom Command Window aus erfolgen.
Wenn du das Problem momentan nur zur Übung machst, würde ich mir da über die optimale Umsetzung keine zu großen Gedanken machen.
Grüße,
Harald
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