Тип публикации: доклад, тезисы доклада, статья из сборника материалов конференций
Конференция: Hybrid Methods of Modeling and Optimization in Complex Systems (HMMOCS-III 2024); Krasnoyarsk; Krasnoyarsk
Год издания: 2025
Идентификатор DOI: 10.1051/itmconf/20257201001
Аннотация: Dynamic programming (DP) is a powerful algorithmic technique for solving optimization problems by breaking them down into simpler subproblems. This paper presents an implementation of DP algorithms for two classic optimization problems: the Knapsack problem and the Traveling Salesman Problem (TSP). The solutions are developed and dПоказать полностьюemonstrated using the Mathematica® programming language. For the Knapsack problem, we present two variants: with and without item repetition. The paper describes the mathematical formulation of each variant and provides detailed Mathematica code for their implementation. Examples are given to illustrate the effectiveness of the algorithms in finding optimal solutions. The TSP implementation demonstrates how DP can be applied to find the shortest Hamiltonian contour in a given network. The paper outlines the mathematical model, recurrent formula, and step-by-step solution process. An example with a four-node network is provided to showcase the algorithm's application. This work highlights the versatility of dynamic programming in solving complex optimization problems and demonstrates the effectiveness of Mathematica as a tool for implementing and visualizing these solutions. The presented algorithms and code snippets serve as valuable resources for researchers and practitioners working on similar optimization challenges.
Журнал: ITM Web of Conferences
Номера страниц: 1001
Место издания: Krasnoyarsk