2-opc

W optymalizacji 2-opt to prosty algorytm wyszukiwania lokalnego służący do rozwiązywania problemu komiwojażera . Algorytm 2-opt został po raz pierwszy zaproponowany przez Croesa w 1958 roku, chociaż podstawowy ruch został już zasugerowany przez Flooda. Główną ideą jest wybranie trasy, która przecina samą siebie i zmianę jej kolejności, aby tego nie robiła. Pełne wyszukiwanie lokalne z 2 opcjami porówna każdą możliwą prawidłową kombinację mechanizmu wymiany. Technikę tę można zastosować do problemu komiwojażera, jak również do wielu problemów pokrewnych. Należą do nich problem trasowania pojazdów (VRP) oraz pojemnościowe VRP, które wymagają niewielkiej modyfikacji algorytmu.

Pseudo kod

Wizualnie jedna zamiana wygląda następująco:

- AB - - A - B - × ==> - CD - - C - D -

W pseudokodzie mechanizm, za pomocą którego 2-opt swap manipuluje daną trasą, jest następujący. Tutaj v1 i v2 to pierwsze wierzchołki krawędzi, które chcesz zamienić podczas przechodzenia przez trasę:

 procedura  2optSwap(route, v1, v2) { 1. weź trasę [0] do trasy [v1] i dodaj je w celu nowej_trasy 2. weź trasę [v1 + 1] do trasy [v2] i dodaj je w odwrotnej kolejności do nowa_trasa 3. weź trasę [v2+1] do trasy [początek] i dodaj je, aby nowa_trasa  zwróciła  nową_trasę; }

Oto przykład powyższego z dowolnymi danymi wejściowymi:

Przykładowa trasa: A → B → E → D → C → F → G → H → A
Przykładowe parametry: v1=1, v2=4 (zakładając, że indeks początkowy to 0)
Zawartość new_route krok po kroku:
1. (A → B)
2. A → B → (C → D → E)
3. A → B → C → D → E → (F → G → H → A)

To jest kompletna zamiana 2-opt wykorzystująca powyższy mechanizm:

 powtarzaj do momentu  braku poprawy { best_distance = calkowita odległość(istniejąca_trasa) start_again:  for  (i = 0; i <= liczba węzłów kwalifikujących się do zamiany - 1; i++) {  for  (j = i + 1; j <= liczba węzłów węzły kwalifikujące się do zamiany; j++) { nowa_trasa = 2optSwap(istniejąca_trasa, i, j) nowa_odległość = obliczDługośćCałkowita(nowa_trasa)  if  (nowa_dystans < najlepsza_dystans) { istniejąca_trasa = nowa_trasa najlepsza_dystans = nowa_dystans goto start_again } } } }

Uwaga: jeśli zaczynasz/kończysz w określonym węźle lub zajezdni, musisz usunąć to z wyszukiwania jako kwalifikującego się kandydata do zamiany, ponieważ odwrócenie kolejności spowoduje nieprawidłową ścieżkę.

Na przykład z zajezdnią w A:

A → B → C → D → A

Zamiana przy użyciu węzła [0] i węzła [2] przyniosłaby skutek

C → B → ZA → D → A

który jest nieważny (nie wyjeżdża z A, zajezdni).

Efektywna implementacja

$obliczanie$ nowej trasy może być bardzo kosztowną operacją, zwykle n $to$ liczba wierzchołków trasy Czasami można to pominąć, wykonując operację ${\ Displaystyle O (1)}$ . Ponieważ operacja 2-opt polega na usunięciu 2 krawędzi i dodaniu 2 różnych krawędzi, możemy odjąć i dodać odległości tylko tych krawędzi.

długośćDelta = - dist(trasa[v1], trasa[v1+1]) - dist(trasa[v2], trasa[v2+1]) + dist(trasa[v1+1], trasa[v2+1]) + dist(trasa[v1], trasa[v2])

Jeśli lengthDelta jest ujemna, oznaczałoby to, że nowa odległość po zamianie byłaby mniejsza. Gdy wiadomo, że lengthDelta jest ujemna, wykonujemy zamianę 2-opt. To oszczędza nam wielu obliczeń.

Również użycie tam kwadratów odległości pomaga zmniejszyć obliczenia, pomijając wywołanie funkcji pierwiastka kwadratowego. Ponieważ zależy nam tylko na porównaniu dwóch odległości, a nie dokładnej odległości, pomoże to przyspieszyć działanie. To niewiele, ale pomaga w przypadku dużych zbiorów danych, które mają miliony wierzchołków

Kod C++

 
 
 
 

  

  
  
	  

	    
		  
		  
	
	 
		  0
		  0
	

	
	      
		               
	



   
	   0
	    0     
		      
	
	 



       
	         



     
	 
	    0     
		     0 
			
		

		      
			  
		
		 
			  
		
	
	



   
	 
	    0     
		     
	
	 


  
	   
	 

	   
	   
	   
	  
		  
		    0       
			             
				                         

				
				   0 
					  
					  
					  
				
			
		
	

	 
	 0
 #include  <algorytm>  #include  <random>  #include  <stdio.h>  #include  <wektor>  using  namespace  std  ;  klasa  Punkt  {  public  :  int  x  ,  y  ;  Punkt  (  int  x  ,  int  y  )  {  this  ->  x  =  x  ;  to  ->  y  =  y  ;  }  Punkt  ()  {  to  ->  x  =  ;  to  ->  y  =  ;  }  // Odległość między dwoma punktami podniesiona do kwadratu  inline  int  dist2  (  const  Punkt  i  inne  )  const  {  return  (  x  -  inne  .  x  )  *  (  x  -  inne  .  x  )  +  (  y  -  inne  .  y  )  *  (  y  -  inne  .  y  );  }  };  // Oblicz odległość całej ścieżki (Odległości między punktami podniesione do kwadratu)  int  pathLengthSq  (  vector  <  Punkt  >  &  ścieżka  )  {  int  length  =  ;  for  (  int  i  =  ;  i  <  ścieżka  .  rozmiar  ();  i  ++  )  {  długość  +=  ścieżka  [  i  ].  dist2  (  ścieżka  [(  i  +  1  )  %  ścieżka  .  rozmiar  ()]);  }  zwracana  długość  ;  }  // Wykonaj zamianę z 2 opcjami  void  do2Opt  (  vector  <  Point  >  &  path  ,  int  i  ,  int  j  )  {  reverse  (  begin  (  path  )  +  i  +  1  ,  begin  (  path  )  +  j  +  1  );  }  // Wydrukuj ścieżkę.  void  printPath  (  string  pathName  ,  vector  <  Point  >  &  path  )  {  printf  (  "%s = ["  ,  pathName  .  c_str  ());  for  (  int  i  =  ;  i  <  ścieżka  .  rozmiar  ();  i  ++  )  {  if  (  i  %  10  ==  )  {  printf  (  "  \n  "  );  }  if  (  i  <  ścieżka  .  rozmiar  ()  -  1  )  {  printf  (  "[%3d, %3d],"  ,  ścieżka  [  i  ].  x  ,  ścieżka  [  i  ].  y  );  }  else  {  printf  (  "[%3d, %3d]"  ,  ścieżka  [  i  ]  .x  ,  ścieżka  [  i  ]  .y  );  }  }  printf  (  "  \n  ];  \n  "  );  }  // Utwórz ścieżkę o długości n z losowymi punktami z przedziału od 0 do 1000  vector  <  Point  >  createRandomPath  (  int  n  )  {  vector  <  Point  >  path  ;  for  (  int  ja  =  ;  ja  <  n  ;  ja  ++  )  {  ścieżka  .  push_back  (  Punkt  (  rand  ()  %  1000  ,  Rand  ()  %  1000  ));  }  ścieżka  powrotu  ;  }  int  main  ()  {  wektor  <  Punkt  >  ścieżka  =  utwórz Losową Ścieżkę  (  100  );  printPath  (  "ścieżka1"  ,  ścieżka  );  int  CurLength  =  pathLengthSq  (  ścieżka  );  int  n  =  ścieżka  .  rozmiar  ();  bool  znaleziona poprawa  =  true  ;  while  (  znaleziona poprawa  )  {  znaleziona poprawa  =  false  ;  for  (  int  ja  =  ;  ja  <=  n  -  2  ;  ja  ++  )  {  for  (  int  j  =  ja  +  1  ;  j  <=  n  -  1  ;  j  ++  )  {  int  długośćDelta  =  -  ścieżka  [  i  ].  dist2  (  ścieżka  [(  i  +  1  )  %  n  ])  -  ścieżka  [  j  ].  dist2  (  ścieżka  [(  j  +  1  )  %  n  ])  +  ścieżka  [  i  ].  dist2  (  ścieżka  [  j  ])  +  ścieżka  [(  i  +  1  )  %  n  ].  dist2  (  ścieżka  [(  j  +  1  )  %  n  ]);  // Jeśli długość ścieżki jest zmniejszona, wykonaj zamianę 2-opt  if  (  lengthDelta  <  )  {  do2Opt  (  path  ,  i  ,  j  );  CurLength  +=  długośćDelta  ;  znaleziona poprawa  =  true  ;  }  }  }  }  printPath  (  "ścieżka2"  ,  ścieżka  );  powrót  ;  }

Wyjście
























 ścieżka1 = [  [ 743, 933], [ 529, 262], [ 508, 700], [ 256, 752], [ 119, 256], [ 351, 711], [ 705, 843], [ 393, 108] , [ 366, 330], [ 932, 169],  [ 847, 917], [ 868, 972], [ 223, 980], [ 592, 549], [ 169, 164], [ 427, 551], [ 624, 190], [ 920, 635], [ 310, 944], [ 484, 862], [ 301, 363], [ 236, 710], [ 431, 876],  [ 397, 929], [ 491, 675], [ 344, 190], [ 425, 134], [ 30, 629], [ 126, 727], [ 334, 743], [ 760, 104], [ 620, 749], [ 932, 256  ] , [ 613, 572], [ 509, 490], [ 405, 119], [ 49, 695], [ 719, 327], [ 824, 497], [ 649, 596], [ 184, 356],  [ 245, 93], [ 306, 7], [ 754, 509], [ 665, 352], [ 738, 783], [ 690, 801], [ 337, 330], [ 656, 195], [ 11, 963],  [ 42, 427], [ 968, 106], [ 1, 212], [ 480, 510], [ 571, 658], [ 814, 331], [ 564, 847], [ 625, 197] , [ 931, 438], [ 487, 18],  [ 187, 151], [ 179, 913], [ 750, 995], [ 913, 750], [ 134, 562], [ 547, 273], [ 830, 521], [ 557, 140], [ 726, 678], [ 597, 503], [  893, 408], [ 238, 988], [ 93, 85], [ 720, 188], [ 746, 211], [ 710, 387], [ 887, 209], [ 103, 668], [ 900, 473], [ 105, 674], [ 952, 183], [ 787, 370], [ 410, 302  ] , [ 110, 905], [ 996, 400], [ 585, 142], [ 47, 860], [ 731, 924], [ 386, 158], [ 400, 219], [ 55, 415],  [ 874, 682], [ 6, 61], [ 268, 602], [ 470, 365], [ 723, 518], [ 106, 89], [ 130, 319], [ 732, 655], [ 974, 993]  ];  ścieżka2 = [  [ 743, 933], [ 750, 995], [ 847, 917], [ 868, 972], [ 974, 993], [ 913, 750], [ 920, 635], [ 874, 682] , [ 726, 678], [ 732, 655],  [ 830, 521], [ 900, 473], [ 893, 408], [ 931, 438], [ 996, 400], [ 932, 256], [ 952, 183], [ 968, 106], [ 932, 169], [ 887, 209], [  760, 104], [ 746, 211], [ 720, 188], [ 656, 195], [ 625, 197], [ 624, 190], [ 585, 142], [ 557, 140], [ 487, 18], [ 306, 7], [ 245, 93], [ 187, 151], [ 169, 164  ] , [ 106, 89], [ 93, 85], [ 6, 61], [ 1, 212], [ 119, 256], [ 130, 319], [ 184, 356], [ 301, 363],  [ 337, 330], [ 366, 330], [ 410, 302], [ 344, 190], [ 393, 108], [ 405, 119], [ 425, 134], [ 386, 158], [ 400, 219],  [ 529, 262], [ 547, 273], [ 470, 365], [ 509, 490], [ 597, 503], [ 710, 387], [ 665, 352], [ 719, 327] , [ 814, 331], [ 787, 370],  [ 824, 497], [ 754, 509], [ 723, 518], [ 649, 596], [ 571, 658], [ 613, 572], [ 592, 549], [ 480, 510], [ 427, 551], [ 268, 602], [ 134, 562], [ 55, 415], [ 42, 427], [ 30,  629], [ 49, 695], [ 103, 668], [ 105, 674], [ 126, 727], [ 47, 860], [ 11, 963], [ 110, 905], [ 179, 913], [ 223, 980  ] , [ 238, 988], [ 310, 944], [ 256, 752], [ 236, 710], [ 334, 743], [ 351, 711], [ 491, 675], [ 508, 700],  [ 431, 876], [ 397, 929], [ 484, 862], [ 564, 847], [ 620, 749], [ 690, 801], [ 738, 783], [ 705, 843], [ 731, 924]  ];

Wyobrażanie sobie

Zobacz też

GA CROES (1958). Metoda rozwiązywania problemów komiwojażera . Operacje Rez. 6 (1958), s., 791-812.
MM POWÓDŹ (1956). Problem komiwojażera . Operacje Rez. 4 (1956), s. 61-75.

Linki zewnętrzne