|
Автоматика и телемеханика, 1989, выпуск 10, страницы 131–139
(Mi at6447)
|
|
|
|
Моделирование поведения и интеллекта
Комбинаторная структура, обеспечивающая применимость метода динамического программирования
Н. В. Багоцкая, В. Е. Левит, И. С. Лосев Москва
Аннотация:
Вводится комбинаторная структура (фиброид), являющаяся обобщением матроида и структуры путей графа без ориентированных циклов. Описывается разветвленно-жадный алгоритм поиска оптимального множества (РЖ-алгоритм), частными случаями которого являются жадный алгоритм и алгоритм Форда поиска кратчайшего пути. Доказывается, что для класса допустимых функций, включающего в себя линейные функции, разветвленно-жадный алгоритм на фиброиде находит оптимальные решения. Показано, что при некоторых дополнительных предположениях из правильной работы РЖ-алгоритма на системе множеств для класса линейных функций следует, что эта система является фиброидом.
Поступила в редакцию: 01.08.1988
Образец цитирования:
Н. В. Багоцкая, В. Е. Левит, И. С. Лосев, “Комбинаторная структура, обеспечивающая применимость метода динамического программирования”, Автомат. и телемех., 1989, № 10, 131–139; Autom. Remote Control, 50:10 (1989), 1414–1420
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/at6447 https://www.mathnet.ru/rus/at/y1989/i10/p131
|
Статистика просмотров: |
Страница аннотации: | 134 | PDF полного текста: | 55 | Первая страница: | 2 |
|