9
votes
Accepted
Aren’t most constraining variable and least constraining value the exact opposite?
Yes, these two heuristics sound like inconsistent. Most Constrained Variable (MCV) (also called MRV for Minimum Remaining Values) tries to reduce the size of the next branch to search while Least ...
- 39.1k
7
votes
Accepted
Branch and bound for minimum linear arrangement
One of the best solution is likely based on a linear programming relaxation or direct integer programming. For the latter, the branching and backtracking will be implicit, and you won't have to manage ...
- 485
6
votes
Accepted
Using backtracking to find all possible permutations in a string
Backtracking is a general algorithm "that incrementally builds candidates to the solutions, and abandons each partial candidate ("backtracks") as soon as it determines that the candidate cannot ...
- 9,885
6
votes
Accepted
Neural Network: Why can't we calculate derivatives during forward prop itself?
You described the simplest case of the neural network, where the center neuron has only one output $a$, which is connected to the final loss function. In general, there can be several outputs and the ...
- 640
4
votes
Accepted
Binarization of Constraints
Introduce a new variable $Q$, whose domain is $\{0000,0001,0010,\dots,1111\}$. It represents the value of $C1,C2,C3,P$. For instance, if $Q=0001$, that means that $C1=0$, $C2=0$, $C3=1$, $P=0$. ...
D.W.♦
- 166k
3
votes
Maximize number of museums visited in a day
The problem is strongly $NP$-complete by reduction from 3-Partition.
Given a set of $3n$ integers with total sum $3M$, we want to determine whether they can be partitioned into $n$ triples, each ...
- 13.4k
3
votes
Why run -time of N-Queens using backtracking algorithm fluctuates?
Consider that there might be something wrong with your experimental setup. The theoretical running time of an algorithm is based on an ideal model of a computer, but in practice there are lots of non-...
- 13.4k
3
votes
Optimal way to find maximal sum (with constraints) of array elements
This is a classic Dynamic Programming problem. Basically, dynamic programming is a way of turning a recursive algorithm into an iterative one with better runtime, by saving previous results that we ...
- 7,176
3
votes
Accepted
SAT Solving + Turing Machines
Yes, it is common for a SAT solver to combine several techniques, e.g., random restarts with smart backtracking or other tricks. More generally, nothing stops you from throwing everything and anything ...
- 22.8k
3
votes
Line-search does not guarantee convergence so how to use it?
First of all, if we have a descent direction, we can always find a step size $\tau$ that is arbitrary small, such that "the sufficient descent criterion" is satisfied (see the Wikipedia ...
- 31
3
votes
Accepted
Why is backtracking a necessary step in the Maze problem?
Your question title doesn't match your question details.
You're not asking why backtracking is necessary, but you're asking why a cell marked in the matrix needs to be unmarked when backtracking.
A ...
- 5,941
3
votes
Longest sequence of dominoes
Your problem is NP-hard. Consider an instance of Hamiltonian path graph $G=(V,E)$ in which the degree of each vertex is at most $3$ and we are given a starting vertex $s$ and ending vertex $t$ both of ...
- 29.6k
3
votes
Partition a set of n integers into m subsets in a way that the maximum subset sum is minimized
The problem can be shown to be weakly NP-hard by noticing that it is a generalization of partition. In particular, when $m=2$ the input set of integers is a yes instance of partition if and only if ...
- 29.6k
3
votes
Trajectories with collisions
One possible approach is to use the Bentley-Ottman algorithm (or similar algorithm) to find all intersections between line segments.
More specifically: for each plasma gun, add a directed line ...
D.W.♦
- 166k
3
votes
Accepted
How to solve a system of XOR equations in a cyclic graph?
You can express this as an instance of XOR-SAT, then find a solution using Gaussian elimination. I am assuming that each value $1,2,3,$ represents a bit-vector of some appropriate length, and you are ...
D.W.♦
- 166k
2
votes
Time complexity of this solution to N-queens problem
Your analysis would be reasonable for rooks, but not for queens. For example, in the second row there are not n-1 possible positions, but n-2 in two cases and n-3 in most cases. Now big-O provides an ...
- 31.6k
2
votes
Accepted
Is there any advantage of using an Integer Linear Program over Backtracking in a combinatorial optimization problem?
Integer linear programming can potentially be more efficient. ILP solvers normally combine backtracking with many other methods, so for many problems ILP might be faster than backtracking alone. ...
D.W.♦
- 166k
2
votes
Accepted
How to count the combinations not greater than a given volume in a knapsack problem?
Why did it fail?
Look at the code cache = new int[size+1][volume+1];. Suppose size is 1 and ...
- 39.1k
2
votes
Accepted
Divide an array into two sub arrays such that their sums are equal and possibly maximum
The problem is NP-hard, by a straightforward reduction from the partition problem. Therefore, you should not expect any efficient algorithm. However, there is a pseudo-polynomial-time algorithm ...
D.W.♦
- 166k
2
votes
Minimum sum of distance from entrance gate
I will try to give a solution. Tell me if I am mistaking anywhere.
First observation : When we have equal number of chairs and persons the solution is trivial.Ask all the people from 1st gate to fill ...
- 498
2
votes
Why run -time of N-Queens using backtracking algorithm fluctuates?
The exponential running time of backtracking for the$N$-queens problem is an upper bound, which means that the algorithm may do better sometimes. If the algorithm is 'lucky' and tries good positions ...
- 8,342
2
votes
Does Warnsdorff’s algorithm for Knight’s tour problem always gives complete tour
In general Warnsdorff's rule is just a heuristic that guides the search. It is still possible that the search hits a dead-end and we are forced to backtrack.
So let us consider the $n \times n$ ...
- 22.8k
2
votes
Need recursive version of Conflict based backjumping
When a conflict is found during a recursive constraint satisfaction search there may be assignments and inferences in the call stack that have no connection to the conflict. Instead of backtracking ...
- 8,149
2
votes
Best approach to resource allocation problem
Let us first show that your proposed greedy algorithm for the second restriction is not optimal.
For this, consider a scenario with $e_1 = 1, e_2 = 3$ and $e_3 = 4$ as well as $d_1 = 1, d_2 = 2$ and $...
- 1,536
2
votes
Longest sequence of dominoes
Regarding each given domino as an edge in a graph connecting the vertices labelled from $[\![0, k-1]\!]$, with "doubles" $\langle j,j\rangle$ handled separately, we need to answer:
is the ...
- 219
1
vote
How to generate all combinations given an array of elements using backtracking?
I wrote the description below thinking that you were asking for all combinations of elements. However, at second glance it is unclear. I'll describe both cases.
Combinations
So let's talk about the ...
- 1,041
1
vote
Cracking code with clues
Your problem is a variant of Mastermind. In particular, it is "Super Mastermind". Wikipedia contains some relevant pointers, and you can find many more by searching for Super Mastermind. For example, ...
- 279k
1
vote
Maximize number of museums visited in a day
I agree with you that dynamic programming is the best choice. However, I wouldn't recurse over the number of museums, but over the time of day.
In particular: at 11:00pm, what plan gives you the ...
- 7,176
1
vote
Help with graph search problem
"Graph search" is a very general term that includes breadth-first-search and depth-first-search. Let's say you wanna do BFS on this problem.
For this problem, think of a matrix, or a state, as a node ...
- 133
1
vote
Can memoization be applied to any recursive algorithm?
Memoization can be applied to any function. Whether it helps with a given program or not depends on how often the function is called with the same parameters.
You don't specify what your recursive ...
- 781
Only top scored, non community-wiki answers of a minimum length are eligible