. "K-Opt-Heuristik"@de . . . . "8818504"^^ . . "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 - \u00D7 ==> - 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: \n* Example route: A \u2192 B \u2192 E \u2192 D \u2192 C \u2192 F \u2192 G \u2192 H \u2192 A \n* Example parameters: v1=1, v2=4 (assuming starting index is 0) \n* Contents of new_route by step: 1. \n* (A \u2192 B) 2. \n* A \u2192 B \u2192 (C \u2192 D \u2192 E) 3. \n* A \u2192 B \u2192 C \u2192 D \u2192 E \u2192 (F \u2192 G \u2192 H \u2192 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 \u2192 B \u2192 C \u2192 D \u2192 A Swapping using node[0] and node[2] would yield C \u2192 B \u2192 A \u2192 D \u2192 A which is not valid (does not leave from A, the depot)."@en . . . . . . "2-OPT"@ko . "\uC218\uD559\uC801 \uCD5C\uC801\uD654\uC5D0\uC11C 2-OPT\uB294 \uC678\uD310\uC6D0 \uBB38\uC81C\uB97C \uD574\uACB0\uD558\uAE30 \uC704\uD574 1958\uB144 Croes\uAC00 \uC81C\uC548\uD55C \uAC04\uB2E8\uD55C \uC9C0\uC5ED \uD0D0\uC0C9(Local Search) \uC54C\uACE0\uB9AC\uC998\uC774\uB2E4. 2-OPT\uB97C \uD1B5\uD574 \uACBD\uB85C(Route)\uAC00 \uAF2C\uC778(Cross over itself) \uB178\uC120\uC744 \uC7AC\uC815\uB82C(\uC21C\uC11C \uBCC0\uACBD)\uD558\uC5EC \uD480\uC5B4\uC8FC\uACE0, \uC774\uB97C \uD1B5\uD574 \uBE44\uC6A9(Traveling Cost)\uC744 \uAC1C\uC120\uD560 \uC218 \uC788\uB2E4\uB294 \uAC8C \uC8FC\uC694 \uC544\uC774\uB514\uC5B4\uC774\uB2E4. - A B - - A - B - X ==>- C D - - C - D - \uC804\uCCB4 2-OPT \uC9C0\uC5ED \uAC80\uC0C9\uC740 \uAC00\uB2A5\uD55C \uBAA8\uB4E0 \uC720\uD6A8\uD55C \uC870\uD569\uC744 \uBE44\uAD50\uD558\uACE0, \uAD50\uD658(swap)\uD558\uB294 \uBA54\uCEE4\uB2C8\uC998\uC774\uB2E4. \uC774 \uAE30\uC220\uC740 \uC678\uD310\uC6D0 \uBB38\uC81C\uBFD0\uB9CC \uC544\uB2C8\uB77C \uB9CE\uC740 \uAD00\uB828 \uBB38\uC81C\uC5D0 \uC801\uC6A9\uB420 \uC218 \uC788\uC73C\uBA70,\uAC04\uB2E8\uD55C \uBCC0\uACBD(minor modification)\uC744 \uD1B5\uD574 (VRP:Vehicle Routing Problem)\uBFD0\uB9CC \uC544\uB2C8\uB77C capacitated VRP \uC5D0 \uC801\uC6A9\uD560 \uC218 \uC788\uB2E4. \uC544\uB798\uB294 2-OPT swap\uC774 \uC8FC\uC5B4\uC9C4 \uACBD\uB85C\uB97C \uBCC0\uACBD/\uAC1C\uC120\uD558\uB294 \uBC29\uC2DD\uC774\uB2E4 : 2optSwap(route, i, k) { 1. route[1]\uC5D0\uC11C route[i-1]\uAE4C\uC9C0 \uC21C\uC11C\uB300\uB85C new_route\uC5D0 \uCD94\uAC00 2. route[i]\uC5D0\uC11C route[k]\uAE4C\uC9C0 \uC5ED\uC21C\uC73C\uB85C new_route\uC5D0 \uCD94\uAC00 3. route[K + 1]\uC5D0\uC11C \uB05D\uAE4C\uC9C0 \uC21C\uC11C\uB300\uB85C new_route\uC5D0 \uCD94\uAC00 return new_route; } \uC704\uC758 \uBC29\uC2DD\uC5D0 \uB300\uD55C \uC544\uB798 \uC608\uC2DC\uB97C \uBCF4\uBA74 \uAC04\uB2E8\uD788 \uC774\uD574\uD560 \uC218 \uC788\uC744 \uAC83\uC774\uB2E4. 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) \uC774\uB7EC\uD55C \uC54C\uACE0\uB9AC\uC998\uC740 \uC544\uB798\uC640 \uAC19\uC774 \uC815\uB9AC\uD560 \uC218 \uC788\uB2E4. 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 } } } } \uCC38\uACE0 : \uD2B9\uC815 \uB178\uB4DC\uC5D0\uC11C \uCD9C\uBC1C/\uB3C4\uCC29\uD558\uBA74, swap \uD6C4\uBCF4 \uAC80\uC0C9\uC5D0\uC11C \uC774\uB97C \uC81C\uAC70\uD574\uC57C \uD55C\uB2E4. \uADF8\uB807\uC9C0 \uC54A\uC73C\uBA74 \uC798\uBABB\uB41C \uACBD\uB85C\uB97C \uC0DD\uC131\uD55C\uB2E4. \uC608\uB97C \uB4E4\uC5B4, \uB178\uB4DC A: A ==> B ==> C ==> D ==> A \uB178\uB4DC[0]\uACFC \uB178\uB4DC[2]\uC758 swap\uC744 \uD558\uC600\uB2E4\uBA74 C ==> B ==> A ==> D ==> A \uC640 \uAC19\uC774 \uC720\uD6A8\uD558\uC9C0 \uC54A\uC740 \uACBD\uB85C\uB97C \uC0DD\uC131\uD55C\uB2E4.\uCD9C\uBC1C/\uC885\uB8CC\uC810\uC774 \uC815\uD574\uC838 \uC788\uB2E4\uBA74 \uC774\uB97C \uC81C\uC678\uD55C \uB178\uB4DC\uB9CC\uC744 swap\uD6C4\uBCF4\uB85C \uC120\uD0DD\uD560 \uC218 \uC788\uB3C4\uB85D \uD574\uC57C\uD55C\uB2E4."@ko . . . . . . "\uC218\uD559\uC801 \uCD5C\uC801\uD654\uC5D0\uC11C 2-OPT\uB294 \uC678\uD310\uC6D0 \uBB38\uC81C\uB97C \uD574\uACB0\uD558\uAE30 \uC704\uD574 1958\uB144 Croes\uAC00 \uC81C\uC548\uD55C \uAC04\uB2E8\uD55C \uC9C0\uC5ED \uD0D0\uC0C9(Local Search) \uC54C\uACE0\uB9AC\uC998\uC774\uB2E4. 2-OPT\uB97C \uD1B5\uD574 \uACBD\uB85C(Route)\uAC00 \uAF2C\uC778(Cross over itself) \uB178\uC120\uC744 \uC7AC\uC815\uB82C(\uC21C\uC11C \uBCC0\uACBD)\uD558\uC5EC \uD480\uC5B4\uC8FC\uACE0, \uC774\uB97C \uD1B5\uD574 \uBE44\uC6A9(Traveling Cost)\uC744 \uAC1C\uC120\uD560 \uC218 \uC788\uB2E4\uB294 \uAC8C \uC8FC\uC694 \uC544\uC774\uB514\uC5B4\uC774\uB2E4. - A B - - A - B - X ==>- C D - - C - D - \uC804\uCCB4 2-OPT \uC9C0\uC5ED \uAC80\uC0C9\uC740 \uAC00\uB2A5\uD55C \uBAA8\uB4E0 \uC720\uD6A8\uD55C \uC870\uD569\uC744 \uBE44\uAD50\uD558\uACE0, \uAD50\uD658(swap)\uD558\uB294 \uBA54\uCEE4\uB2C8\uC998\uC774\uB2E4. \uC774 \uAE30\uC220\uC740 \uC678\uD310\uC6D0 \uBB38\uC81C\uBFD0\uB9CC \uC544\uB2C8\uB77C \uB9CE\uC740 \uAD00\uB828 \uBB38\uC81C\uC5D0 \uC801\uC6A9\uB420 \uC218 \uC788\uC73C\uBA70,\uAC04\uB2E8\uD55C \uBCC0\uACBD(minor modification)\uC744 \uD1B5\uD574 (VRP:Vehicle Routing Problem)\uBFD0\uB9CC \uC544\uB2C8\uB77C capacitated VRP \uC5D0 \uC801\uC6A9\uD560 \uC218 \uC788\uB2E4. \uC544\uB798\uB294 2-OPT swap\uC774 \uC8FC\uC5B4\uC9C4 \uACBD\uB85C\uB97C \uBCC0\uACBD/\uAC1C\uC120\uD558\uB294 \uBC29\uC2DD\uC774\uB2E4 : \uC704\uC758 \uBC29\uC2DD\uC5D0 \uB300\uD55C \uC544\uB798 \uC608\uC2DC\uB97C \uBCF4\uBA74 \uAC04\uB2E8\uD788 \uC774\uD574\uD560 \uC218 \uC788\uC744 \uAC83\uC774\uB2E4. \uC774\uB7EC\uD55C \uC54C\uACE0\uB9AC\uC998\uC740 \uC544\uB798\uC640 \uAC19\uC774 \uC815\uB9AC\uD560 \uC218 \uC788\uB2E4. \uC608\uB97C \uB4E4\uC5B4, \uB178\uB4DC A: \uB178\uB4DC[0]\uACFC \uB178\uB4DC[2]\uC758 swap\uC744 \uD558\uC600\uB2E4\uBA74"@ko . . "Die k-Opt-Heuristiken sind eine Klasse von Algorithmen zum n\u00E4herungsweisen L\u00F6sen des Problems des Handlungsreisenden (TSP). Die k-Opt-Heuristiken geh\u00F6ren zu den (engl.: Nach-Optimierung), die sich dadurch auszeichnen, dass sie eine bereits gefundene L\u00F6sung 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\u00FCrzer als die alte, wird sie als neue L\u00F6sung verwendet."@de . . . . . . . . "En optimisation, 2-opt est un algorithme de recherche locale propos\u00E9 par Georges A. Croes en 1958 pour r\u00E9soudre le probl\u00E8me du voyageur de commerce en am\u00E9liorant une solution initiale."@fr . . . . . . . . . "Die k-Opt-Heuristiken sind eine Klasse von Algorithmen zum n\u00E4herungsweisen L\u00F6sen des Problems des Handlungsreisenden (TSP). Die k-Opt-Heuristiken geh\u00F6ren zu den (engl.: Nach-Optimierung), die sich dadurch auszeichnen, dass sie eine bereits gefundene L\u00F6sung 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\u00FCrzer als die alte, wird sie als neue L\u00F6sung verwendet."@de . . "2-opt"@fr . . "2-opt"@en . "En optimisation, 2-opt est un algorithme de recherche locale propos\u00E9 par Georges A. Croes en 1958 pour r\u00E9soudre le probl\u00E8me du voyageur de commerce en am\u00E9liorant une solution initiale."@fr . . . . . . "5820"^^ . . . . . "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 - \u00D7 ==> - 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 \u2192 B \u2192 C \u2192 D \u2192 A"@en . "1113143213"^^ .