Questions tagged [constraint-satisfaction-problems]

For questions about constraint satisfaction problems (CSPs), which are usually described by a set of variables, a set of domains, and a set of constraints. For more details, see, for example, chapter 6 of the book "Artificial Intelligence: A Modern Approach" (3rd Edition) by Stuart Russell and Peter Norvig.

17 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
1answer
211 views

What is local consistency in constraint satisfaction problems?

In the Constraint Propagation in CSP, it is often stated that pre-processing can solve the whole problem, so no search is required at all. And the key idea is local consistency. What does this ...
3
votes
0answers
133 views

How can I formulate a nonogram problem as a constraint satisfaction problem?

I've just started learning CSP and I find it quite exciting. Now I'm facing nonogram solving problem and I want to solve it using backtracking with CSP. The first problem that I face is that I cannot ...
2
votes
0answers
376 views

Can the degree and minimum remaining values heuristics be used in conjunction?

I am currently studying constraint satisfaction problems and have come across two heuristics for variable selection. The minimum remaining values(MRV) heuristic and the degree heuristic. The MRV ...
2
votes
0answers
114 views

How can I assign agents to tasks based on time and affinity?

I am working on an assignment problem. Consider $K$ agents $A_1, \dots A_K$ and $N$ tasks $T_1, \dots T_N$. Each task has a certain time $t(T_i)$ to be completed and each agent has a matching (or ...
2
votes
0answers
1k views

How to improve the efficiency of the backtracking search in CSPs?

Backtracking search is the basic uninformed search algorithm for constraint satisfaction problems (CSPs). How could we improve the efficiency of the backtracking search in CSPs?
1
vote
0answers
21 views

Understanding conflict set generation for conflict directed backjumping

I was reading Constraint Satisfaction Problem chapter from Artificial Intelligence 3rd ed book by Peter Norvig et al. On page 219, section 6.3 it explains computation of conflict set for conflict ...
1
vote
0answers
21 views

CSP heuristic to simultaneously reduce conflicts and find near optimal assignment

I am trying to design a good heuristic to solve a constraint satisfaction problem (CSP). I think that a possible heuristic to use is $$h_1(\text{state}) = \text{number of conflicts in state}$$ However,...
1
vote
0answers
50 views

Somone can help me to solve this question about the AC-3 algorithm

i was watching this video: https://www.youtube.com/watch?v=4cCS8rrYT14 and I tried to solve this question: "Given the variables A, B, C and D, with domain {1, 2, 3, 4} in each of them and ...
1
vote
0answers
22 views

How can I design a system that suggests physical exercises to a person while keeping into account the fatigue?

I want to create an exercise suggester. Each day either has a routine or is a rest day. A routine has 4 slots. For each slot we select an exercise. We constrain the legal exercises, only do upper-body ...
1
vote
0answers
23 views

How do I decide which norm to use for placing a constraint on my adversarial perturbation?

I am performing an adversarial machine learning attack on a neural network for network traffic classification. For adding adversarial perturbations in features such as packet interarrival times and ...
1
vote
0answers
18 views

Where can I find example data for Nonogram solver?

I made CSP nonogram solver and I wanna test it on some bigger data. Where can I find such data to test my program? I've been looking on the internet but I couldn't find anything.
1
vote
0answers
129 views

What is exactly the role of commutative property in a Constraint Satisfaction Problem?

I have been looking into the backtracking search for CSPs, and understand that if we just plainly do a typical depth-limited search we have a vast tree with leaves size n!d^n where n is the # of ...
1
vote
0answers
31 views

Write Constraint Satisfaction Formulation for problem

Given $F_1,F_2,..,F_n$ as set of final exams of subjects taken by students $S_1,..,S_k$ in h slots such that no student takes two exams in a single slot.Here the objective is to maximize the number of ...
1
vote
0answers
113 views

Can AC-3 algorithm solve N-Queens problem?

I am building CSP NQueens solver and apply the AC-3 algorithm.But,the domain reduction doesn't occur and gets more search time.How does it happen?Is it a nature of AC-3 algorithm?
0
votes
0answers
19 views

Constraint Satisfaction Problem - Scheduling Problems

I have been working through some CSPs and I have noted that scheduling problems are quite often used with CSPs. I have the following example: A certain deli prepares the following meals for take-away: ...
0
votes
0answers
44 views

Which set operation is used to find equivalence of two constraint networks?

I was given a question Given the following constraint networks $X$, $Y$ and $Z$ with four variables $x_1, x_2, x_3$ and $x_4$ all defined on the same domain values $\{\text{red}, \text{blue} \}$. The ...
0
votes
0answers
55 views

How can I translate this deep-first search pseudocode into JavaScript?

In the paper Using Cyclic Scheduling to Generate Believable Behavior in Games, Richard Zhao and Duane Szafron describe a tool that is able to generate schedules for NPCs. The tool The tool offers a ...