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.
Questions tagged [constraint-satisfaction-problems]
32 questions
6
votes
1 answer
How to turn a ternary constraint into three binary constraints?
I'm trying to solve problem 6.6 from the book Artificial Intelligence: A Modern Approach, by Peter Norvig and Stuart Russell.
This is in the context of Constraint Satisfaction Problem and how you can re-formulate some problems with the constraints…
Cristóbal Alcázar
- 173
- 1
- 8
6
votes
1 answer
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 actually mean?
Lexi
- 109
- 7
5
votes
1 answer
What are the differences between constraint satisfaction problems and linear programming?
I have taken an algorithms course where we talked about LP significantly, and also many reductions to LPs. As I recall, normal LP is not NP-Hard. Integer LP is NP-Hard. I am currently taking an introduction to AI course, and I was wondering if CSP…
Prabh Dhali
- 51
- 1
4
votes
1 answer
What AI technique should I use to assign a person to a task?
I'm trying to learn AI and thinking to apply it to our system. We have an application for the translation industry. What we are doing now is the coordinator $C$ assigns a file to a translator $T$. The coordinator usually considers these criteria…
Jaime Sangcap
- 143
- 4
3
votes
0 answers
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 a nonogram solving problem and I want to solve it using backtracking with CSP.
The first problem that I face is that I cannot quite figure out what such variables, domains,…
Karol
- 161
- 3
3
votes
0 answers
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 heuristic tells you to choose a variable that has the…
calveeen
- 1,251
- 7
- 17
2
votes
1 answer
What is a successor function (in CSPs)?
In Constraint Satisfaction Problems (CSPs), a state is any data structure that supports
a successor function,
a heuristic function, and
a goal test.
In this context, what is a successor function?
Abbas Ali
- 566
- 3
- 10
- 17
2
votes
1 answer
Have evolutionary algorithms been used for engineering design?
Recently, I've been looking recently into what uses AI - specifically evolutionary algorithms - may have in automating engineering design. For a long time, there have been algorithms that solve constraint satisfaction problems, and, to me, it makes…
QuadraticOne
- 53
- 3
2
votes
0 answers
How to create a loss function that penalizes duplicate indices in the output tensor?
We're working on a sequence-to-sequence problem using pytorch, and are using cross-entropy to calculate the loss when comparing the output sequence to the target sequence. This works fine and penalizes the model correctly. However, we also have the…
vgoklani
- 121
- 2
2
votes
0 answers
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 directed backjumping as follows:
In our example,…
Rnj
- 221
- 2
- 6
2
votes
1 answer
How can I develop a genetic algorithm with a constraint on the sum of alleles?
I'm working on a genetic algorithm with a constraint on the sum of the alleles, e.g. if we use regular binary coding and a chromosome is 5-bits long I'd like to constrain it so that the sum of the bits has to be 3 or less (011100 is valid but 011110…
Mark
- 21
- 1
2
votes
1 answer
How can I formulate the k-knights problem as a constraint satisfaction problem?
There are three things in every constraint satisfaction problem (CSP):
Variables
Domain
Constraints
In the given scenario, I know how to identify the constraints, but I don't know how to identify the variables and the domain.
The given scenario…
Sheri
- 123
- 1
- 6
2
votes
1 answer
Which algorithm can I use to solve a problem with multiple objectives and constraints?
Consider a problem with many objectives. In my case, these are school grades for different courses (or subjects). To be more concrete, suppose that my current grade for the math course is $12/20$ and for the philosophy course is $8/20$. My objective…
YLM
- 121
- 3
2
votes
0 answers
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 affinity) value associated with each task…
Tariq Kavish Arain
- 41
- 4
2
votes
1 answer
What are daily life examples of SAT problems?
What are (good) daily life examples of SAT problems?
I've thought about this one. The problem of placing a bunch of different kinds of glasses in a shared cabinet in such a way that some constraints would be satisfied, such as putting the longer…
Jay Critch
- 343
- 1
- 7