Co to jest najmniej ograniczająca wartość?

W przypadku problemów związanych z satysfakcją z ograniczeń heurystykę można wykorzystać w celu poprawy wydajności solvera z funkcją Bactracking. Trzy najczęściej podawane heurystyki dla prostych solverów do cofania to:

• Minimalna pozostała wartość (ile wartości jest nadal poprawnych dla tej zmiennej)
• Stopień heurystyczny (ile innych zmiennych wpływa na tę zmienną)
• Najmniejsza wartość ograniczająca (jaka wartość pozostawi najwięcej innych wartości dla innych zmiennych)

Pierwsze dwa są dość oczywiste i łatwe do wdrożenia. Najpierw wybierz zmienną, która ma najmniej wartości w swojej domenie, a jeśli istnieją powiązania, wybierz tę, która wpływa na większość innych zmiennych. W ten sposób, jeśli krok nadrzędny w rozwiązaniu wybrał złe zadanie, prawdopodobnie dowiesz się wcześniej, a tym samym zaoszczędzisz czas, jeśli wybierzesz zmienną o najmniejszej wartości, która wpływa na większość innych rzeczy.

Są one proste, jasno zdefiniowane i łatwe do wdrożenia.

Najmniejsza wartość ograniczająca nie jest jasno określona, ​​gdziekolwiek spojrzałem. Sztuczna inteligencja: nowoczesne podejście (Russel i Norvig) mówi tylko:

Preferuje wartość, która wyklucza najmniejszą liczbę opcji dla sąsiednich zmiennych na wykresie ograniczeń.

Wyszukiwanie „najmniej ograniczającej wartości” ujawniło tylko wiele pokazów slajdów uniwersyteckich opartych na tym podręczniku, bez dalszych informacji na temat tego, jak można to zrobić algorytmicznie.

Jedynym przykładem podanym dla tej heurystyki jest przypadek, w którym jeden wybór wartości eliminuje wszystkie wybory dla sąsiedniej zmiennej, a drugi nie. Problem z tym przykładem polega na tym, że jest to trywialny przypadek, który zostałby natychmiast wyeliminowany, gdy potencjalne przypisanie zostanie sprawdzone pod kątem zgodności z ograniczeniami problemu. Tak więc we wszystkich przykładach, które mogłem znaleźć, heurystyka o najmniejszej wartości w rzeczywistości w żaden sposób nie poprawiła wydajności solvera, z wyjątkiem niewielkiego negatywnego efektu dodania nadmiarowej kontroli.

Jedyne, co mogę wymyślić, to przetestować możliwe przypisania sąsiednich zmiennych dla każdego przypisania i policzyć liczbę możliwych przypisań sąsiadów, które istnieją dla każdego możliwego przypisania tej zmiennej, a następnie uporządkować wartości dla tej zmiennej na podstawie liczby dostępnych przypisań sąsiadów, jeśli ta wartość zostanie wybrana. Nie rozumiem jednak, w jaki sposób poprawiłoby to losowość, ponieważ wymaga to zarówno przetestowania wielu kombinacji zmiennych, jak i sortowania na podstawie wyników zliczania.

Czy ktoś może podać bardziej użyteczny opis wartości najmniej ograniczającej i wyjaśnić, w jaki sposób ta wersja wartości najmniej ograniczającej rzeczywiście przyniosłaby poprawę?

zobacz ten link:

https://people.cs.pitt.edu/~wiebe/courses/CS2710/lectures/constraintSat.example.txt

Najpierw wybiera zmienną „O”, a następnie testuje „O” ze wszystkimi dopuszczalnymi wartościami „i”, aby zobaczyć liczbę redukcji u sąsiadów „O” „N”. Dodaje je wszystkie. i wybiera „i”, które powoduje mniejsze redukcje:

   sums = {0:0,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
   For i from 0 to 9:  
     plug "o=i" into the constraint formulas
     For each neighbor "N" of "o" in the constraint graph:
       sums[i] += the number of values remaining for "N"

Wybiera „i”, dzięki czemu:

sums[i] = MAX{sums[i] | for all "i" that is a member of "O",s valid values}

Mam nadzieję, że pomoże Ci to znaleźć odpowiedź!

Myślę, że najważniejsze jest to, że te heurystyki są stosowane w zależności od zadania, dla którego napisany jest solver. A jeśli istnieje możliwość, że jeśli wybrana wartość zmiennej nie pozostawi pojedynczej wartości w domenie innej zmiennej (powiedzmy, że mamy mocno ograniczony problem z tylko jednym rozwiązaniem), wówczas rozwiązanie zatrzyma się . Losowe wyszukiwanie może pójść właściwą ścieżką prowadzącą do podjęcia decyzji i niewłaściwej. A jeśli pójdzie nie tak, będziesz musiał cofnąć się (patrz skakanie przez konflikt), a to zajmie czas obliczeniowy. Ale algorytm wykorzystujący heurystykę LCV jest bardziej prawdopodobne, że pójdzie bardziej prawidłową ścieżką i żadne zwroty nie są wymagane. Ale jeśli występuje problem z ograniczeniami, myślę, że będzie to podobne do wyszukiwania losowego.