# Questions tagged [heuristics]

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

209 questions
Filter by
Sorted by
Tagged with
784 views

### Measuring the difficulty of SAT instances

Given an instance of SAT, I would like to be able to estimate how difficult it will be to solve the instance. One way is to run existing solvers, but that kind of defeats the purpose of estimating ...
33k views

### How does an admissible heuristic ensure an optimal solution?

When using A* (or any other best path finding algorithm), we say that the heuristic used should be admissible, that is, it should never overestimate the actual solution path's length (or moves). How ...
2k views

### When to use SAT vs Constraint Satisfaction?

If I have a hard problem, one standard approach is to express it as a SAT instance and try running a SAT solver on it. Another standard approach is to express it as a constraint satisfaction problem, ...
15k 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 ...
13k views

### How does consistency imply that a heuristic is also admissible?

A heuristic function $h (n)$ is... Consistent if the estimated cost from node $n$ to the goal is no greater than the step cost to its successor $n'$ plus the estimated cost from the successor to the ...
9k views

### Difference between heuristic and approximation algorithm?

i have a problem regarding the following situation. I have two arrays of numbers like this: ...
24k views

### Why is the A* search heuristic optimal even if it underestimates costs?

A* search finds optimal solution to problems as long as the heuristic is admissible which means it never overestimates the cost of the path to the from any given node (and consistent but let us focus ...
8k views

111 views

### One-dimensional packing problem: Optimal decomposition of music structure

I am currently working on my Master thesis on the visualization of music structure and I'm looking to find an optimal description of repetitions found in a piece of music. Problem Description Given a ...
170 views

### Greedy Heuristics with an Altered Subset Sum/Partition Problem

Say we have a constant-time function that accepts some integer set. The function outputs True if we can split the integers into two subsets of an equal sum. If we can't partition the integers given, ...
54 views

### Optimization Problem when calculating fitness is expensive

I need to solve an optimization problem, maximizing fitness in a set of around 1 million solutions. Calculating the fitness of any solution is very time consuming, taking around 5 minutes. Therefore, ...