Misplaced Pages

#661338

53-548: For a given instance ( G , c ) {\displaystyle (G,c)} of the travelling salesman problem, tours are uniquely determined by their sets of edges, so we may as well encode them as such. In the main loop of the local search, we have a current tour T ⊂ E ( G ) {\displaystyle T\subset \mathrm {E} (G)} and are looking for new tour T ′ ⊂ E ( G ) {\displaystyle T'\subset \mathrm {E} (G)} such that

106-484: A i > 0 {\displaystyle \sum _{i=0}^{n-1}a_{i}>0} , then there is a cyclic permutation of these numbers such that all partial sums are positive as well, i.e., there is some k {\displaystyle k} such that For a closed alternating trail F = e 0 e 1 … e n − 1 {\displaystyle F=e_{0}\,e_{1}\,\dots \,e_{n-1}} , one may define

159-453: A i = c ( e i ) {\displaystyle a_{i}=c(e_{i})} if e i ∈ T {\displaystyle e_{i}\in T} and a i = − c ( e i ) {\displaystyle a_{i}=-c(e_{i})} if e i ∉ T {\displaystyle e_{i}\notin T} ;

212-470: A ∈ ⋃ M : | { A ∈ M : a ∈ A } |  is odd } . {\displaystyle \Delta M=\left\{a\in \bigcup M:\left|\{A\in M:a\in A\}\right|{\text{ is odd}}\right\}.} Evidently, this is well-defined only when each element of the union ⋃ M {\textstyle \bigcup M}

265-899: A metric if Σ is considered modulo the equivalence relation X ~ Y if and only if μ ( X Δ Y ) = 0 {\displaystyle \mu (X\,\Delta \,Y)=0} . It is sometimes called Fréchet - Nikodym metric. The resulting metric space is separable if and only if L (μ) is separable. If μ ( X ) , μ ( Y ) < ∞ {\displaystyle \mu (X),\mu (Y)<\infty } , we have: | μ ( X ) − μ ( Y ) | ≤ μ ( X Δ Y ) {\displaystyle |\mu (X)-\mu (Y)|\leq \mu (X\,\Delta \,Y)} . Indeed, If S = ( Ω , A , μ ) {\displaystyle S=\left(\Omega ,{\mathcal {A}},\mu \right)}

318-409: A metric space . If S has n elements, then the distance from the empty set to S is n , and this is the maximum distance for any pair of subsets. Using the ideas of measure theory , the separation of measurable sets can be defined to be the measure of their symmetric difference. If μ is a σ-finite measure defined on a σ-algebra Σ, the function is a pseudometric on Σ. d μ becomes

371-733: A better tour has been found, but also as a constraint to descending in the search tree, as controlled via the infeasibility depth p 2 {\displaystyle p_{2}} . Concretely, at larger depths in the search a vertex v 2 k + 1 {\displaystyle v_{2k+1}} is only appended to the alternating trail if T △ { v 0 v 1 , v 1 v 2 , … , v 2 k v 2 k + 1 , v 2 k + 1 v 0 } {\displaystyle T\mathbin {\triangle } \{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{2k}v_{2k+1},v_{2k+1}v_{0}\}}

424-433: A form of addition modulo 2 . The power set of any set becomes an abelian group under the operation of symmetric difference, with the empty set as the neutral element of the group and every element in this group being its own inverse . The power set of any set becomes a Boolean ring , with symmetric difference as the addition of the ring and intersection as the multiplication of the ring. The symmetric difference

477-471: A tour; it could alternatively turn out to be a disconnected 2 {\displaystyle 2} -regular subgraph. Alternating trails (closed or open) are built by extending a shorter alternating trail, so when exploring the neighbourhood of the current tour T {\displaystyle T} , one is exploring a search tree of alternating trails. The key idea of the Lin–Kernighan algorithm

530-567: Is { 1 , 2 , 4 } {\displaystyle \{1,2,4\}} . The symmetric difference of the sets A and B is commonly denoted by A Δ ⁡ B {\displaystyle A\operatorname {\Delta } B} (alternatively, A △ ⁡ B {\displaystyle A\operatorname {\vartriangle } B} ), A ⊕ B {\displaystyle A\oplus B} , or A ⊖ B {\displaystyle A\ominus B} . It can be viewed as

583-969: Is a formula for | Δ M | {\displaystyle |\Delta M|} , the number of elements in Δ M {\displaystyle \Delta M} , given solely in terms of intersections of elements of M {\displaystyle M} : | Δ M | = ∑ l = 1 n ( − 2 ) l − 1 ∑ 1 ≤ i 1 < i 2 < … < i l ≤ n | M i 1 ∩ M i 2 ∩ … ∩ M i l | . {\displaystyle |\Delta M|=\sum _{l=1}^{n}(-2)^{l-1}\sum _{1\leq i_{1}<i_{2}<\ldots <i_{l}\leq n}\left|M_{i_{1}}\cap M_{i_{2}}\cap \ldots \cap M_{i_{l}}\right|.} As long as there

SECTION 10

#1732798090662

636-641: Is a measure space and F , G ∈ A {\displaystyle F,G\in {\mathcal {A}}} are measurable sets, then their symmetric difference is also measurable: F Δ G ∈ A {\displaystyle F\Delta G\in {\mathcal {A}}} . One may define an equivalence relation on measurable sets by letting F {\displaystyle F} and G {\displaystyle G} be related if μ ( F Δ G ) = 0 {\displaystyle \mu \left(F\Delta G\right)=0} . This relation

689-401: Is a notion of "how big" a set is, the symmetric difference between two sets can be considered a measure of how "far apart" they are. First consider a finite set S and the counting measure on subsets given by their size. Now consider two subsets of S and set their distance apart as the size of their symmetric difference. This distance is in fact a metric , which makes the power set on S

742-852: Is a partial order on the family of subsets of A {\displaystyle {\mathcal {A}}} . We write D = E [ A , μ ] {\displaystyle {\mathcal {D}}={\mathcal {E}}\left[{\mathcal {A}},\mu \right]} if D ⊆ E [ A , μ ] {\displaystyle {\mathcal {D}}\subseteq {\mathcal {E}}\left[{\mathcal {A}},\mu \right]} and E ⊆ D [ A , μ ] {\displaystyle {\mathcal {E}}\subseteq {\mathcal {D}}\left[{\mathcal {A}},\mu \right]} . The relation " = [ A , μ ] {\displaystyle =\left[{\mathcal {A}},\mu \right]} "

795-737: Is a sub- σ {\displaystyle \sigma } -algebra of A {\displaystyle {\mathcal {A}}} , so is the symmetric closure of D {\displaystyle {\mathcal {D}}} . F = G [ A , μ ] {\displaystyle F=G\left[{\mathcal {A}},\mu \right]} iff | 1 F − 1 G | = 0 {\displaystyle \left|\mathbf {1} _{F}-\mathbf {1} _{G}\right|=0} [ A , μ ] {\displaystyle \left[{\mathcal {A}},\mu \right]} almost everywhere . The Hausdorff distance and

848-466: Is a tour. By design that set of edges constitutes a 2-factor in G {\displaystyle G} , so what needs to be determined is whether that 2-factor consists of a single Hamiltonian cycle, or instead is made up of several cycles. If naively posing this subproblem as giving a subroutine the set of n {\displaystyle n} edges as input, one ends up with O ( n ) {\displaystyle O(n)} as

901-395: Is again a tour, looking for such a set which has g ( F ) > 0 {\displaystyle g(F)>0} . It is however easier to do those tests in the opposite order: first search for plausible F {\displaystyle F} with positive gain, and only second check if T △ F {\displaystyle T\mathbin {\triangle } F}

954-791: Is an equivalence relationship between the subsets of A {\displaystyle {\mathcal {A}}} . The symmetric closure of D {\displaystyle {\mathcal {D}}} is the collection of all A {\displaystyle {\mathcal {A}}} -measurable sets that are = [ A , μ ] {\displaystyle =\left[{\mathcal {A}},\mu \right]} to some D ∈ D {\displaystyle D\in {\mathcal {D}}} . The symmetric closure of D {\displaystyle {\mathcal {D}}} contains D {\displaystyle {\mathcal {D}}} . If D {\displaystyle {\mathcal {D}}}

1007-406: Is before or after v 2 k {\displaystyle v_{2k}} . Hence it would be sufficient to examine 2 k {\displaystyle 2k} different cases as part of performing step 2.3.2 for v 2 k − 1 {\displaystyle v_{2k-1}} ; as far as v 2 k + 1 {\displaystyle v_{2k+1}}

1060-555: Is concerned, the outcome of this test can be inherited information rather than something that has to be computed fresh. Symmetric difference In mathematics , the symmetric difference of two sets , also known as the disjunctive union and set sum , is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets { 1 , 2 , 3 } {\displaystyle \{1,2,3\}} and { 3 , 4 } {\displaystyle \{3,4\}}

1113-496: Is contained in the union of the symmetric difference of A and B and that of B and C . Intersection distributes over symmetric difference: and this shows that the power set of X becomes a ring , with symmetric difference as addition and intersection as multiplication. This is the prototypical example of a Boolean ring . Further properties of the symmetric difference include: The symmetric difference can be defined in any Boolean algebra , by writing This operation has

SECTION 20

#1732798090662

1166-399: Is contributed by a finite number of elements of M {\displaystyle M} . Suppose M = { M 1 , M 2 , … , M n } {\displaystyle M=\left\{M_{1},M_{2},\ldots ,M_{n}\right\}} is a multiset and n ≥ 2 {\displaystyle n\geq 2} . Then there

1219-1031: Is denoted F = G [ A , μ ] {\displaystyle F=G\left[{\mathcal {A}},\mu \right]} . Given D , E ⊆ A {\displaystyle {\mathcal {D}},{\mathcal {E}}\subseteq {\mathcal {A}}} , one writes D ⊆ E [ A , μ ] {\displaystyle {\mathcal {D}}\subseteq {\mathcal {E}}\left[{\mathcal {A}},\mu \right]} if to each D ∈ D {\displaystyle D\in {\mathcal {D}}} there's some E ∈ E {\displaystyle E\in {\mathcal {E}}} such that D = E [ A , μ ] {\displaystyle D=E\left[{\mathcal {A}},\mu \right]} . The relation " ⊆ [ A , μ ] {\displaystyle \subseteq \left[{\mathcal {A}},\mu \right]} "

1272-517: Is equivalent to the union of both relative complements , that is: The symmetric difference can also be expressed using the XOR operation ⊕ on the predicates describing the two sets in set-builder notation : The same fact can be stated as the indicator function (denoted here by χ {\displaystyle \chi } ) of the symmetric difference, being the XOR (or addition mod 2 ) of

1325-696: Is in fact a tour. Define a trail in G {\displaystyle G} to be alternating (with respect to T {\displaystyle T} ) if its edges are alternatingly in T {\displaystyle T} and not in T {\displaystyle T} , respectively. Because the subgraphs ( V ( G ) , T ) {\displaystyle {\bigl (}\mathrm {V} (G),T{\bigr )}} and ( V ( G ) , T ′ ) {\displaystyle {\bigl (}\mathrm {V} (G),T'{\bigr )}} are 2 {\displaystyle 2} - regular ,

1378-473: Is to remove from this tree all alternating trails which have gain ≤ 0 {\displaystyle \leq 0} . This does not prevent finding every closed trail with positive gain, thanks to the following lemma. Lemma. If a 0 , … , a n − 1 {\displaystyle a_{0},\dotsc ,a_{n-1}} are numbers such that ∑ i = 0 n − 1

1431-426: Is used in graph theory , to define the cycle space of a graph. From the property of the inverses in a Boolean group, it follows that the symmetric difference of two repeated symmetric differences is equivalent to the repeated symmetric difference of the join of the two multisets, where for each double set both can be removed. In particular: This implies triangle inequality: the symmetric difference of A and C

1484-534: The symmetric difference F = T △ T ′ {\displaystyle F=T\mathbin {\triangle } T'} is not too large and the length ∑ e ∈ T ′ c ( e ) {\displaystyle \sum _{e\in T'}c(e)} of the new tour is less than the length ∑ e ∈ T c ( e ) {\displaystyle \sum _{e\in T}c(e)} of

1537-475: The (area of the) symmetric difference are both pseudo-metrics on the set of measurable geometric shapes. However, they behave quite differently. The figure at the right shows two sequences of shapes, "Red" and "Red ∪ Green". When the Hausdorff distance between them becomes smaller, the area of the symmetric difference between them becomes larger, and vice versa. By continuing these sequences in both directions, it

1590-505: The Hamiltonicity test done when considering the ( k + 1 ) {\displaystyle (k+1)} th edge v 2 k v 2 k + 1 {\displaystyle v_{2k}v_{2k+1}} depends only on in which of these paths that v 2 k {\displaystyle v_{2k}} resides and whether v 2 k + 1 {\displaystyle v_{2k+1}}

1643-399: The Lin–Kernighan heuristic proper, and what constitutes further refinements. For the asymmetric TSP, the idea of using positive gain alternating trails to find favourable exchanges is less useful, because there are fewer ways in which pieces of a tour can be rearranged to yield new tours when one may not reverse the orientation of a piece. Two pieces can only be patched together to reproduce

Lin–Kernighan heuristic - Misplaced Pages Continue

1696-450: The average overall running time for their algorithm, but other implementors have had trouble reproducing that result. It appears unlikely that the worst-case running time is polynomial. In terms of a stack as above, the algorithm is: The length of the alternating trails considered are thus not explicitly bounded, but beyond the backtracking depth p 1 {\displaystyle p_{1}} no more than one way of extending

1749-866: The current tour T {\displaystyle T} is than the new tour T ′ {\displaystyle T'} . Naively k {\displaystyle k} -opt can be regarded as examining all F ⊆ E ( G ) {\displaystyle F\subseteq \mathrm {E} (G)} with exactly 2 k {\displaystyle 2k} elements ( k {\displaystyle k} in T {\displaystyle T} but not in T ′ {\displaystyle T'} , and another k {\displaystyle k} in T ′ {\displaystyle T'} but not in T {\displaystyle T} ) such that T △ F {\displaystyle T\mathbin {\triangle } F}

1802-668: The current tour. Since F {\displaystyle F} is typically much smaller than T {\displaystyle T} and T ′ {\displaystyle T'} , it is convenient to consider the quantity since g ( T △ T ′ ) = ∑ e ∈ T c ( e ) − ∑ e ∈ T ′ c ( e ) {\displaystyle g(T\mathbin {\triangle } T')=\sum _{e\in T}c(e)-\sum _{e\in T'}c(e)} : how much longer

1855-432: The current trail is considered, which in principle stops those explorations from raising the exponent in the runtime complexity. The closed alternating trails found by the above method are all connected, but the symmetric difference T △ T ′ {\displaystyle T\mathbin {\triangle } T'} of two tours need not be, so in general this method of alternating trails cannot explore

1908-530: The enumeration after finding the first hit. It should however be remarked that: The basic form of the Lin–Kernighan algorithm not only does a local search counterpart of the above enumeration, but it also introduces two parameters that narrow the search. Because there are O ( n ⌊ p 1 / 2 ⌋ ) {\displaystyle O(n^{\lfloor p_{1}/2\rfloor })} alternating trails of length p 1 {\displaystyle p_{1}} , and

1961-529: The final round of the algorithm may have to check all of them before concluding that the current tour is locally optimal, we get ⌊ p 1 / 2 ⌋ {\displaystyle \lfloor p_{1}/2\rfloor } (standard value 2 {\displaystyle 2} ) as a lower bound on the exponent of the algorithm complexity. Lin & Kernighan report 2.2 {\displaystyle 2.2} as an empirical exponent of n {\displaystyle n} in

2014-461: The full neighbourhood of a trail T {\displaystyle T} . The literature on the Lin–Kernighan heuristic uses the term sequential exchanges for those that are described by a single alternating trail. The smallest non-sequential exchange would however replace 4 edges and consist of two cycles of 4 edges each (2 edges added, 2 removed), so it is long compared to the typical Lin–Kernighan exchange, and there are few of these compared to

2067-409: The full set of 4-edge exchanges. In at least one implementation by Lin & Kernighan there was an extra final step considering such non-sequential exchanges of 4 edges before declaring a tour locally optimal, which would mean the tours produced are 4-opt unless one introduces further constraints on the search (which Lin and Kernighan in fact did). The literature is vague on exactly what is included in

2120-432: The gains of the partial trails are positive as well, so F {\displaystyle F} will be found when the search explores the branch of alternating trails starting at v 0 {\displaystyle v_{0}} . (Prior to that the search may have considered other subtrails of F {\displaystyle F} starting at other vertices but backed out because some subtrail failed

2173-805: The graph G [ T △ T ′ ] {\displaystyle G[T\mathbin {\triangle } T']} decomposes into closed alternating trails. Sets F ⊆ E ( G ) {\displaystyle F\subseteq \mathrm {E} (G)} that may satisfy F = T △ T ′ {\displaystyle F=T\mathbin {\triangle } T'} for some tour T ′ {\displaystyle T'} may thus be found by enumerating closed alternating trails in G {\displaystyle G} , even if not every closed alternating trail F {\displaystyle F} makes T △ F {\displaystyle T\mathbin {\triangle } F} into

Lin–Kernighan heuristic - Misplaced Pages Continue

2226-468: The group thus obtained is the Klein four-group . Equivalently, a Boolean group is an elementary abelian 2-group . Consequently, the group induced by the symmetric difference is in fact a vector space over the field with 2 elements Z 2 . If X is finite, then the singletons form a basis of this vector space, and its dimension is therefore equal to the number of elements of X . This construction

2279-782: The indicator functions of its two arguments: χ ( A Δ B ) = χ A ⊕ χ B {\displaystyle \chi _{(A\,\Delta \,B)}=\chi _{A}\oplus \chi _{B}} or using the Iverson bracket notation [ x ∈ A Δ B ] = [ x ∈ A ] ⊕ [ x ∈ B ] {\displaystyle [x\in A\,\Delta \,B]=[x\in A]\oplus [x\in B]} . The symmetric difference can also be expressed as

2332-486: The original tour. Three pieces can be patched together to form a different tour in one way only, and the corresponding alternating trail does not extend to a closed trail for rearranging four pieces into a new tour. To rearrange four pieces, one needs a non-sequential exchange. The Lin–Kernighan heuristic checks the validity of tour candidates T △ F {\displaystyle T\mathbin {\triangle } F} at two points: obviously when deciding whether

2385-477: The positive gain constraint.) Reducing the number of branches to explore translates directly to a reduction in runtime, and the sooner a branch can be pruned, the better. This yields the following algorithm for finding all closed, positive gain alternating trails in the graph. As an enumeration algorithm this is slightly flawed, because it may report the same trail multiple times, with different starting points, but Lin–Kernighan does not care because it mostly aborts

2438-437: The same properties as the symmetric difference of sets. Repeated symmetric difference is in a sense equivalent to an operation on a multitude of sets (possibly with multiple appearances of the same set) giving the set of elements which are in an odd number of sets. The symmetric difference of a collection of sets contains just elements which are in an odd number of the sets in the collection: Δ M = {

2491-743: The subgraph G [ T △ T ′ ] = ( V ( G ) , T △ T ′ ) {\displaystyle G[T\mathbin {\triangle } T']={\bigl (}\mathrm {V} (G),T\mathbin {\triangle } T'{\bigr )}} will have vertices of degree 0 {\displaystyle 0} , 2 {\displaystyle 2} , and 4 {\displaystyle 4} only, and at each vertex there are as many incident edges from T {\displaystyle T} as there are from T ′ {\displaystyle T'} . Hence (essentially by Hierholzer's algorithm for finding Eulerian circuits )

2544-443: The sum ∑ i = 0 n − 1 a i {\displaystyle \sum \nolimits _{i=0}^{n-1}a_{i}} is then the gain g ( F ) {\displaystyle g(F)} . Here the lemma implies that there for every closed alternating trail with positive gain exists at least one starting vertex v 0 {\displaystyle v_{0}} for which all

2597-457: The symmetric difference as operation.) A group in which every element is its own inverse (or, equivalently, in which every element has order 2) is sometimes called a Boolean group ; the symmetric difference provides a prototypical example of such groups. Sometimes the Boolean group is actually defined as the symmetric difference operation on a set. In the case where X has only two elements,

2650-829: The test can instead be carried out in constant time. A useful degree of freedom here is that one may choose the order in which step 2.3.2 iterates over all vertices; in particular, one may follow the known tour T {\displaystyle T} . After picking k {\displaystyle k} edges from T {\displaystyle T} , the remaining subgraph ( V ( G ) , T ∖ { v 0 v 1 , … , v 2 k − 2 v 2 k − 1 } ) {\displaystyle {\bigl (}\mathrm {V} (G),T\setminus \{v_{0}v_{1},\dotsc ,v_{2k-2}v_{2k-1}\}{\bigr )}} consists of k {\displaystyle k} paths. The outcome of

2703-417: The time complexity for this check, since it is necessary to walk around the full tour before being able to determine that it is in fact a Hamiltonian cycle. That is too slow for the second usage of this test, which gets carried out for every alternating trail with more than 2 {\displaystyle 2} edges from T {\displaystyle T} . If keeping track of more information,

SECTION 50

#1732798090662

2756-997: The union of the two sets, minus their intersection : In particular, A Δ B ⊆ A ∪ B {\displaystyle A\mathbin {\Delta } B\subseteq A\cup B} ; the equality in this non-strict inclusion occurs if and only if A {\displaystyle A} and B {\displaystyle B} are disjoint sets . Furthermore, denoting D = A Δ B {\displaystyle D=A\mathbin {\Delta } B} and I = A ∩ B {\displaystyle I=A\cap B} , then D {\displaystyle D} and I {\displaystyle I} are always disjoint, so D {\displaystyle D} and I {\displaystyle I} partition A ∪ B {\displaystyle A\cup B} . Consequently, assuming intersection and symmetric difference as primitive operations,

2809-408: The union of two sets can be well defined in terms of symmetric difference by the right-hand side of the equality The symmetric difference is commutative and associative : The empty set is neutral , and every set is its own inverse: Thus, the power set of any set X becomes an abelian group under the symmetric difference operation. (More generally, any field of sets forms a group with

#661338