Wyniki wyszukiwania - BazTech

1

A genetic algorithm for the maximum 2-packing set problem

Trejo-Sánchez Joel Antonio, Fajardo-Delgado Daniel, Gutierrez-Garcia J. Octavio

International Journal of Applied Mathematics and Computer Science

|

2020

|

Vol. 30, no. 1

173--184

EN

Given an undirected connected graph G = (V, E), a subset of vertices S is a maximum 2-packing set if the number of edges in the shortest path between any pair of vertices in S is at least 3 and S has the maximum cardinality. In this paper, we present a genetic algorithm for the maximum 2-packing set problem on arbitrary graphs, which is an NP-hard problem. To the best of our knowledge, this work is a pioneering effort to tackle this problem for arbitrary graphs. For comparison, we extended and outperformed a well-known genetic algorithm originally designed for the maximum independent set problem. We also compared our genetic algorithm with a polynomial-time one for the maximum 2-packing set problem on cactus graphs. Empirical results show that our genetic algorithm is capable of finding 2-packing sets with a cardinality relatively close (or equal) to that of the maximum 2-packing sets. Moreover, the cardinality of the 2-packing sets found by our genetic algorithm increases linearly with the number of vertices and with a larger population and a larger number of generations. Furthermore, we provide a theoretical proof demonstrating that our genetic algorithm increases the fitness for each candidate solution when certain conditions are met.

2

Wybrane algorytmy grafowe w analizie czasowej przedsięwzięć budowlanych

Jakubowski G.

Materiały Budowlane

|

2016

|

nr 6

34--36

PL

W artykule przedstawiono istotę i sposób wykorzystania opracowanego modelu realizacji przedsięwzięcia budowlanego oraz algorytmu przeszukiwania w głąb i algorytmu sortowania topologicznego w analizie czasowej przedsięwzięć budowlanych. Prezentowane algorytmy zapisano w pseudokodzie oraz zilustrowano przykładem obliczeniowym w Microsoft Excel i VBA.

EN

The paper presents the essence and the use of elaborated model of construction projects, depth first search algorithm and topological sorting algorithm in the time analysis of constructions projects realization. Presented algorithms written in pseudo-code and illustrated with examples in Microsoft Excel and VBA.

3

Polioptymalizacja transportu odpadów z wykorzystaniem planarnych, parametryzowanych grafów topologicznych

Gaska K., Generowicz A., Iwanicka Z., Kozioł M., Ścierski W., Landrat M.

Logistyka

|

2014

|

nr 6

3780--3792

PL

Zintegrowany system gospodarki odpadami stanowi złożony zbiór obiektów, procesów technologicznych, logistycznych i relacji zachodzących między nimi. Jednym z kluczowych elementów systemu są procesy transportu, determinujące m.in. przepływ strumieni odpadów ze źródeł ich powstawania do miejsc przetwarzania i unieszkodliwiania. Dynamika zmian w ruchu drogowym, w tym zróżnicowane technologie napędu i paliw oraz zmienność sytuacji w eksploatacji pojazdów powoduje wzrost kosztów, których znaczący udział w sumarycznych kosztach systemu gospodarki odpadami skłania do podjęcia działań optymalizacji szeregu parametrów determinujących wartości poszczególnych składników kosztów (stałych i zmiennych). Optymalizacja procesu transportu wymaga podejścia dualnego, wynikającego z ograniczenia kosztów procesów cząstkowych przy jednoczesnym spełnieniu wymagań w zakresie ochrony środowiska oraz bezpieczeństwa życia i zdrowia ludzi. Artykuł przedstawia metodologię optymalizacji procesów transportowych w zintegrowanych systemach gospodarki odpadami, z wykorzystaniem modelu komponentowego parametryzowanych grafów topologicznych.

EN

Integrated waste management system is a complex set of objects, technological processes logistics and relations between them. One of the crucial elements of the system are the processes of transport, determining among other the flow of waste streams from sources to destinations of their formation processing and disposal. Dynamics of changes in traffic, including different propulsion technologies and fuels, and the volatility of the situation in vehicle operating cost increases, the significant share of the aggregated costs of waste management system tends to take action to optimize a number of parameters that determine the value of the individual components of costs (fixed and variable). Optimization of the transport process requires a dual approach, resulting from the reduction of the cost of the partial processes while meeting the requirements of environmental protection and safety of human life and health. This article presents a methodology to optimize transport processes in integrated waste management systems using a model parameterized component topological graphs.

4

Planowanie trasy statku. Trasa najkrótsza, najszybsza czy może najlepsza?

Neumann T.

Logistyka

|

2014

|

nr 3

4615--4619

PL

W artykule przedstawiono ogólną charakterystykę planowania morskiej trasy statku. Planowanie trasy jest zadaniem optymalizacyjnym mogącym polegać na wyznaczeniu kolejno po sobie występujących punktów zwrotu. Problematyką podobną do tej znaleźć moŜna w wielu pracach informatycznych, których zadaniem jest znalezienie najkrótszej drogi pomiędzy dwoma punktami. W artykule przedstawiono ogólny zarys problemu określania najkrótszej trasy w algorytmie grafowym, mrówkowym oraz pszczelim.

EN

The paper presents the general characteristics of the sea voyage planning. Travel planning is the task of optimization which consists in determining the succession occurring return points. Issues similar to this problem can be found in many works of informatics technology, where the main goal is to find the shortest path between two points. The article presents an overview of the problem of determining the shortest path graphs algorithm, ant algorithm and bees algorithm.

5

O kodowaniu struktury drzewa oznaczonego postaci pary liczb naturalnych

Palka Z.

Wiadomości Matematyczne

|

2011

|

T. 47, Nr 2

157--165

6

Detecting surfaces of minimal cut - a graph theoretical approach

Tabor Z.

Inżynieria Materiałowa

|

2008

|

Vol. 29, nr 4

439-442

EN

In the study an algorithm localizing surfaces of minimal cuts within gray-level volumetric images of porous structures is introduced. A two-stage algorithm consists of identifying the typical intensity, corresponding to the background (void) phase and then finding an optimal cut in a properly constructed graph. It is conjectured that the minimal cut surface can provide information about the region in which deformation can localize during mechanical loading. Finite element simulations are presented to support such conjecture.

PL

W pracy przedstawiono algorytm znajdujący powierzchnie minimalnego cięcia w obrazach struktur porowatych. Zaprezentowany algorytm może być użyty do analizy zarówno obrazów binarnych jak i obrazów w skali szarości, dwu- i trójwymiarowych. Algorytm w pierwszym kroku identyfikuje typową intensywność odpowiadającą tłu, a następnie po odpowiednim prze skalowaniu odcieni szarości znajduje minimalne cięcie w obrazie, interpretowanym jako graf ważony. Powierzchnia minimalnego cięcia może dawać informację o obszarze w którym zlokalizuje się deformacja w trakcie mechanicznego obciążania badanej struktury.

7

Ulepszony algorytm poszukiwania grafów o całkowitym spektrum w wielkich zbiorach grafów

Niwińska M.

Studia z Automatyki i Informatyki

|

2005

|

T. 30

95--100

PL

Graf jest nazywany całkowitym, jeżeli wszystkie wartości własne należące do spektrum jego macierzy przyległości są liczbami całkowitymi. Rozważa się problem wyszukiwania spójnych grafów całkowitych w wielkich zbiorach grafów o danej liczbie wierzchołków i krawędzi. Proponuje się algorytm cgen1(n, k) generowania grafów o n wierzchołkach i o k krawędziach oraz dwustopniowego sprawdzania, czy dany graf jest całkowity. Ocenia się jego przydatność do znalezienia wszystkich spójnych grafów całkowitych na 13 wierzchołkach.

EN

A graph is called integral if the spectrum of its adjacency matrix consists of integers. A problem of finding all connected integral graphs in huge sets of graphs of order n and size k is considered. An improved algorithm cgen1(n, k) for generating these graphs is proposed. Its usefulness for finding all connected integral graphs on 13 vertices is tested.

8

Heurystyczny algorytm projektowania sieci elektroenergetycznej typu drzewo Steinera

Schiff K.

Elektrotechnika i Elektronika

|

2001

|

T. 20, z. 2

97--99

PL

W artykule tym zaprezentowano algorytm wyznaczania drzewa Steinera о złożoności obliczeniowej rzędu О(n3) bazujący na algorytmie Warshalla-Floyda wyznaczania najkrótszych ścieżek pomiędzy wszystkimi wierzchołkami grafu i nа algorytmie Sollina rozpinania drzewa о minimalnej wadze nа wierzchołkach grafu. Pojęcie punktów Steinera zostało jednak zmodyfikowane, gdyż w ich skład oprócz wierzchołków, które muszą znaleźć się w rozwiązaniu, dołączono w trakcie działania algorytmu wierzchołki, którе nie musiały znaleźć się w rozwiązaniu zgodnie z początkowymi założeniami.

EN

In this paper algorithm for Steineг tree network design with time complexity О(n3) is presented, which is based оn Warshall—Floyd shortes path algorithms and Sollin spaning trees algorithms, but the notion of Steiner point is modificated.

9

Dynamic flows with supply and demand

Ciurea E.

Control and Cybernetics

|

2000

|

Vol. 29, no 4

895-903

EN

We are given a network G = (N, A, h, c) with node set N, arc set A, time function h, capacity function c, and P the set of periods, s the source and s' the sink of the network G. Associated with s, there is a non-negative real number q(t) called the supply of source s at time t, and with s' - a nonnegative real number q'(t) called the demand of sink s' at time t, t [belongs to] P. The objective is to determine the existence of a dynamic flow in G for p periods, so that the demands at sink s' can be fulfilled from the supplies at the source s. A numerical example is presented.