Questions tagged [backtracking]
The backtracking tag has no usage guidance.
90
questions
9
votes
1
answer
1k
views
Conflict Driven Clause Learning backtracking clarification
On the wikipedia page here it describes pretty well the CDCL algorithm (and it seems the pictures were taken from slides created by Sharad Malik at Princeton). However when describing how to backtrack ...
8
votes
1
answer
273
views
Branch and bound for minimum linear arrangement
I am trying to solve this branch and bound problem but I could not come up with any approximate cost function which is better than the cost.
Let's say $G$ is a graph of $n$ nodes $\{1, 2, 3, \ldots , ...
7
votes
2
answers
366
views
Find if a sequence of nodes is yielded by a preorder traversal of a binary tree
Assume we have a sequence of $0$s and $1$s: $n_1, n_2, ..., n_N$, in which $0$ stands for a leaf node, and $1$ stands for an uncertain node that may or may not be a leaf node. How can we check if this ...
6
votes
2
answers
7k
views
Greedy and backtracking solutions to an arrangement problem with constraints
I'm revising for my finals. I have found a pattern in past papers in terms of a recurring question, reworded coming up every year. But I've no idea what the marker actually wants... I've asked class ...
6
votes
1
answer
6k
views
Aren’t most constraining variable and least constraining value the exact opposite?
So aren’t MCV and LCV the exact opposite?MCV tries to choose the variable with the most constraints on
remaining variables but LCV is opposite: it tries to rule out as least values for other variables ...
6
votes
2
answers
3k
views
How does one formulate a backtracking algorithm
I am new to learning algorithms.
I was reading backtracking algorithm for generating all strings for n bits.
If I dry run the program I know the program is giving right result.
But I didn't understood ...
6
votes
1
answer
408
views
Neural Network: Why can't we calculate derivatives during forward prop itself?
I have been studying Andrew Ng's Coursera course about Deep Learning. In that he mentions that we calculate the activation functions during the forward pass, and the derivatives $\dfrac{dL}{dz} \ $, $\...
5
votes
2
answers
15k
views
Using backtracking to find all possible permutations in a string
I came across this algorithm in a book, and have been struggling to understand the basic idea. The books says it uses backtracking to print all possible permutations of the characters in a string. In ...
4
votes
1
answer
1k
views
Is there a more efficient algorithm than backtracking/dynamic programming?
Consider the following game:
One day a castle is attacked at sunrise (by surprise) by n soldiers.
Each soldier carries a canon and a rifle.
The castle has strength s.
On the first day each ...
4
votes
0
answers
37
views
Cardinalities in set coverings
Let
$I$ be a set of items;
$C \subseteq \mathcal{P}(I)$ be a set of subsets of $I$, where $\mathcal{P}(I)$ stands for the power set of $I$; And
$C(i) = \{ c \in C \mid i \in c \}$ be the set of sets, ...
4
votes
0
answers
78
views
(Historical perspective) CSP and SAT inter-fertilization
[Disclaimer: this is a rather specialized question]
It is known that techniques like Conflict-Driven Clause Learning (CDCL) and back-jumping -- which improved the Satisfiability (SAT) strategies ...
3
votes
2
answers
102
views
Maximize number of museums visited in a day
Given a list of museums, their opening hours and time needed to visit each, make a schedule such that a tourist visits maximal number of museums in a given day.
Suppose that no time is needed in ...
3
votes
1
answer
893
views
Why doesn't the Needleman-Wunsch algorithm find solutions that begin with a gap?
I have implemented in C++ the Needleman-Wunsch algorithm for pairwise sequence alignment using the following scores:
+1 for match (regardless of base)
-1 gap penalty
-1 for a mismatch.
Given two ...
3
votes
1
answer
37
views
Trajectories with collisions
Say that I have a plasma gun:
It's easy to compute the trajectory of the plasma ray starting from the gun.
However, another ray may come from afar:
As everybody knows, plasma rays are deviated when ...
3
votes
1
answer
16k
views
Time complexity of this solution to N-queens problem
I'm trying to figure out the time complexity of this implementation of classic N-queens problem on geeksforgeeks. The goal is to find just one such non-attacking solution(as opposed to finding all of ...
3
votes
0
answers
1k
views
Backtracking vs Branch-and-Bound
I'm getting a bit confused about the three terms and their differences: Depth-First-Search (DFS), Backtracking, and Branch-and-Bound.
What confuses me:
Stack Overflow: Difference between '...
2
votes
2
answers
807
views
Longest sequence of dominoes
Given $k$, a $k$-domino is a non-ordered pair of integer values of $[\![0, k-1]\!]$, for example $\langle 0, 3\rangle$ or $\langle 1, 1\rangle$ are dominoes, the domino $\langle 3, 0\rangle$ being the ...
2
votes
1
answer
808
views
Binarization of Constraints
I am trying to solve a Constraint Satisfaction Problem that involves lots of n-ary constraints. But the solver I have implemented only works with algorithms for binary constraints.
I've been reading ...
2
votes
1
answer
2k
views
Optimal way to find maximal sum (with constraints) of array elements
Problem: Find the maximum sum of the elements in an array, with the following constraints:
all the elements of the array are non-negative integers
each element can either be left out completely from ...
2
votes
2
answers
235
views
Need recursive version of Conflict based backjumping
I am implementing conflict directed Backjumping algorithm of prosser in java. But, the algorithm is iterative approach. How can it be built with recursive approach?
In AIMA they give the recursive ...
2
votes
1
answer
686
views
SAT Solving + Turing Machines
I have a couple of questions based on how SAT solvers work. I understand that SAT solvers may employ any/all of the following techniques:
Randomness
Heuristics
Backtracking
SAT is just one example ...
2
votes
1
answer
583
views
Basic question about backjumping in SAT solvers
I am reading "Formalization and Implementation of Modern SAT Solvers", by Filip Marić.
My question is about how backjumping is defined. In an example [1], there is a conflict clause C equal to
[-1,-...
2
votes
1
answer
263
views
Ways to speed up a Recursive Backtracking Algorithm
When dealing with a Recursive Backtracking Algorithm what are the ways to speed it up and what computational hardware is involved?
I'm assuming from ignorance that everything is done by the CPU so the ...
2
votes
1
answer
827
views
Can memoization be applied to any recursive algorithm?
I am new to the concepts of recursion, backtracking and dynamic programming.
I am having a hard time understanding if at all I can apply memoization to a particular recursive algorithm and if there ...
2
votes
1
answer
3k
views
Checking the validity of a pyramid of dominoes
I came across this question in a coding interview and couldn't figure out a good solution.
You are given 6 dominoes. A domino has 2 halves each with a number of spots. You are building a 3-level ...
2
votes
1
answer
1k
views
time complexity of word break algorithm
I found this question here but I don't think the answer is correct.
Here is the original word break question:
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence ...
2
votes
1
answer
271
views
Finding all soldier wins
Consider the following game (see also this question):
One day a castle is attacked at sunrise (by surprise) by n soldiers.
Each soldier carries a canon and a rifle.
The castle has strength s.
On the ...
2
votes
0
answers
43
views
Choosing a method for algorithmic problems - is it an art or science?
I've been doing lot of programming challenges lately (such as on leetcode.com) and often find myself in a situation when I cannot pick a method for solving a problem. I stuck with questions like - ...
2
votes
0
answers
43
views
Filling a board with maximum number of fixed size tiles
You are given a rectangular board of known size, e.g. 20x20 cm. Some 1x1 cm pieces are missing. Your task is to cover this board with a maximum number of 2x2 cm tiles (an example is attached below), ...
2
votes
0
answers
2k
views
DPLL time complexity analysis
Consider the most naïve backtracking for CNF-SAT. It only checks if an assignment satisfies the input formula $\phi$ when all the $n$ variables have values assigned. Let $m$ be the size of $\phi$. ...
2
votes
1
answer
173
views
Runtime complexity of permutation function
I am trying to find the asymptotic run time complexity of the following function which will return a list of all permutations of nums.
...
1
vote
2
answers
2k
views
Maximum non-intersecting subset of circles
We are given a set of circles, stored by their center points in an array $A$. In particular, the center of the $i$th circle is at coordinates $(A[i].x, A[i].y)$. All the circles have radius of $k$.
...
1
vote
2
answers
609
views
Best approach to resource allocation problem
Problem
The enemy army has taken $n$ of our cities. In each city $i$ the enemy has placed $e_i$ soldiers. We have $n$ teams, each team $j$ with $d_j$ soldiers. If we place more soldiers in a city ...
1
vote
1
answer
345
views
Why is backtracking a necessary step in the Maze problem?
The problem I am working on is specifically this:
A Maze is given as N*N binary matrix of blocks where source block is
the upper left most block i.e., maze[0][0] and destination block is
lower ...
1
vote
2
answers
3k
views
Minimum sum of distance from entrance gate
Assumes we have N position, and 3 entrance gate. For example 10 position:
1--2--3--4--5--6--7--8--9--10
For each entrance gate, there is some people waiting to enter and fill positions, first number ...
1
vote
1
answer
146
views
Generating hard puzzles for a backtracking snake
Let $M$ be a matrix of height $h$ and width $w$. Each entry of $M$ is an integer.
There is a snake that starts from the "left side" of $M$, and its goal is to reach the "right side" of $M$. To get ...
1
vote
1
answer
645
views
Partition a set of n integers into m subsets in a way that the maximum subset sum is minimized
Let's say we have a set of n integers. I'm trying to find a way to partition this set into m subsets (empty subsets are not ...
1
vote
2
answers
929
views
Line-search does not guarantee convergence so how to use it?
Line-search/backtracking in gradient descent methods essentially boils down to picking the current estimate $\theta_n$ (which depends on the stepsize $\gamma$ and the prior estimate $\theta_{n-1}$) by ...
1
vote
1
answer
145
views
Is there any advantage of using an Integer Linear Program over Backtracking in a combinatorial optimization problem?
Is there any advantage of using an Integer Linear Program over Backtracking in a combinatorial optimization problem?
I saw this Gurobi post that uses Integer Linear Programming to solve the traveling ...
1
vote
1
answer
335
views
How to count the combinations not greater than a given volume in a knapsack problem?
You are given a certain set of items with weight wi and the volume of the bag.
Case:
...
1
vote
1
answer
168
views
How is ARC consistency un-done after a recursive failure condition?
Taking this as an example:
...
1
vote
1
answer
697
views
Why does backtracking work the way it does?
I just recently started learning in a CS context (as opposed to a programming context) about simple recursive functions, along with the combinatorial applications, and techniques such as Backtracking ...
1
vote
1
answer
226
views
Given a sequence of strings how can you find the maximum number of strings so that if you concatenate them you have a dominant letter?
The naive approach, which is the first thing that came to my mind, is to use some sort of backtracking to generate all subsets of the given set of strings and then to find the subset with the maximum ...
1
vote
1
answer
58
views
Does this LCS algo generate all the CS or only all the LCSs?
The Wikipedia article on LCS has an algorithm that backtracks all the LCS strings. This link redirects to the desired bulletin in the article. The C table in the backtrackAll function is pre-...
1
vote
2
answers
1k
views
Does DFS have better constants/complexity than Backtracking on a Graph?
I came to know through some examples that DFS and Backtracking aren't exactly the same ( A misconception I had since a long time). So now my question is, since Backtracking visits nodes backwards step ...
1
vote
1
answer
41
views
Cracking code with clues
I am trying to solve this code cracking problem. The solution is either the code or all possible solutions if you can't narrow the possibilities.
We have a 5 character code that is consisting of ...
1
vote
1
answer
453
views
Algorithm to organize a tournament where the team componentes change each round
So, I was tasked with creating an app that generates the schedule of a doubles tennis tournament (i.e., teams of two) in a way that, by the end of it, everyone would have played against the rest of ...
1
vote
1
answer
113
views
Filling a 3x3 board with connected tiles
long story short: I want to list all possible combinations of n tiles on a 3x3 board with the restriction that at least 6 tiles are part of a connected chain. Tiles are connected if the pattern ...
1
vote
1
answer
1k
views
Backtracking for listing k elements
Can someone give me a hand here, I am new to backtracking, and preparing for an interview. I couldn't even attempt this question, please help.
Describe a back tracking algorithm for efficiently ...
1
vote
0
answers
33
views
Subset sum backtracking algorithm correctness proof
I'm trying to prove that the algorithm for subset sum, that is the algorithm that given a set of numbers $\\{x_1, \dots, x_n\\}$ and a number $K$ find if there is a subset $\\{x_{1_k}, \dots, x_{n_k}\\...