Wyszukiwanie zaawansowane ?

Obiekt

Pobierz

Tytuł: A fine-grained arc-consistency algorithm for non-normalized constraint satisfaction problems

Autor:

Arangú, Marlene ; Salido, Miguel A.

Data wydania:

2011

Typ zasobu:

artykuł

Współtwórca:

Korbicz, Józef (1951- ) - red. ; Uciński, Dariusz - red.

Tytuł publikacji grupowej:

AMCS, Volume 21 (2011)

Abstract:

Constraint programming is a powerful software technology for solving numerous real-life problems. Many of these problems can be modeled as Constraint Satisfaction Problems (CSPs) and solved using constraint programming techniques. However, solving a CSP is NP-complete so filtering techniques to reduce the search space are still necessary. Arcconsistency algorithms are widely used to prune the search space. ; The concept of arc-consistency is bidirectional, i.e., it must be ensured in both directions of the constraint (direct and inverse constraints). Two of the most well-known and frequently used arc-consistency algorithms for filtering CSPs are AC3 and AC4. These algorithms repeatedly carry out revisions and require support checks for identifying and deleting all unsupported values from the domains. Nevertheless, many revisions are ineffective, i.e., they cannot delete any value and consume a lot of checks and time. ; In this paper, we present AC4-OP, an optimized version of AC4 that manages the binary and non-normalized constraints in only one direction, storing the inverse founded supports for their later evaluation. Thus, it reduces the propagation phase avoiding unnecessary or ineffective checking. The use of AC4-OP reduces the number of constraint checks by 50% while pruning the same search space as AC4. The evaluation section shows the improvement of AC4-OP over AC4, AC6 and AC7 in random and non-normalized instances.

Wydawca:

Zielona Góra: Uniwersytet Zielonogórski

Identyfikator zasobu:

oai:zbc.uz.zgora.pl:46955

DOI:

10.2478/v10006-011-0058-2

Strony:

733-744

Źródło:

AMCS, Volume 21, Number 4 (2011) ; kliknij tutaj, żeby przejść

Jezyk:

eng

Prawa do dysponowania publikacją:

Biblioteka Uniwersytetu Zielonogórskiego

Temat i słowa kluczowe:

constraint satisfaction problems filtering techniques consistency algorithms

Kolekcje, do których przypisany jest obiekt:

Data ostatniej modyfikacji:

2024-11-05

Data dodania obiektu:

2018-08-29

Liczba wyświetleń treści obiektu:

171

Wszystkie dostępne wersje tego obiektu:

https://zbc.uz.zgora.pl/repozytorium/publication/55056

Wyświetl opis w formacie RDF:

RDF

Wyświetl opis w formacie OAI-PMH:

OAI-PMH

Nazwa wydania Data
A fine-grained arc-consistency algorithm for non-normalized constraint satisfaction problems 2024-11-05

Obiekty

Podobne
AMCS, Volume 24 (2014)
AMCS, Volume 24 (2014)

Accelerating backtrack search with a best-first-search strategy

Mann, Zoltán Ádám Szép, Tamás Korbicz, Józef (1951- ) - red. Uciński, Dariusz - red.

2014
artykuł
AMCS, volume 19 (2009)
AMCS, volume 19 (2009)

Derivation of physically motivated constraints for efficient interval simulations applied to the analysis of uncertain dynamical systems

Freihold, Mareile Hofer, Eberhard P. Rauh, Andreas - ed. Auer, Ekaterina - ed. Hofer,Eberhard P. - ed. Luther, Wolfram - ed.

2009
artykuł
Więcej

Dane kontaktowe

Adres

Biblioteka Uniwersytetu Zielonogórskiego
al. Wojska Polskiego 71
65-762 Zielona Góra

Telefon

(+48) 68 328 21 55

E-Mail

repozytorium@uz.zgora.pl

Odwiedź nas!

Ta strona wykorzystuje pliki 'cookies'. Więcej informacji