Рекуррентный метод решения задачи о назначениях
Предложен новый метод решения задачи о назначениях, основанный на рекурсивном получении ее оптимального решения. Задача о назначениях формулируется в перестановочно-матричной форме, что позволяет использовать матричный подход к построению оптимального решения. Алгоритм состоит в нахождении взвешенно...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2015 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/124933 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Рекуррентный метод решения задачи о назначениях / О.Б. Маций, А.В. Морозов, А.В. Панишев // Кибернетика и системный анализ. — 2015. — Т. 51, № 6. — С. 119-127. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-124933 |
|---|---|
| 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 |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Рекуррентный метод решения задачи о назначениях |
| spellingShingle |
Рекуррентный метод решения задачи о назначениях Маций, О.Б. Морозов, А.В. Панишев, А.В. Системный анализ |
| title_short |
Рекуррентный метод решения задачи о назначениях |
| title_full |
Рекуррентный метод решения задачи о назначениях |
| title_fullStr |
Рекуррентный метод решения задачи о назначениях |
| title_full_unstemmed |
Рекуррентный метод решения задачи о назначениях |
| title_sort |
рекуррентный метод решения задачи о назначениях |
| author |
Маций, О.Б. Морозов, А.В. Панишев, А.В. |
| author_facet |
Маций, О.Б. Морозов, А.В. Панишев, А.В. |
| topic |
Системный анализ |
| topic_facet |
Системный анализ |
| publishDate |
2015 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Рекурентний метод розв’язання задачі про призначення Recurrent method to solve the assignment problem |
| 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.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/124933 |
| citation_txt |
Рекуррентный метод решения задачи о назначениях / О.Б. Маций, А.В. Морозов, А.В. Панишев // Кибернетика и системный анализ. — 2015. — Т. 51, № 6. — С. 119-127. — Бібліогр.: 3 назв. — рос. |
| 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 |
| first_indexed |
2025-12-07T16:07:45Z |
| last_indexed |
2025-12-07T16:07:45Z |
| _version_ |
1850866312527478784 |