Рекуррентный метод решения задачи о назначениях
Предложен новый метод решения задачи о назначениях, основанный на рекурсивном получении ее оптимального решения. Задача о назначениях формулируется в перестановочно-матричной форме, что позволяет использовать матричный подход к построению оптимального решения. Алгоритм состоит в нахождении взвешенно...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2015 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/124933 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Рекуррентный метод решения задачи о назначениях / О.Б. Маций, А.В. Морозов, А.В. Панишев // Кибернетика и системный анализ. — 2015. — Т. 51, № 6. — С. 119-127. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862687994921615360 |
|---|---|
| author | Маций, О.Б. Морозов, А.В. Панишев, А.В. |
| author_facet | Маций, О.Б. Морозов, А.В. Панишев, А.В. |
| citation_txt | Рекуррентный метод решения задачи о назначениях / О.Б. Маций, А.В. Морозов, А.В. Панишев // Кибернетика и системный анализ. — 2015. — Т. 51, № 6. — С. 119-127. — Бібліогр.: 3 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Предложен новый метод решения задачи о назначениях, основанный на рекурсивном получении ее оптимального решения. Задача о назначениях формулируется в перестановочно-матричной форме, что позволяет использовать матричный подход к построению оптимального решения. Алгоритм состоит в нахождении взвешенного паросочетания минимального суммарного веса в двудольном графе с 2n вершинами. Вычислительная схема рекуррентного метода решения задачи о назначениях представлена в форме, удобной для реализации на ЭВМ.
Запропоновано новий метод розв’язання задачі про призначення, що ґрунтується на рекурсивному одержанні її оптимального розв’язку. Задача про призначення формулюється в перестановочно-матричной формі, що дає можливість використовувати матричний підхід до побудови оптимального розв’язку. Алгоритм полягає у знаходженні зваженого паросполучення мінімальної сумарної ваги у двочастковому графі з 2n вершинами. Обчислювальну схему рекурентного методу розв’язання задачі про призначення представлено у формі, зручній для реалізації на ЕОМ.
The paper proposes a new method to solve the assignment problem based on recursive derivation of the optimal solution. The assignment problem is formulated in the rearrangement matrix form that allows the use of the matrix approach to optimal solution. The algorithm is to find the minimum total weight matching in the bipartite graph with 2n vertices. The computational scheme of the recurrence method for solving the assignment problem is presented in the form adapted for implementation on a computer.
|
| first_indexed | 2025-12-07T16:07:45Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-124933 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T16:07:45Z |
| publishDate | 2015 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Маций, О.Б. Морозов, А.В. Панишев, А.В. 2017-10-12T09:09:48Z 2017-10-12T09:09:48Z 2015 Рекуррентный метод решения задачи о назначениях / О.Б. Маций, А.В. Морозов, А.В. Панишев // Кибернетика и системный анализ. — 2015. — Т. 51, № 6. — С. 119-127. — Бібліогр.: 3 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/124933 519.161 Предложен новый метод решения задачи о назначениях, основанный на рекурсивном получении ее оптимального решения. Задача о назначениях формулируется в перестановочно-матричной форме, что позволяет использовать матричный подход к построению оптимального решения. Алгоритм состоит в нахождении взвешенного паросочетания минимального суммарного веса в двудольном графе с 2n вершинами. Вычислительная схема рекуррентного метода решения задачи о назначениях представлена в форме, удобной для реализации на ЭВМ. Запропоновано новий метод розв’язання задачі про призначення, що ґрунтується на рекурсивному одержанні її оптимального розв’язку. Задача про призначення формулюється в перестановочно-матричной формі, що дає можливість використовувати матричний підхід до побудови оптимального розв’язку. Алгоритм полягає у знаходженні зваженого паросполучення мінімальної сумарної ваги у двочастковому графі з 2n вершинами. Обчислювальну схему рекурентного методу розв’язання задачі про призначення представлено у формі, зручній для реалізації на ЕОМ. The paper proposes a new method to solve the assignment problem based on recursive derivation of the optimal solution. The assignment problem is formulated in the rearrangement matrix form that allows the use of the matrix approach to optimal solution. The algorithm is to find the minimum total weight matching in the bipartite graph with 2n vertices. The computational scheme of the recurrence method for solving the assignment problem is presented in the form adapted for implementation on a computer. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Рекуррентный метод решения задачи о назначениях Рекурентний метод розв’язання задачі про призначення Recurrent method to solve the assignment problem Article published earlier |
| spellingShingle | Рекуррентный метод решения задачи о назначениях Маций, О.Б. Морозов, А.В. Панишев, А.В. Системный анализ |
| title | Рекуррентный метод решения задачи о назначениях |
| title_alt | Рекурентний метод розв’язання задачі про призначення Recurrent method to solve the assignment problem |
| title_full | Рекуррентный метод решения задачи о назначениях |
| title_fullStr | Рекуррентный метод решения задачи о назначениях |
| title_full_unstemmed | Рекуррентный метод решения задачи о назначениях |
| title_short | Рекуррентный метод решения задачи о назначениях |
| title_sort | рекуррентный метод решения задачи о назначениях |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/124933 |
| work_keys_str_mv | AT maciiob rekurrentnyimetodrešeniâzadačionaznačeniâh AT morozovav rekurrentnyimetodrešeniâzadačionaznačeniâh AT paniševav rekurrentnyimetodrešeniâzadačionaznačeniâh AT maciiob rekurentniimetodrozvâzannâzadačípropriznačennâ AT morozovav rekurentniimetodrozvâzannâzadačípropriznačennâ AT paniševav rekurentniimetodrozvâzannâzadačípropriznačennâ AT maciiob recurrentmethodtosolvetheassignmentproblem AT morozovav recurrentmethodtosolvetheassignmentproblem AT paniševav recurrentmethodtosolvetheassignmentproblem |