- Tytuł:
-
Algorytm selekcji wykorzystujący teorię hipergrafów
A selection algorithm based on the hypergraph theory - Autorzy:
-
Stefanowicz, Ł.
Wiśniewski, R.
Adamski, M. - Powiązania:
- https://bibliotekanauki.pl/articles/152957.pdf
- Data publikacji:
- 2014
- Wydawca:
- Stowarzyszenie Inżynierów i Techników Mechaników Polskich
- Tematy:
-
selekcja
podsieci automatowe
implikanty proste
hipergraf
hipergraf transwersal dokładnych
transwersala
transwersala dokładna
selection
State Machine Components
SMCs
prime implicants
hypergraph
transversal
exact transversal - Opis:
-
Artykuł porusza kwestię selekcji określonych elementów zbioru z wykorzystaniem teorii hipergrafów. Przedstawiona została idea wspólnego algorytmu selekcji, w przypadku takich problemów, jak selekcja podsieci automatowych w dekompozycji sieci Petriego, a także selekcja implikantów prostych w procesie miminalizacji funkcji logicznych. Jako bazowy algorytm, wykorzystano metodę transwersal dokładnych, jednocześnie usprawniając ją o alternatywną scieżkę w przypadku, kiedy dany hipergraf selekcji nie należy do klasy hipergrafu transwersal dokładnych. Jak pokazują badania, metoda może być dobrą alternatywą obok wykorzystywanych metod tradycyjnych.
The paper deals with the selection problem based on the hypergraph theory. There is presented an idea of a common selection algorithm for selection of State Machine Components and Prime Implicants. The exact transversal method was used as a baseline algorithm. It was improved by supporting it with an optional path when a given selection hypergraph did not belong to the xt-class (class of the exact transversal hypergraph). In this case, the exact transversal was searched. When it was unsuccessful, the regular transversal was searched. The studies prove that the method allows obtaining the exact solution when the selection hypergraph does not belong to the xt-class, but has an exact transversal. The presented results show that a hypergraph which does not belong to the xt-class may have an exact transversal enabling obtaining a solution which would be as good as the one obtained with the backtracking method. The exact solution was also obtained with the use of an ordinary transversal, which de facto indicated that the regular transversals allowed, in certain cases, obtaining the exact solution. It seems to confirm the aptly determined class of solutions of the proposed improvements. In some cases, the solution contained one extra subnet, but in one tested case, the solution turned out to be much worse than the exact one. - Źródło:
-
Pomiary Automatyka Kontrola; 2014, R. 60, nr 7, 7; 516-518
0032-4140 - Pojawia się w:
- Pomiary Automatyka Kontrola
- Dostawca treści:
- Biblioteka Nauki
Artykuł