Algorytm hybrydowy (spełnienie ograniczeń)
W ramach sztucznej inteligencji i badań operacyjnych w zakresie spełniania ograniczeń algorytm hybrydowy rozwiązuje problem spełniania ograniczeń poprzez połączenie dwóch różnych metod, na przykład warunkowania zmiennych ( backtracking , backjumping itp.) I wnioskowania o ograniczeniach ( spójność łuku , eliminacja zmiennych itp.)
Algorytmy hybrydowe wykorzystują dobre właściwości różnych metod, stosując je do problemów, które mogą skutecznie rozwiązać. Na przykład wyszukiwanie jest skuteczne, gdy problem ma wiele rozwiązań, podczas gdy wnioskowanie jest skuteczne w dowodzeniu niespełnialności problemów z nadmiernymi ograniczeniami.
Algorytm wnioskowania/przeszukiwania cyklu cięcia
Ten algorytm hybrydowy opiera się na przeszukiwaniu zestawu zmiennych i wnioskowaniu na podstawie innych. W szczególności śledzenie wsteczne lub inna forma wyszukiwania jest wykonywana na wielu zmiennych; ilekroć spójne przypisanie częściowe dla tych zmiennych, wnioskowanie jest przeprowadzane dla pozostałych zmiennych, aby sprawdzić, czy to częściowe przypisanie można rozszerzyć, aby utworzyć rozwiązanie.
W przypadku niektórych rodzajów problemów istnieją wydajne i kompletne algorytmy wnioskowania. Na przykład problemy, których grafami pierwotnymi lub dualnymi są drzewa lub lasy, można rozwiązać w czasie wielomianowym. Wpływa to na wybór zmiennych ocenianych przez wyszukiwanie. Rzeczywiście, po oszacowaniu zmiennej można ją skutecznie usunąć z wykresu, ograniczając wszystkie ograniczenia, które są związane z jej wartością. Alternatywnie ocenianą zmienną można zastąpić wieloma odrębnymi zmiennymi, po jednej dla każdego ograniczenia, z których wszystkie mają domenę o jednej wartości.
Ten mieszany algorytm jest wydajny, jeśli zmienne wyszukiwania są tak dobrane, że ich powielanie lub usuwanie zmienia problem w taki, który można skutecznie rozwiązać przez wnioskowanie. W szczególności, jeśli te zmienne tworzą zbiór cykli wykresu problemu, wnioskowanie jest wydajne, ponieważ musi rozwiązać problem, którego wykresem jest drzewo lub , bardziej ogólnie, las . Taki algorytm jest następujący:
znajdź zbiór fragmentów cykli wykresu przebiegu problemu wyszukaj zmienne zbioru przekrojów, gdy zostaną znalezione spójne częściowe przypisania do wszystkich zmiennych, zastąp każdą zmienną zbioru przekrojów nową zmienną dla każdego ograniczenia; ustaw dziedziny tych nowych zmiennych na wartość starej zmiennej w przypisaniu częściowym rozwiąż problem za pomocą wnioskowania
Wydajność tego algorytmu zależy od dwóch przeciwstawnych czynników. Z jednej strony, im mniejszy zbiór fragmentów, tym mniejszy podproblem do rozwiązania za pomocą wyszukiwania; ponieważ wnioskowanie jest wydajne na drzewach, wyszukiwanie jest częścią, która ma największy wpływ na wydajność. Z drugiej strony znalezienie zestawu o minimalnym rozmiarze jest trudnym problemem. W rezultacie, zamiast minimalnego, można zastosować mały cykl cięcia.
Inną alternatywą skracania czasu wyszukiwania jest większe obciążenie części wnioskowania. W szczególności wnioskowanie może być stosunkowo wydajne, nawet jeśli wykres problemu nie jest lasem, ale wykresem o małej indukowanej szerokości. Można to wykorzystać, przeprowadzając wyszukiwanie na zestawie zmiennych, który nie jest zestawem wycinków cyklicznych, ale po usunięciu problemu pozostawia indukowaną szerokość ograniczoną przez . [ wyjaśnienie ] Taki zestaw zmiennych nazywa się problemu.
Indukowana szerokość wykresu po usunięciu zestawu zmiennych jest nazywana dopasowaną szerokością indukowaną . Dlatego indukowana szerokość dostosowana względem zestawu cięć jest zawsze . Znalezienie zestawu minimalnym rozmiarze ogólnie trudne. Jednak o rozmiarze innym niż minimalny można łatwo znaleźć dla ustalonej kolejności zmiennych. W szczególności taki zestaw cięć pozostawi pozostały wykres szerokości ograniczony zgodnie z tą konkretną kolejnością zmiennych.
Algorytm znajdowania takiego zestawu przekrojowego polega na naśladowaniu procedury znajdowania indukowanego grafu problemu zgodnie z rozważaną kolejnością zmiennych (procedura ta przebiega od ostatniego węzła w kolejności do pierwszego, dodając krawędź pomiędzy każdą parą niepołączonych rodziców każdego węzła). Ilekroć ta procedura znalazłaby lub węzeł mający więcej niż , węzeł jest usuwany z wykresu i dodawany do zbioru cięć. Z definicji wynikowy wykres nie zawiera węzła o szerokości większej niż , a zatem zbiór usuniętych węzłów jest - cutset.
Alternatywą dla korzystania z tego algorytmu jest umożliwienie wyszukiwaniu oceny zmiennych, ale sprawdzenie na każdym kroku, czy pozostały wykres jest lasem, i uruchomienie wnioskowania, jeśli tak jest. Innymi słowy, zamiast znajdować zbiór zmiennych na początku i używać tylko ich podczas wyszukiwania, algorytm rozpoczyna zwykłe wyszukiwanie; na każdym kroku, jeśli przypisane zmienne tworzą zestaw problemu, wnioskowanie jest uruchamiane w celu sprawdzenia spełnialności ponieważ sprawdzenie, czy dany zestaw węzłów jest zestawem cięć dla ustalonego jest problemem wielomianowym.
Hybrydowy algorytm dekompozycji drzewa
Inny hybrydowy algorytm wyszukiwania/wnioskowania działa na dekompozycji drzewa . Ogólnie rzecz biorąc, problem spełniania ograniczeń można rozwiązać, najpierw tworząc dekompozycję drzewa, a następnie używając wyspecjalizowanego algorytmu.
Jeden z takich algorytmów opiera się najpierw na propagowaniu ograniczeń między węzłami, a następnie rozwiązywaniu podproblemu w każdym węźle. Propagacja ta polega na tworzeniu nowych wiązań, które reprezentują skutki ograniczeń w węźle nad połączonym węzłem. Dokładniej, jeśli dwa węzły są połączone, dzielą zmienne. Dozwolone oceny tych zmiennych zgodnie z ograniczeniami pierwszego węzła mówią, w jaki sposób pierwszy węzeł wpływa na zmienne drugiego węzła. Algorytm działa poprzez utworzenie ograniczenia spełnianego przez te oceny i włączenie tego nowego ograniczenia do drugiego węzła.
Kiedy wszystkie ograniczenia zostały rozpropagowane z liści do korzenia iz powrotem do korzenia, wszystkie węzły zawierają wszystkie istotne dla nich ograniczenia. Problem można zatem rozwiązać w każdym węźle.
Podejście hybrydowe można przyjąć, stosując eliminację zmiennych do tworzenia nowych ograniczeń, które są propagowane w węzłach, oraz algorytm wyszukiwania (taki jak śledzenie wsteczne , przeskakiwanie wstecz , wyszukiwanie lokalne ) w każdym pojedynczym węźle.
- Dechter, Rina (2003). Przetwarzanie ograniczeń . Morgana Kaufmanna. ISBN 1-55860-890-7 .