Questions tagged [constraint-satisfaction-problems]
For questions about constraint satisfaction problems.
23
questions
1
vote
0answers
12 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
35 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 ...
1
vote
0answers
40 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 ...
2
votes
1answer
52 views
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 ...
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 ...
0
votes
0answers
112 views
Constraint Satisfaction for light switches problem
While revising on the topic of constraint satisfaction, I came across a question on light switches which asks us to formulate the problem as a CSP. This problem was taken from
stanford's cs221 ...
1
vote
0answers
18 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
16 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.
4
votes
0answers
70 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
144 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
1answer
59 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
67 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
984 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 ...
3
votes
1answer
66 views
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 ...
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 ...
1
vote
0answers
29 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
99 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?
4
votes
1answer
115 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 ...
0
votes
1answer
60 views
What is the goal of a constraint solver?
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
140 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 ...
3
votes
1answer
101 views
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 ...
5
votes
1answer
2k 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 ...
2
votes
1answer
234 views
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 ...
