Problemy z ograniczeniami (CSP)

Constraint satisfaction problems (CSP) · id csp

Przypisywanie wartości zmiennym tak, by spełnić wszystkie ograniczenia — harmonogramy, układy, sudoku.

Assigning values to variables so all constraints hold — schedules, layouts, sudoku.

In one sentence

To szukanie układu, w którym wszystkie zapisane warunki są spełnione jednocześnie.

This finds an arrangement that satisfies all recorded conditions at once.

Problem it solves

Wiele wyborów zależy od siebie, więc poprawienie jednego fragmentu może zepsuć inny.

Many choices depend on each other, so fixing one part can break another.

What it does

Odrzuca wartości sprzeczne z warunkami, sprawdza pozostałe połączenia i cofa wcześniejsze wybory, gdy prowadzą do sprzeczności.

It rules out values that violate conditions, tests remaining combinations and revisits earlier choices when they create contradictions.

Everyday example

Układasz spotkania tak, żeby uczestnicy byli dostępni, sale się nie nakładały, a potrzebny sprzęt był na miejscu.

You schedule meetings so participants are available, rooms are not double booked and the required equipment is present.

This concerns you if you…

Examples

Related topics

Sources