WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

 
Gast > Registrieren       Autologin?   

Partner:




Forum
      Option
[Erweitert]
  • Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

kürzeste Gesamtstrecke zwischen Punkten

 

jamesbizarre
Forum-Anfänger

Forum-Anfänger


Beiträge: 30
Anmeldedatum: 27.11.09
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 01.12.2009, 20:39     Titel: kürzeste Gesamtstrecke zwischen Punkten
  Antworten mit Zitat      
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,

Gruß
Frank

Hier die Funktion:


Code:
function strecke=weg(a,b,c,d,e)

A=[a,b,c,d,e]; %Zusammenfassen der Zeilenvektoren in eine Matrix
[n,m]=size(A); %Einlesen der Matrixdimensionen

if n==2 || n==3 %Abfrage nach ob Dimension korrekt ist
   
    for i=1:m  
        j=1;
        B{i}=(A(:,i)-A(:,j));  %Vektor A - Vektor B = Vektor BA
                               %als erstes Element des Arrays B{i}
       
        for j=2:m
            C=(A(:,i)-A(:,j));  %Anheften der weiteren Elemente
            B{i}=[B{i},(C)];
        end
    end
       
        for q=1:m
            for r=1:m
                s=norm(B{q}(:,r));%Berechnen der Vektorbeträge
                D{q}(1,r)=s;      %und Ordnen in ein neues Feld
            end
        end
 
   
    E=[];
       
        for p=1:m                        %Kombination aller möglichen
                                         %Wege zwischen den Punkten
            for j=1:m ~=p
                weg= weg + D{p}(1,j);
               
                for k=1:m ~=(p|j)
                    weg=weg+D{j}(1,k);                        
                   
                    for l=1:m ~=(p|j|k)
                        weg=weg+D{k}(1,l);
                           
                        for o=1:m ~=(p|j|k|l)
                            weg=weg+D{l}(1,o);
                            E=[E;weg]; %Auflistung aller Gesamtwege in Matrix
                        end
                    end
                end  
            end
        end    
   
else disp('Nur 2 oder 3 dimensionale Vektoren');
end

return
   
 
[/quote]
Private Nachricht senden Benutzer-Profile anzeigen


jamesbizarre
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 30
Anmeldedatum: 27.11.09
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 02.12.2009, 18:38     Titel:
  Antworten mit Zitat      
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.
Private Nachricht senden Benutzer-Profile anzeigen
 
Gast



Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 03.12.2009, 00:37     Titel:
  Antworten mit Zitat      
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.

Gruss
 
jamesbizarre
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 30
Anmeldedatum: 27.11.09
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 05.12.2009, 16:34     Titel:
  Antworten mit Zitat      
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.
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.501
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 05.12.2009, 18:28     Titel:
  Antworten mit Zitat      
Hallo,

die for-Schleifen sind so nicht sinnvoll, z.B.
Code:


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.

Richtig wäre
Code:


Natürlich muss jede der ähnlichen for-Schleifen entsprechend umgeschrieben werden.

Grüße,
Harald
Private Nachricht senden Benutzer-Profile anzeigen
 
jamesbizarre
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 30
Anmeldedatum: 27.11.09
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 07.12.2009, 13:35     Titel:
  Antworten mit Zitat      
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 k=setdiff(1:m,F)
                    weg=weg+D{r}(1,k);                        
                   
                    for l=setdiff(1:m,F)
                        weg=weg+D{k}(1,l);
                           
                        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;
else disp('Nur 2 oder 3 dimensionale Vektoren');
end

return
 
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.501
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 07.12.2009, 15:17     Titel:
  Antworten mit Zitat      
Hallo,

vielleicht sollten wir versuchen, das ganze auf ein einfacheres Beispiel runterzubrechen. Was du meiner Ansicht nach brauchst, ist sowas wie

Code:


Bei mir liefert das - wie erwartet - 1 3 5.
So wie ich das sehe, ist das genau das, was du brauchst.

Falls es das nicht ist: was brauchst du?
Falls du anderen Output bekommst: welche MATLAB-Version hast du?

Grüße,
Harald
Private Nachricht senden Benutzer-Profile anzeigen
 
jamesbizarre
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 30
Anmeldedatum: 27.11.09
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 07.12.2009, 16:21     Titel:
  Antworten mit Zitat      
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:

Code:
function [maxstrecke , minstrecke]=weg(a,b,c,d,e)

A=[a,b,c,d,e]; %Zusammenfassen der Zeilenvektoren in eine Matrix
[n,m]=size(A); %Einlesen der Matrixdimensionen

if n==2 || n==3 %Abfrage nach ob Dimension korrekt ist
   
    for i=1:m  
        j=1;
        B{i}=(A(:,i)-A(:,j));  %Vektor A - Vektor B = Vektor BA
                               %als erstes Element des Arrays B{i}
       
        for j=2:m
            C=(A(:,i)-A(:,j));  %Anheften der weiteren Elemente
            B{i}=[B{i},(C)];
        end
    end
       
        for q=1:m
            for r=1:m
                s=norm(B{q}(:,r));%Berechnen der Vektorbeträge
                D{q}(1,r)=s;      %und Ordnen in ein neues Feld
            end
        end
 
   E=[];
       
        for p=1:m                       %Kombination aller möglichen
                                        %Wege zwischen den Punkten
            for r = setdiff(1:m,p)
                weg=D{p}(1,r);
               
               
               
                for k= setdiff(1:m,[p,r])
                    weg=weg+D{r}(1,k);                        
                   
                    for l=setdiff(1:m,[p,r,k])
                        weg=weg+D{k}(1,l);
                           
                        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);
else disp('Nur 2 oder 3 dimensionale Vektoren');
end

return
 
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.501
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 07.12.2009, 17:32     Titel:
  Antworten mit Zitat      
Hallo,

Zitat:
Hier der Quellcode der laufenden Funktion, leider gibt er nur maxstrecke eaus, nicht minstrecke, was mir auch rätselhaft ist:


Der Aufruf muss mit zwei Rückgabeargumenten erfolgen:
Code:
[maxdist, mindist] = weg(1,2,3,4,5)


Zitat:
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.

Grüße,
Harald
Private Nachricht senden Benutzer-Profile anzeigen
 
jamesbizarre
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 30
Anmeldedatum: 27.11.09
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 08.12.2009, 17:06     Titel:
  Antworten mit Zitat      
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?


Code:
function [maxstrecke , minstrecke]=weg(a,b,c,d,e)
 


Danke für die Hilfe!
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.501
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 08.12.2009, 17:13     Titel:
  Antworten mit Zitat      
Hallo,

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
Private Nachricht senden Benutzer-Profile anzeigen
 
Neues Thema eröffnen Neue Antwort erstellen



Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:

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
.





 Impressum  | Nutzungsbedingungen  | Datenschutz | FAQ | goMatlab RSS Button RSS

Hosted by:


Copyright © 2007 - 2025 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

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.