Вісники та науково-технічні збірники, журнали
Permanent URI for this communityhttps://ena.lpnu.ua/handle/ntb/12
Browse
6 results
Search Results
Item Ігрова самоорганізація гамільтонового циклу графа(Видавництво Львівської політехніки, 2021-03-01) Кравець, Петро; Пасічник, Володимир Володимирович; Проданюк, Микола; Kravets, Petro; Pasichnyk, Volodymyr; Prodaniuk, Mykola; Національний університет “Львівська політехніка”; Lviv Polytechnic National UniversityУ роботі запропоновано нове застосування моделі стохастичної гри для розв’язування задачі самоорганізації гамільтонового циклу графа. Для цього у вершинах неорієнтованого графа розміщено ігрових агентів, чисті стратегії яких є варіантами вибору одного із інцидентних ребер. Випадковий вибір стратегій усіма агентами утворює набір локальних шляхів, що розпочинаються у кожній вершині графа. Поточні платежі гравців визначено як функції програшів, залежні від стратегій сусідніх гравців, які контролюють суміжні вершини графа. Ці функції сформовано зі штрафу за вибір протилежних стратегій сусідніми гравцями та штрафу за стратегії, які призвели до зменшення довжини локального шляху. Випадковий вибір чистих стратегії гравців спрямовано на мінімізацію їх функцій середніх програшів. Генерування послідовностей чистих стратегій виконано за дискретним розподілом, побудованим на основі динамічних векторів змішаних стратегій. Елементи векторів змішаних стратегій є імовірностями вибору відповідних чистих стратегій, які адаптивно враховують значення поточних програшів. Формування векторів змішаних стратегій визначено за марковським рекурентним методом, для побудови якого використано градієнтний метод стохастичної апроксимації. У ході гри метод збільшує значення імовірностей вибору тих чистих стратегій, які призводять до зменшення функцій середніх програшів. Для заданих способів формування поточних платежів результатом стохастичної гри є утворення патернів самоорганізації у вигляді циклічно зорієнтованих стратегій ігрових агентів. Умови збіжності рекурентного методу до колективно оптимальних розв’язків забезпечено дотриманням фундаментальних умов стохастичної апроксимації. Виконано розширення ігрової задачі на випадкові графи. Для цього вершинам приписано імовірності відновлювальних відмов, які спричиняють зміну структури графа на кожному кроці гри. Реалізації випадкового графа адаптивно враховуються під час пошуку гамільтонових циклів. Збільшення імовірності відмов сповільнює збіжність стохастичної гри. Комп’ютерне моделювання стохастичної гри забезпечило отримання патернів самоорганізації стратегій агентів у вигляді декількох локальних циклів або глобального гамільтонового циклу графа залежно від способів формування поточних програшів гравців. Достовірність експериментальних досліджень підтверджено повторенням реалізацій патернів самоорганізації для різних послідовностей випадкових величин. Результати дослідження можна використати на практиці для ігрового розв’язування NPскладних задач, транспортних і комунікаційних задач, для побудови протоколів автентифікації у розподілених інформаційних системах, для колективного прийняття рішень в умовах невизначеності.Item Методи та засоби розвитку територіальної громади в напрямку ремонту доріг(Видавництво Львівської політехніки, 2018-02 26) Литвин, В. В.; Рибчак, З. Л.; Завущак, І. І.; Lytvyn, Vasyl; Rybchak, Zoriana; Zavuschak, Iryna; Національний університет “Львівська політехніка”; Lviv Polytechnic National UniversityУ статті розглянуто моделювання ремонту доріг територіальної громади за наявності коштів та залежно від стану доріг. Для моделювання запропоновано використати метод пошуку мінімального кістякового дерева на основі модифікації алгоритму Пріма. Наведено приклади використання запропонованого підходу в межах Ходорівської територіальної громади.Item Алгоритми мінімізації сумарного запізнювання робіт на одиночному пристрої на основі визначення найкоротшого Гамільтонового шляху в графі та правил домінування(Видавництво Львівської політехніки, 2013) Мінухін, С.Запропоновано метод мінімізації сумарного запізнювання на одиночному пристрої на основі визначення найкоротшого гамільтонового шляху в довільному графі та алгоритми його реалізації з використанням правил домінування, які покращують їх ефективність та не зменшують час виконання. Запропоновано метрики для оцінки ефективності використання правил домінування. Наведені результати експериментальних досліджень алгоритмів, які обґрунтовують ефективність пропонованої модифікації за рахунок отримання локальних оптимальних рішень. The paper proposes a method, algorithms and its implementations using dominance rules for minimizing the total tardiness on a single device-based on shortest Hamiltonian path in a arbitrary graph that improve the efficiency and not reduce the execution time. Metrics for evaluating the effectiveness of the dominance rules are proposed. The experimental results ofalgorithms are developed that justify the effectiveness of the proposed modifications by getting local optimal solutions during procedure.Item Методи оптимізації фізичної та логічної структур телекомунікаційних мереж(Видавництво Львівської політехніки, 2013) Бугиль, Б. А.; Лаврів, О. А.; Бешлей, М. І.; Червенець, В. В.The article deals with reasons why the planned network resource is not used completely. The main attention is paid to the dynamic routing protocol, which does not consider the current load of local network segments according to the principle of its functioning. In the paper local segments loading considers with existence of a constant flow to reduce the computational complexity of the proposed method. The method is proposed in the work to maximize the use of network resources and resource allocation improving based on alternative routes variation through less loaded local segment. The proposed method implemented as a simulation model in Matlab. It allows making decision on routes variation based on introduced efficiency index for resource allocation. The article shows results of two experiments on the proposed method to determine its adequacy. The task of the first experiment is to determine the effectiveness of the method to vary the network resources allocation for simple network structure. The second experiment compares the value of efficiency index for resource allocation with load balancing according to the protocol EIGRP and the one with route replacement. The proposed method replaces dynamically defined routes to alternative that maximizes the efficient use of shared network resource. The major factors influencing the effectiveness of a network resource handling is a network physical or logical structure. It depends on the number of edges in the network topology. Physical structure forms when designing the network in the future does not undergo significant modifications, so the paper proposes a method of physical structure selecting that will provide the highest flows service quality for a given number of nodes and edges. Physical structure redundancy increases with connectivity increasing, leading to a set of possible logical structures. Formation of these logical structures provides routing policies in the network. In this paper, we propose a comprehensive method of physical and logical structures selection, which provides the most effective use of network resources to ensure a high level of flows service quality. Routing protocols operation depends on the network physical structure, because it has to form the best logical structure. The criterions of logical structure effectiveness are the QoS parameters for transmitting flows. The main disadvantage of dynamic routing protocols is that the selection of the optimal route bases on mono-criterion metric does not considers all the network features and causes an ineffective use of network resources. At present, the only way to control the network resources allocation during the routing process is traffic balancing. It means that all equivalent routes are uses, through which you can reach the recipient. Проведено аналіз та обґрунтування чинників, що впливають на особливості використання мережевого ресурсу, закладеного у процесі проектування телекомунікаційної мережі. Кількість ребер у топології мережі є основним фактором, що характеризує вплив фізичної та логічної структур на ефективність використання мережевого ресурсу. Запропоновано метод вибору фізичної структури, яка забезпечить максимальну якість сервісу потокам при заданій кількості вузлів і ребер. Для забезпечення балансу потоків розроблено метод модифікації логічної структури, що ґрунтується на пошуку альтернативних шляхів через найменш завантажені локальні сегменти телекомунікаційної мережі.Item Формалізація проблеми захисту інформації у мережах загального користування(Видавництво Львівської політехніки, 2012) Петров, А. О.Запропоновано підхід до формалізації проблеми системи захисту інформації у мережах загального користування. The paper presents an approach to formalize the problem of information security in public networks.Item Представлення асоціативної мережі образів за допомогою графів(Видавництво Національного університету "Львівська політехніка", 2009) Бісікало, О.; Тадевосян, Р.Розглянуто загальний підхід до представлення асоціативної мережі образів (АМО) а допомогою графів. Обґрунтовано модель АМО у вигляді орієнтованого зваженого рафу з двостороннім рухом. Для пошуку найкоротшого шляху у графі запропоновано новий алгоритм вичерпної дії, побудований на основі принципу «пошук углиб з поверненням». The main approach to the introduction of associative network of images (ANI) in the orm of a graph is considered in the given article. The model of ANI as a rough weight graph with two-extraneous motion is defined. The new algorithm of exhaustive action, built on the basis of principle «search in deepen with back» is suggested aiming for the search of short cut.