Questions tagged [constraint-satisfaction-problems]
For questions about constraint satisfaction problems.
13
questions
2
votes
1answer
36 views
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 ...
1
vote
0answers
12 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 ...
2
votes
1answer
187 views
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 ...
1
vote
0answers
111 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 ...
0
votes
0answers
12 views
Algorithm for pretty printing CSP graph visualization to be easy to understand?
I'm trying to come up with an algorithm to print complex CSP graphs in a easy to understand manner. I originally thought maybe to center constraints around their domain nodes but that probably won't ...
1
vote
0answers
21 views
How to calculate constraint check in nqueen of AIMA CSP?
I am testing aima csp of java code and I want to know how the constraint check of these problems described in AIMA book is got.
1
vote
0answers
25 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 ...
0
votes
0answers
55 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?
3
votes
1answer
47 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 ...
1
vote
1answer
47 views
Understanding Constraint Search
What is the goal of a constraint solver? How are constraints propagated in a constraint satisfaction search?
Any references are also appreciated.
2
votes
1answer
91 views
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 ...
0
votes
0answers
81 views
How to solve constraint satisfaction problem of two queen and two knights on a $4 \times 4$ grid?
Consider the problem of placing 2 knights and 2 queens on a $4 \times 4$ chessboard, each piece (knight or queen) per row (denoted by R1, R2, R3, and R4), such that no two pieces are attacking each ...
5
votes
1answer
979 views
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 ...
