About: 3-opt

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: 3-opt Goto Sponge NotDistinct Permalink

An Entity of Type : yago:Rule105846932, within Data Space : dbpedia.org associated with source document(s)
QRcode icon

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2F3-opt

In optimization, 3-opt is a simple local search algorithm for solving the travelling salesperson problem and related problems. Compared to the simpler 2-opt algorithm, it is slower but can generate higher-quality solutions. This is the mechanism by which the 3-opt swap manipulates a given route: The principle is pretty simple. You compute the original distance and you compute the cost of each modification. If you find a better cost, apply the modification and return (relative cost).This is the complete 3-opt swap making use of the above mechanism:

Attributes	Values
rdf:type	software yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatHeuristicAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932
rdfs:label	3-opt (en)
rdfs:comment	In optimization, 3-opt is a simple local search algorithm for solving the travelling salesperson problem and related problems. Compared to the simpler 2-opt algorithm, it is slower but can generate higher-quality solutions. This is the mechanism by which the 3-opt swap manipulates a given route: The principle is pretty simple. You compute the original distance and you compute the cost of each modification. If you find a better cost, apply the modification and return (relative cost).This is the complete 3-opt swap making use of the above mechanism: (en)
dcterms:subject	Heuristic algorithms Travelling salesman problem
Wikipage page ID	8818695 (xsd:integer)
Wikipage revision ID	1044566353 (xsd:integer)
Link from a Wikipage to another Wikipage	Graph (discrete mathematics) Lin–Kernighan heuristic Local search (optimization) 2-opt Heuristic algorithms Travelling salesman problem Travelling salesperson problem ORSA (OR) dbr:Network_optimization
Link from a Wikipage to an external page	http://bstj.bell-labs.com/BSTJ/images/Vol44/bstj44-10-2245.pdf http://www.dti.unimi.it/~righini/Didattica/Algoritmi%20Euristici/MaterialeAE/Lin%20Kernighan%20TSP.pdf http://www.tmsk.uitm.edu.my/~naimah/csc751/slides/LS.pdf
sameAs	3-opt 3-opt 3-opt 3-opt
dbp:wikiPageUsesTemplate	dbt:Cite_book dbt:Dead_link dbt:Expert_needed dbt:Reflist
bot	InternetArchiveBot (en)
date	April 2019 (en) September 2018 (en)
fix-attempted	yes (en)
has abstract	In optimization, 3-opt is a simple local search algorithm for solving the travelling salesperson problem and related problems. Compared to the simpler 2-opt algorithm, it is slower but can generate higher-quality solutions. 3-opt analysis involves deleting 3 connections (or edges) in a network (or tour), to create 3 sub-tours. Then the 7 different ways of reconnecting the network are analysed to find the optimum one. This process is then repeated for a different set of 3 connections, until all possible combinations have been tried in a network. A single execution of 3-opt has a time complexity of . Iterated 3-opt has a higher time complexity. This is the mechanism by which the 3-opt swap manipulates a given route: def reverse_segment_if_better(tour, i, j, k): """If reversing tour[i:j] would make the tour shorter, then do it.""" # Given tour [...A-B...C-D...E-F...] A, B, C, D, E, F = tour[i-1], tour[i], tour[j-1], tour[j], tour[k-1], tour[k % len(tour)] d0 = distance(A, B) + distance(C, D) + distance(E, F) d1 = distance(A, C) + distance(B, D) + distance(E, F) d2 = distance(A, B) + distance(C, E) + distance(D, F) d3 = distance(A, D) + distance(E, B) + distance(C, F) d4 = distance(F, B) + distance(C, D) + distance(E, A) if d0 > d1: tour[i:j] = reversed(tour[i:j]) return -d0 + d1 elif d0 > d2: tour[j:k] = reversed(tour[j:k]) return -d0 + d2 elif d0 > d4: tour[i:k] = reversed(tour[i:k]) return -d0 + d4 elif d0 > d3: tmp = tour[j:k] + tour[i:j] tour[i:k] = tmp return -d0 + d3 return 0 The principle is pretty simple. You compute the original distance and you compute the cost of each modification. If you find a better cost, apply the modification and return (relative cost).This is the complete 3-opt swap making use of the above mechanism: def three_opt(tour): """Iterative improvement based on 3 exchange.""" while True: delta = 0 for (a, b, c) in all_segments(len(tour)): delta += reverse_segment_if_better(tour, a, b, c) if delta >= 0: break return tourdef all_segments(n: int): """Generate all segments combinations""" return ((i, j, k) for i in range(n) for j in range(i + 2, n) for k in range(j + 2, n + (i > 0))) For the given tour, you generate all segments combinations and for each combinations, you try to improve the tour by reversing segments. While you find a better result, you restart the process, otherwise finish. (en)
gold:hypernym	Algorithm
prov:wasDerivedFrom	wikipedia-en:3-opt?oldid=1044566353&ns=0
page length (characters) of wiki page	4585 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:3-opt
is Link from a Wikipage to another Wikipage of	Travelling salesman problem Lin–Kernighan heuristic 2-opt
is foaf:primaryTopic of	wikipedia-en:3-opt

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (62 GB total memory, 38 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software