Модифікації алгоритму GLoSS для розв'язання FDCSP
Loading...
Date
2016
Authors
Гороховський, Семен
Галковська, Любов
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
У цій роботі подано розроблені автором модифікації алгоритму GLoSS, що розв’язують розподілену задачу задоволення обмежень із гнучкими обмеженнями. Наведено доведення повноти та
коректності алгоритмів, а також оцінки їх часової складності.
Description
This work introduces three new algorithms for solving Fuzzy Distributed Constraint Satisfaction Problem
(FDCSP). They all are modifications of the author’s algorithm for solving DCSP problems – GLoSS. Modifications
were built using the method proposed by the authors of ADOPT algorithm for converting CSP algorithms
for solving CSP problems to the ones that solve FCSP. Given that GLoSS is a hybrid method and consists
of three components, its three different modifications were created. The first component – SBT – needed
no modification but required some corrections of the exit condition. The same can be said about the second
component iGL. The only big change that has been made in it is that the modified version is attempting to find
the solution which satisfies all the constraints with some given satisfaction level, which is not necessarily 1.
The third component – AWCS – experienced the biggest changes between all three GLoSS components. Now
its exit condition has been changed so that it restarts with the new configuration instead of returning “no solution”
answer.
All these algorithms, specifically those parts that have changed from the original version, are supported
with the pseudo-code. Also their completeness and correctness is proved by the corresponding theorems.
Besides that, the article contains complexity estimations for the algorithms and their brief comparison, which
may help to choose the right algorithm depending on the type of the problem to solve.
Keywords
задача задоволення обмежень із гнучкими обмеженнями, розподілена задача задоволення обмежень із гнучкими обмеженнями, ступінь задоволеності обмежень, Fuzzy Constraint Satisfaction Problem, Fuzzy Distributed Constraint Satisfaction Problem, satisfaction degree
Citation
Гороховський Семен Самуїлович. Модифікації алгоритму GLoSS для розв'язання FDCSP / Гороховський С. С., Галковська Л. О. // Наукові записки НаУКМА : Комп'ютерні науки. - 2016. - Т. 190. - С. 4-10.