Czy w programowaniu ograniczeń istnieją jakieś modele uwzględniające liczbę zmian zmiennych?

Rozważ model CSP, w którym zmiana wartości konkretnej zmiennej jest kosztowna. Czy jest jakaś praca, w której funkcja celu bierze również pod uwagę liczbę zmian wartości zmiennej podczas procesu wyszukiwania?

Przykład: Zmienna kosztowna do zmiany może być pod kontrolą jakiegoś innego agenta i istnieje pewien narzut związany z zaangażowaniem tego agenta do zmiany zmiennej. Kolejny przykład: zmienna uczestniczy w jednym z ograniczeń, a spełnienie tego ograniczenia polega na wywołaniu drogiej funkcji (takiej jak symulator), np. jest ograniczeniem, a jest kosztownym- funkcja obliczania. Dlatego też, i są drogie do zmiany zmiennych. $z = f(x, y)$ $f$ $x$ $y$

algorithms constraint-programming

— amit
źródło

Funkcja celu mówi o końcowych wartościach CSP i nie wie o procesie wyszukiwania. Zatem w standardowych sformułowaniach zmiany takich zmiennych nie są narażone na model CSP. Niektóre solwery, takie jak Choco, zapewniają heurystykę do kierowania procesem wyszukiwania. Niektóre z nich mogą nawet być zdefiniowane przez użytkownika. Być może jest to miejsce, w którym można zmienić sposób wyszukiwania.

— Dave Clarke,

Ale dlaczego funkcja celu miałaby odzwierciedlać, jak drogie było znalezienie rozwiązania? Czy nie powinieneś porównywać rozwiązań według ich przydatności w dziedzinie problemów? A może czas rozwiązania jest częścią rzeczywistego problemu?

— Raphael

Brzmi, jakbyś był w ustawieniu zadowolenia z rozproszonego ograniczenia i brzmi, jakbyś szukał heurystyki.

— Dave Clarke

Wygląda na to, że potrzebujesz wrażliwej na koszty (uwzględniającej koszty, budżetowanej) techniki optymalizacji. Minimalizacja dwie wartości (np rozwiązanie twój cel i koszt operacji na i ) jest problem optymalizacji wielokryterialnej , a te wydają się być bardzo trudne do rozwiązania. Powszechnym podejściem jest określenie budżetu dla maksymalnych dopuszczalnych kosztów, a następnie zminimalizowanie funkcji celu w odniesieniu do . Ta formuła ma tendencję do ładnego dopasowania do istniejących ram jako dodatkowe ograniczenie. Oczywiście określenie funkcji kosztów i dopuszczalnego budżetu w taki sposób, aby uzyskać sensowne rozwiązania, może być trudne - będzie to zależeć od konkretnego problemu, który próbujesz rozwiązać. $x$ $y$ $costs(x,y) \le Budget$

— Nacięcie
źródło