Back to search

Institutional Repository of Vilnius University

Euristiniai algoritmai NP-pilniems uždaviniams spręsti ir jų realizacija GRIDui /

Abstract

dc:description

The main goal of this work is to implement and test heuristic algorithms for GRID computing network to solve NP-complete problems. The problems of NP-complete set are not solved in polynomial time. To solve such problems, researchers have to use heuristic algorithms. Heuristic algorithms always give result in polynomial time, but it doesn’t mean that result is optimal, also computing time grows together with problem scope, and in this case bigger computing recourses are needed. Three popular heuristic algorithms are included in this works: genetic, simulated annealing and ant colony. All of them were implemented to solve traveling salesman problem in GRID computing network. With mentioned heuristic algorithms 20 TSP instances of TSPLIB library were solved. Experiential results shows that efficiently of heuristic algorithms are high and with 12 tested instances optimal solution was found. Author of this work recommends to use “DAG” type GRID tasks. Such type tasks allows to execute algorithms in different clusters at same time, so in same time researcher can execute a lot of tests and final test will give best results.

Degree

thesis:*
Grantor dc:publisher
Institutional Repository of Vilnius University
Year dc:date
2014

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Venckus, Irmantas,
Contributors dc:contributor
  • Žilinskas, Antanas

Rights

dc:rights
Statement dc:rights
  • info:eu-repo/semantics/openAccess
Language dc:language
lit

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Vilnius University
Base URL
epublications.vu.lt/oai
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Venckus, Irmantas,. Euristiniai algoritmai NP-pilniems uždaviniams spręsti ir jų realizacija GRIDui /. Institutional Repository of Vilnius University, 2014. https://repository.vu.lt/VU:ELABAETD2151429&prefLang=en_US