In optimization, 2-opt is a simple local search algorithm for solving the traveling salesman problem.The 2-opt algorithm was first proposed by Croes in 1958, although the basic move had already been suggested by Flood. The main idea behind it is to take a route that crosses over itself and reorder it so that it does not. - A B - - A - B - × ==> - C D - - C - D - This is the mechanism by which the 2-opt swap manipulates a given route. Here v1 and v2 are the first vertices of the edges you wish to swap when traversing through the route: A → B → C → D → A
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - K-Opt-Heuristik (de)
- 2-opt (en)
- 2-opt (fr)
- 2-OPT (ko)
|
| rdfs:comment
| - Die k-Opt-Heuristiken sind eine Klasse von Algorithmen zum näherungsweisen Lösen des Problems des Handlungsreisenden (TSP). Die k-Opt-Heuristiken gehören zu den (engl.: Nach-Optimierung), die sich dadurch auszeichnen, dass sie eine bereits gefundene Lösung weiter verbessern. Die Grundidee besteht darin, Kanten aus einer gegebenen Tour zu entfernen und gegen andere Kanten auszutauschen, so dass sich wieder eine Tour ergibt. Ist die neue Tour kürzer als die alte, wird sie als neue Lösung verwendet. (de)
- En optimisation, 2-opt est un algorithme de recherche locale proposé par Georges A. Croes en 1958 pour résoudre le problème du voyageur de commerce en améliorant une solution initiale. (fr)
- In optimization, 2-opt is a simple local search algorithm for solving the traveling salesman problem.The 2-opt algorithm was first proposed by Croes in 1958, although the basic move had already been suggested by Flood. The main idea behind it is to take a route that crosses over itself and reorder it so that it does not. - A B - - A - B - × ==> - C D - - C - D - This is the mechanism by which the 2-opt swap manipulates a given route. Here v1 and v2 are the first vertices of the edges you wish to swap when traversing through the route: A → B → C → D → A (en)
- 수학적 최적화에서 2-OPT는 외판원 문제를 해결하기 위해 1958년 Croes가 제안한 간단한 지역 탐색(Local Search) 알고리즘이다. 2-OPT를 통해 경로(Route)가 꼬인(Cross over itself) 노선을 재정렬(순서 변경)하여 풀어주고, 이를 통해 비용(Traveling Cost)을 개선할 수 있다는 게 주요 아이디어이다. - A B - - A - B - X ==>- C D - - C - D - 전체 2-OPT 지역 검색은 가능한 모든 유효한 조합을 비교하고, 교환(swap)하는 메커니즘이다. 이 기술은 외판원 문제뿐만 아니라 많은 관련 문제에 적용될 수 있으며,간단한 변경(minor modification)을 통해 (VRP:Vehicle Routing Problem)뿐만 아니라 capacitated VRP 에 적용할 수 있다. 아래는 2-OPT swap이 주어진 경로를 변경/개선하는 방식이다 : 위의 방식에 대한 아래 예시를 보면 간단히 이해할 수 있을 것이다. 이러한 알고리즘은 아래와 같이 정리할 수 있다. 예를 들어, 노드 A: 노드[0]과 노드[2]의 swap을 하였다면 (ko)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - In optimization, 2-opt is a simple local search algorithm for solving the traveling salesman problem.The 2-opt algorithm was first proposed by Croes in 1958, although the basic move had already been suggested by Flood. The main idea behind it is to take a route that crosses over itself and reorder it so that it does not. - A B - - A - B - × ==> - C D - - C - D - A complete 2-opt local search will compare every possible valid combination of the swapping mechanism. This technique can be applied to the traveling salesman problem as well as many related problems. These include the vehicle routing problem (VRP) as well as the capacitated VRP, which require minor modification of the algorithm. This is the mechanism by which the 2-opt swap manipulates a given route. Here v1 and v2 are the first vertices of the edges you wish to swap when traversing through the route: procedure 2optSwap(route, v1, v2) { 1. take route[0] to route[v1] and add them in order to new_route 2. take route[v1+1] to route[v2] and add them in reverse order to new_route 3. take route[v2+1] to route[end] and add them in order to new_route return new_route;} Here is an example of the above with arbitrary input:
* Example route: A → B → E → D → C → F → G → H → A
* Example parameters: v1=1, v2=4 (assuming starting index is 0)
* Contents of new_route by step: 1.
* (A → B) 2.
* A → B → (C → D → E) 3.
* A → B → C → D → E → (F → G → H → A) This is the complete 2-opt swap making use of the above mechanism: repeat until no improvement is made { best_distance = calculateTotalDistance(existing_route) start_again: for (i = 0; i <= number of nodes eligible to be swapped - 1; i++) { for (j = i + 1; j <= number of nodes eligible to be swapped; j++) { new_route = 2optSwap(existing_route, i, j) new_distance = calculateTotalDistance(new_route) if (new_distance < best_distance) { existing_route = new_route best_distance = new_distance goto start_again } } }} Note: If you start/end at a particular node or depot, then you must remove this from the search as an eligible candidate for swapping, as reversing the order will cause an invalid path. For example, with depot at A: A → B → C → D → A Swapping using node[0] and node[2] would yield C → B → A → D → A which is not valid (does not leave from A, the depot). (en)
- Die k-Opt-Heuristiken sind eine Klasse von Algorithmen zum näherungsweisen Lösen des Problems des Handlungsreisenden (TSP). Die k-Opt-Heuristiken gehören zu den (engl.: Nach-Optimierung), die sich dadurch auszeichnen, dass sie eine bereits gefundene Lösung weiter verbessern. Die Grundidee besteht darin, Kanten aus einer gegebenen Tour zu entfernen und gegen andere Kanten auszutauschen, so dass sich wieder eine Tour ergibt. Ist die neue Tour kürzer als die alte, wird sie als neue Lösung verwendet. (de)
- En optimisation, 2-opt est un algorithme de recherche locale proposé par Georges A. Croes en 1958 pour résoudre le problème du voyageur de commerce en améliorant une solution initiale. (fr)
- 수학적 최적화에서 2-OPT는 외판원 문제를 해결하기 위해 1958년 Croes가 제안한 간단한 지역 탐색(Local Search) 알고리즘이다. 2-OPT를 통해 경로(Route)가 꼬인(Cross over itself) 노선을 재정렬(순서 변경)하여 풀어주고, 이를 통해 비용(Traveling Cost)을 개선할 수 있다는 게 주요 아이디어이다. - A B - - A - B - X ==>- C D - - C - D - 전체 2-OPT 지역 검색은 가능한 모든 유효한 조합을 비교하고, 교환(swap)하는 메커니즘이다. 이 기술은 외판원 문제뿐만 아니라 많은 관련 문제에 적용될 수 있으며,간단한 변경(minor modification)을 통해 (VRP:Vehicle Routing Problem)뿐만 아니라 capacitated VRP 에 적용할 수 있다. 아래는 2-OPT swap이 주어진 경로를 변경/개선하는 방식이다 : 2optSwap(route, i, k) { 1. route[1]에서 route[i-1]까지 순서대로 new_route에 추가 2. route[i]에서 route[k]까지 역순으로 new_route에 추가 3. route[K + 1]에서 끝까지 순서대로 new_route에 추가 return new_route; } 위의 방식에 대한 아래 예시를 보면 간단히 이해할 수 있을 것이다. example route: A ==> B ==> C ==> D ==> E ==> F ==> G ==> H ==> A example i = 4, example k = 7 new_route: 1. (A ==> B ==> C) 2. A ==> B ==> C ==> (G ==> F ==> E ==> D) 3. A ==> B ==> C ==> G ==> F ==> E ==> D (==> H ==> A) 이러한 알고리즘은 아래와 같이 정리할 수 있다. repeat until no improvement is made { start_again: best_distance = calculateTotalDistance(existing_route) for (i = 0; i < number of nodes eligible to be swapped - 1; i++) { for (k = i + 1; k < number of nodes eligible to be swapped; k++) { new_route = 2optSwap(existing_route, i, k) new_distance = calculateTotalDistance(new_route) if (new_distance < best_distance) { existing_route = new_route goto start_again } } } } 참고 : 특정 노드에서 출발/도착하면, swap 후보 검색에서 이를 제거해야 한다. 그렇지 않으면 잘못된 경로를 생성한다. 예를 들어, 노드 A: A ==> B ==> C ==> D ==> A 노드[0]과 노드[2]의 swap을 하였다면 C ==> B ==> A ==> D ==> A 와 같이 유효하지 않은 경로를 생성한다.출발/종료점이 정해져 있다면 이를 제외한 노드만을 swap후보로 선택할 수 있도록 해야한다. (ko)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
