Browsing by Subject "dynamic programming"

Now showing 1 - 6 of 6

Access status: Open Access ,
A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences
(Wydawnictwa AGH, 2025) Ziemann, Radosław; Żyliński, Paweł
We provide a linear time algorithm for determining the sets of vertices that belong to all, some and no minimum dominating sets of a tree, respectively, thus improving the quadratic time algorithm of Benecke and Mynhardt in 2008 [S. Benecke, C.M. Mynhardt, Trees with domination subdivision number one, Australas. J. Comb. 42 (2008), 201-209]. Some algorithmic consequences are also discussed.
Access status: Open Access ,
Dynamic programming approach to structural optimization problem - numerical algorithm
(2014) Fulmański, Piotr; Nowakowski, Andrzej; Pustelnik, Jan
In this paper a new shape optimization algorithm is presented. As a model application we consider state problems related to fluid mechanics, namely the Navier-Stokes equations for viscous incompressible fluids. The general approach to the problem is described. Next, transformations to classical optimal control problems are presented. Then, the dynamic programming approach is used and sufficient conditions for the shape optimization problem are given. A new numerical method to find the approximate value function is developed.
Access status: Open Access ,
Memoization method for storing of minimum-weight triangulation of a convex polygon
(Wydawnictwa AGH, 2019) Selimi, Aybeyan; Krrabaj, Samedin; Saračević, Muzafer; Pepić, Selver
This study presents a practical view of dynamic programming, specifically in the context of the application of finding the optimal solutions for the polygon triangulation problem. The problem of the optimal triangulation of polygon is considered to be as a recursive substructure. The basic idea of the constructed method lies in finding to an adequate way for a rapid generation of optimal triangulations and storing - them in as small as possible memory space. The upgraded method is based on a memoization technique, and its emphasis is in storing the results of the calculated values and returning the cached result when the same values again occur. The significance of the method is in the generation of the optimal triangulation for a large number of n. All the calculated weights in the triangulation process are stored and performed in the same table. Results processing and implementation of the method was carried out in the Java environment and the experimental results were compared with the square matrix and Hurtado-Noy method.
Access status: Restricted ,
Metoda programowania dynamicznego dla wielowymiarowej macierzy stanów i decyzji
(Data obrony: 2018-09-10) Cebula, Maciej
Wydział Elektrotechniki, Automatyki, Informatyki i Inżynierii Biomedycznej
Access status: Open Access ,
Simulation-based sailboat trajectory optimization using on-board heterogeneous computers
(Wydawnictwa AGH, 2016) Dębski, Roman
A dynamic programming-based algorithm adapted to on-board heterogeneous computers for simulation-based trajectory optimization was studied in the context of high-performance sailing. The algorithm can efficiently utilize all OpenCL-capable devices, starting the computation (if necessary, in singleprecision) on a GPU and finalizing it (if necessary, in double-precision) with the use of a CPU. The serial and parallel versions of the algorithm are presented in detail. Possible extensions of the basic algorithm are also described. The experimental results show that contemporary heterogeneous on-board/mobile computers can be treated as micro HPC platforms. They offer high performance (the OpenCL-capable GPU was found to accelerate the optimization routine 41 fold) while remaining energy and cost efficient. The simulation-based approach has the potential to give very accurate results, as the mathematical model upon which the simulator is based may be as complex as required. The black-box represented performance measure and the use of OpenCL make the presented approach applicable to many trajectory optimization problems.
Access status: Restricted ,
Zastosowanie twierdzenia Brussa do wybranych problemów optymalnego stopowania
(Data obrony: 2014-09-30) Juroszek, Magdalena
Wydział Matematyki Stosowanej