About: Usage of the extremal algebra in solving the travelling salesman problem

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Usage of the extremal algebra in solving the travelling salesman problem Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	This article compares many ways of solving the traveling salesman problem. At first classical heuristic methods and methods using graph theory are mentioned. At the first part many universal methods are described, which can be also used in other transportation problems. The traveling salesman problem is solved by using genetic algorithm in the second part of this article. This algorithm generates at the beginning the first generation, chooses five thousand parents by the roulette method, crosses these pairs and determines the next generation. This process continues with next generations until stabilization. The algorithm is demonstrated on two examples. At the final part extremal algebras, max-plus algebra and max-min algebra, are defined and illustrated by examples. Monge matrices and some their properties are described in these algebras. The optimization of the traveling salesman problem, which leads to a reduction of the computation complexity, is described for these matrices. The optimization is solved at first for the classical case and then for the matrices that satisfy the strict Monge property. Matrices with the strict Monge property lead to the linear complexity of the problem. This article compares many ways of solving the traveling salesman problem. At first classical heuristic methods and methods using graph theory are mentioned. At the first part many universal methods are described, which can be also used in other transportation problems. The traveling salesman problem is solved by using genetic algorithm in the second part of this article. This algorithm generates at the beginning the first generation, chooses five thousand parents by the roulette method, crosses these pairs and determines the next generation. This process continues with next generations until stabilization. The algorithm is demonstrated on two examples. At the final part extremal algebras, max-plus algebra and max-min algebra, are defined and illustrated by examples. Monge matrices and some their properties are described in these algebras. The optimization of the traveling salesman problem, which leads to a reduction of the computation complexity, is described for these matrices. The optimization is solved at first for the classical case and then for the matrices that satisfy the strict Monge property. Matrices with the strict Monge property lead to the linear complexity of the problem. (en)
Title	Usage of the extremal algebra in solving the travelling salesman problem Usage of the extremal algebra in solving the travelling salesman problem (en)
skos:prefLabel	Usage of the extremal algebra in solving the travelling salesman problem Usage of the extremal algebra in solving the travelling salesman problem (en)
skos:notation	RIV/62690094:18450/12:50001880!RIV14-MSM-18450___
http://linked.open...avai/riv/aktivita	O
http://linked.open...avai/riv/aktivity	O
http://linked.open...vai/riv/dodaniDat	2014
http://linked.open...aciTvurceVysledku	Pozdílková, Alena Cimler, Richard
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Hradec Králové / Fakulta informatiky a managementu
http://linked.open...dnocenehoVysledku	176289
http://linked.open...ai/riv/idVysledku	RIV/62690094:18450/12:50001880
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	genetic algorithm; travelling salesman problém; max-min algebra; max-plus algebra; Monge matrix (en)
http://linked.open.../riv/klicoveSlovo	Monge matrix genetic algorithm max-min algebra max-plus algebra travelling salesman problém
http://linked.open...ontrolniKodProRIV	[B358D907ADFB]
http://linked.open...v/mistoKonaniAkce	Karviná
http://linked.open...i/riv/mistoVydani	Karviná
http://linked.open...i/riv/nazevZdroje	Mathematical methods in economics : proceedings of 30th international conference
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...UplatneniVysledku	2012
http://linked.open...iv/tvurceVysledku	Pozdílková, Alena Cimler, Richard
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open...ain/vavai/riv/wos	000316715900126
http://linked.open.../riv/zahajeniAkce	2012-01-11 (xsd:date)
number of pages	6 (xsd:int)
http://purl.org/ne...btex#hasPublisher	Slezská univerzita. Obchodně podnikatelská fakulta
https://schema.org/isbn	978-80-7248-779-0
http://localhost/t...ganizacniJednotka	18450

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 48 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software