Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: set covering problem

Sortuj według:

Ogranicz wyniki do:

Solving sweeping problem for trees in graph theory

Niwanthi W. A. L., Panditharathne H. D., Perera S. S. N.

Computer Science and Mathematical Modelling

2023

No. 17

29--33

We develop a theory to determine the search number of a graph that allows us to detect an intruder along an edge without limiting the visibility of adjacent vertices. The presented technique here will allow to express the sweep problem as a linear program using an existing formulation of a linear program designed for problems where capture occurs only at a vertex of a graph. We also provide a method to solve the sweep problem for any complex tree, utilizing a set of sub-trees of the tree.

Opracowano teorię wyznaczania liczby przeszukiwań grafu, która pozwala wykryć intruza wzdłuż krawędzi bez ograniczania widoczności sąsiednich wierzchołków. Przedstawiona technika pozwoli wyrazić problem przeczesywania grafu w postaci zadania programowania liniowego, wykorzystując istniejące sformułowanie programu liniowego przeznaczonego dla problemów, w których przechwytywanie następuje tylko w wierzchołku grafu. Przedstawiono również metodę rozwiązywania problemu przeczesywania dla dowolnego złożonego drzewa, wykorzystując zestaw poddrzew drzewa.

Ant colony optimization algorithm for the set covering problem

Schiff K.

Czasopismo Techniczne. Automatyka

2013

R. 110, z. 1-AC

39--52

This article describes a new hybrid ant colony optimization algorithms for the set covering problem. The problem is modeled by means of a bipartite graph. New heuristic patterns, which are used in order to choose a vertex to a created covering set have been incorporated into modified hybrid algorithms. Results of tests on investigated algorithms are discussed.

W artykule przedstawiono nowy hybrydowy algorytm mrówkowy dla problemu zagadnienia pokrycia zbioru o minimalnym koszcie. Problem jest zamodelowany za pomocą grafu dwudzielnego. W modyfikowanym algorytmie wprowadzono nową heurystykę wyboru wierzchołków do podzbioru wierzchołków pokrywających. Opracowany algorytm przetestowano i porównano, a wyniki tych badań omówiono.