Detail publikace

Stochastické heuristiky pro problémy batohu

ŠEDA, M. ŠEDA, P.

Český název

Stochastické heuristiky pro problémy batohu

Anglický název

Stochastic Heuristics for Knapsack Problems

Typ

článek v časopise ve Scopus, Jsc

Jazyk

en

Originální abstrakt

In this paper, we introduce knapsack problem formulations, discuss their time complexity and propose their representation and solution based on the instance size. First, deterministic methods are briefly summarized. They can be applied to small-size tasks with a single constraint. However, because of NP-completeness of the problem, more complex problem instances must be solved by means of heuristic techniques to achieve an approximation of the exact solution in a reasonable amount of time. The problem representations and parameter settings for a genetic algorithm and simulated annealing frameworks are shown.

Český abstrakt

V tomto příspěvku jsou představeny formulace verzí problému batohu, je diskutována jejich časová složitost a navrženo řešeno v závislosti na velikosti instance. V úvodu jsou stručně shrnuty deterministické metody. Ty mohou být aplikovány na úlohy malého rozsahu s jením omezením. Avšak vzhledem k NP-úplnosti problému instance většího rozsahu je nutné řešit pomocí heuristických metod, aby bylo možné získat aproximaci řešení v dostupném čase. V příspěvku je prezentována reprezentace problémů a nastavení parametrů pro genetický algoritmus a simulované žíhání.

Anglický abstrakt

In this paper, we introduce knapsack problem formulations, discuss their time complexity and propose their representation and solution based on the instance size. First, deterministic methods are briefly summarized. They can be applied to small-size tasks with a single constraint. However, because of NP-completeness of the problem, more complex problem instances must be solved by means of heuristic techniques to achieve an approximation of the exact solution in a reasonable amount of time. The problem representations and parameter settings for a genetic algorithm and simulated annealing frameworks are shown.

Klíčová slova česky

problém batohu, dynamické programování, metoda větví a mezí, genetický algoritmus, simulované žéhání

Klíčová slova anglicky

knapsack problem, dynamic programming, branch and bound method, heuristic, genetic algorithm, simulated annealing

Vydáno

05.08.2018

Nakladatel

Springer-Verlag

Místo

Berlin

ISSN

2194-5357

Ročník

837

Číslo

1

Strany od–do

157–166

Počet stran

10

BIBTEX


@article{BUT149171,
  author="Miloš {Šeda} and Pavel {Šeda},
  title="Stochastic Heuristics for Knapsack Problems",
  year="2018",
  volume="837",
  number="1",
  month="August",
  pages="157--166",
  publisher="Springer-Verlag",
  address="Berlin",
  issn="2194-5357"
}