Von 2-opt auf 3-opt ändern < Matlab < Mathe-Software < Mathe < Vorhilfe
|
| Aufgabe | Ich habe das 2 Opt-verfahren programmiert (nachbarschaftssuche) in matlab wo 2 kanten gelöscht werden und neu verbunden werden.
jetzt weiß ich nicht wie ich das 3-opt-verfahren daraus basteln kann. was muss noch zusätzlich geändert werden damit er das 3-opt-verfahren ausführt (nachbarschaftssuche)?
hier der code für das 2-opt-verfahren mit kommentaren:
function erg2=zwei_opt(Route1) % auf eine Route wird das 2-opt-Verfahren angewendet, um alle Nachbarn zu ermitteln
R1 = Route1(1,:);
erg2 =[];
zwischenR =[]; % Zwischenspeicher wird erstellt
[n,m] = size(R1);
for i=2:m-2 % in dieser for-Schleife wird das 2-opt-Verfahren ausgeführt
for j=i+1:m-1
zwischenR = R1;
zwischenR(i:j) = R1(j:-1:i);
erg2 =[erg2; zwischenR]; % Ergebnismatrix wird um eine Zeile erweitert
end
end
erg2=loescheDoppelteEintraege(erg2); % Funktion löscht doppelte Rundreisen
erg2=Spiegelung(erg2); % Funktion löscht Spiegelungen
anzahl2=size(erg2,1) % Anzahl der Nachbarn werden ausgegeben
end
function A=loescheDoppelteEintraege(x)
gr=size(x);
A=[];
for i=1:gr(1)
if ~isnan(x(i,:))
A=[A;x(i,:)];
for j=i+1:gr(1)
if x(j,:)==x(i,:)
x(j,:)=NaN;
end
end
end
end
end
function C=Spiegelung(x)
gr=size(x);
C=[];
for i=1:gr(1)
if ~isnan(x(i,:))
C=[C;x(i,:)];
for j=i+1:gr(1)
if fliplr(x(j,:))==x(i,:)
x(j,:)=NaN;
end
end
end
end
end
function erg=loescheAUSGANGSROUTE(x,R)
erg=x;
gr=size(x);
R1=R;
gr=size(erg);
for i=1:gr(1)
if erg(i,:)==R1;
erg(i,:)=[];
break;
end
end
end
danke schon mal im vorraus! |
Kann jmd den Code so umändern dass es das 3opt verfahren auf nachbarn prüft?
ich habe bereits diese frage in dem forum gestellt jedoch noch keine antwort erhalten http://matheplanet.com/
nur für erstposter:
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:10 Sa 26.07.2014 | | Autor: | Diophant |
Hallo,
> ich habe bereits diese frage in dem forum gestellt jedoch
> noch keine antwort erhalten http://matheplanet.com/
ja, und zwar heute Nacht um 2:00. Für eine solche Frage erscheint mir das ein wenig ungeduldig zu sein. Immerhin hast du es angegeben, das ist ok. Aber anstatt dieser Bitte
> Kann jmd den Code so umändern dass es das 3opt verfahren auf nachbarn prüft?
wäre es im Sinne unseres Forums besser gewesen, erst einmal eigene Ideen zu entwickeln und diese dann in deine Frage mit einfließen zu lassen.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:52 Sa 26.07.2014 | | Autor: | kostja007 |
also der code muss ja nur da geändert wo steht "hier wird das 2-opt-verfahren durchgeführt". folgende gedanken habe ich mir da gemacht:
beim 2-opt werden die kanten einer rundreise (v,w) und (x,y) gelöscht und neu verbunden nähmlich (v,x) (w,y). Im gegensatz zum 3 opt dort werden 3 kanten gelöscht:
[(u,v), (w,x), (y,z)]
so werden sie nun neu verbunden:
[(u,w), (v,x), (y,z)]; [(u,v)(w,y)(x,z)];[(u,y)(w,x)(v,z)] (das sind unechte 3opt-schritte.)
Dazu kommen die echten 3optschritte
[(u,x)(y,w)(v,z)]; [(u,y)(x,v)(w,z)]; [(u,x)(y,v)(w,z)]; [(u,w)(v,y)(x,z)]
dies ist die möglichkeit für jeweils einmal 3 kanten löschen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Di 29.07.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
