Изменения

Перейти к: навигация, поиск

Алгоритм построения базы в объединении матроидов

683 байта добавлено, 19:59, 21 октября 2018
Алгоритм
То есть шаг жадного алгоритма заключается в создании нового <tex>D</tex> и поиске такого пути.
== Псевдокод ==
<tex>J</tex> = <tex>\emptyset</tex>
isMaximal = ''false''
'''while''' '''not''' isMaximal
построить [[Граф замен для двух матроидов|граф замен]] <tex>D_{M_1, M_2}(J)</tex>
<tex>X_1 \leftarrow \{ z \in S \setminus J \mid J + z \in \mathcal{I}_1 \}</tex>
<tex>X_2 \leftarrow \{ z \in S \setminus J \mid J + z \in \mathcal{I}_2 \}</tex>
<tex>P</tex> <tex>\leftarrow</tex> кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex>
'''if''' <tex>P \ne \emptyset</tex>
<tex>J</tex> = <tex>J \bigtriangleup V(P)</tex>
'''else'''
isMaximal = ''true''
Анонимный участник

Навигация