# Questions tagged [heuristics]

Questions about algorithmic strategies that quickly solve a problem well most of the time, but give no guarantees.

180 questions
Filter by
Sorted by
Tagged with
900 views

### Can heuristic methods and machine learning approaches be considered alternate methods to solve NP-Complete problems?

I was watching the videos from Skiena's Computational Biology Lectures, which is also available at youtube. In those videos, the professor made a statement that, most of the problems posed to computer ...
41 views

3k views

### Creating admissible heuristics from functions?

I'm having trouble figuring out how to create admissible heuristics from cost functions. For example, if I was trying to create an admissible heuristic from a cost function that takes in starting ...
320 views

### Local search: Problem with neighborhood definition

I have question on understanding the following neighborhood relation within a local-search approximation scheme. Let $M$ be a legal matching on any bipartite graph. Let $U_k$ be the neighborhood ...
451 views

### Algorithm to use for a TSP variant

What type of algorithm would you suggest me to use for this problem? I want to implement an algorithm that minimize the total distance in a graph (TSP) but for only X nodes. Also, we can go as many ...
863 views

### Heuristics & Constrain Satisfaction Problem Differences

I'm currently taking an Algorithms course, and we are covering Backtracking, CSP, and heuristics. However, I'm getting confused on exactly the differences between these terms and their applications. ...
3k views

### When does the nearest neighbor heuristic fail for the Traveling Salesperson?

Can you provide an example of NN algorithm failure on the Euclidean traveling salesman problem? I was trying to construct a specific example of this for my friends and was failing.
17k views

### Trying to improve minimax heuristic function for connect four game in JS

I have made a connect four game in JS and currently have a functioning minimax algorithm. The problem I'm having is that it is very, very easy to beat, even with a large depth. This is leading me to ...
674 views

### How approximate are “approximate” nearest neighbor (ANN) search algorithms?

Starting to use nanoflann to do some point cloud nearest neighbor searching and it got me thinking about just how "approximate" ANN methods are. If I have a (more or less) randomly distributed point ...
14k views

### Initial temperature in simulated annealing algorithm

I've done some testing of different initial temperatures in my simulating annealing algorithm and noticed the starting temperature has an affect on the performance of the algorithm. Is there any way ...
1k views

### Time complexity 2-opt method

I'm doing a practice test for a course on routing problems. There's a question asking to infere the time complexity of the 2-opt method. I can see that the complexity per iteration is in $O(n^2)$ ...
4k views

### A Good Resource for Christofides' Heuristic

Is there an explanation Christofides's Heuristic for solving TSP which does not simply state the algorithm and go ahead to prove the bound? To be specific: (Disclaimer : I am an engineer who knows ...
174 views

### Experimental Survey on Different Heuristics for Knapsack Problem

I am looking for a good survey/study of experimental results of heuristics for Knapsack problem (or implemented libraries in java/c++). Any help is appreciated!
119 views

### Heuristics for tree decomposition into k shortest paths

What kind of heuristics are useful in a tree decomposition of a graph to find the k shortest paths from a given source to a vertex? Moreover, the local shortest paths at each node in a tree are ...
834 views

### 'Texas Hold Em Poker' Agent Heuristics to help decide whether to fold or bet?

I am designing a poker agent with different heuristics to decide whether to raise, fold or pass (in Texas holdem poker). I am planning to have 4 heuristics with the agent biased to one of them. The ...
4k views

### Why is Uniform cost search called “uniform” cost search?

By this possibly good attempt to explain this, the "uniformity" in the Uniform cost search is actually the uniformity of the heuristic function. Is this explanation correct ? If yes, then don't all <...
57 views

### Heuristically determine a value f such that a probability d/f approaches 1/2

We have a set X of N elements. We want to get a new set X' having a size M < N. ...
457 views

### Problem similar to set packing

Call a family of sets $\mathcal{F} = \{S_1, \dotsc, S_k\}$ "diverse" if each set $S_i \in \mathcal{F}$ has at least one unique element. What are possible approaches for finding the largest diverse ...
1k views

### How to implement the details of shotgun hill climbing to make it effective?

I am currently working on a solution to a problem for which (after a bit of research) the use of a hill climbing, and more specificly a shotgun (or random-restart) hill climbing algorithmic idea seems ...
Problem : Given a (one dimensional) row containing $2N$ tiles arranged in $2N + 1$ spaces. There are $N$ black tiles (B), $N$ white tiles (W), and a single empty space. The tiles are initially in an ...