|
Avtomatika i Telemekhanika, 1989, Issue 10, Pages 131–139
(Mi at6447)
|
|
|
|
Simulation of Behavior and Intelligence
On one generalization of the matroid ensuring applicability of the dynamic programming method
N. V. Bagotskaya, V. Y. Levit, I. S. Losev Moscow
Abstract:
A combinatorial structure (fibroid) is introduced which is a generalization of the matroid and structure of paths in a graph without oriented cycles. A bifurcation-greedy (BG) algorithm is described for search for an optimal set whose particular cases are the greedy algorithm and the Ford algorithm for search for the shortest path. For the class of feasible functions which includes linear functions, the BG-algorithm finds optimal solutions on the fibroid. With some additional assumptions correct operation of the BG-algorithm on a system of sets for a class of linear functions is evidence that the system is a fibroid.
Received: 01.08.1988
Citation:
N. V. Bagotskaya, V. Y. Levit, I. S. Losev, “On one generalization of the matroid ensuring applicability of the dynamic programming method”, Avtomat. i Telemekh., 1989, no. 10, 131–139; Autom. Remote Control, 50:10 (1989), 1414–1420
Linking options:
https://www.mathnet.ru/eng/at6447 https://www.mathnet.ru/eng/at/y1989/i10/p131
|
Statistics & downloads: |
Abstract page: | 124 | Full-text PDF : | 48 | First page: | 2 |
|