Stack Overflow
Stack Overflow

Questions tagged [heuristics]

Heuristics refers to the use of algorithms to deal with highly complex problems.

Heuristics refers to the use of algorithms to deal with highly complex problems. A heuristic approach seeks to provide an approximate solution for a problem that is otherwise unsolvable.

683 questions
322
votes
22 answers

Pacman: how do the eyes find their way back to the monster hole?

I found a lot of references to the AI of the ghosts in Pacman, but none of them mentioned how the eyes find their way back to the central ghost hole after a ghost is eaten by Pacman. In my implementation I implemented a simple but awful solution. I…
RoflcoptrException
  • 51,941
  • 35
  • 152
  • 200
114
votes
12 answers

What is the difference between a heuristic and an algorithm?

What is the difference between a heuristic and an algorithm?
streetparade
  • 32,000
  • 37
  • 101
  • 123
85
votes
4 answers

What is the minimum cost to connect all the islands?

There is a grid of size N x M. Some cells are islands denoted by '0' and the others are water. Each water cell has a number on it denoting the cost of a bridge made on that cell. You have to find the minimum cost for which all the islands can be…
vaibhavatul47
  • 2,766
  • 4
  • 29
  • 42
81
votes
6 answers

What are some algorithms for comparing how similar two strings are?

I need to compare strings to decide whether they represent the same thing. This relates to case titles entered by humans where abbreviations and other small details may differ. For example, consider the following two titles: std::string first =…
WilliamKF
  • 41,123
  • 68
  • 193
  • 295
66
votes
11 answers

Rule of thumb for choosing an implementation of a Java Collection?

Anyone have a good rule of thumb for choosing between different implementations of Java Collection interfaces like List, Map, or Set? For example, generally why or in what cases would I prefer to use a Vector or an ArrayList, a Hashtable or a…
hydeph
  • 857
  • 1
  • 12
  • 14
50
votes
8 answers

Generating a tower defense maze (longest maze with limited walls) - near-optimal heuristic?

In a tower defense game, you have an NxM grid with a start, a finish, and a number of walls. Enemies take the shortest path from start to finish without passing through any walls (they aren't usually constrained to the grid, but for simplicity's…
BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
49
votes
3 answers

What is the difference between heuristics and metaheuristics?

After some research about algorithms I found two terms which confuses me. I've read at least 20 papers and yet, there aren't any clear definition about either. I hope someone can help me tell the difference between heuristics and metaheuristics…
Nico Liu
  • 845
  • 2
  • 9
  • 14
47
votes
4 answers

Consistent and Admissible Heuristics

Any consistent heuristic is also admissible. But when is a heuristic admissible but not consistent (monotone)? Please provide an example in which this is the case.
RoarG
  • 793
  • 1
  • 7
  • 20
43
votes
7 answers

Design patterns for converting recursive algorithms to iterative ones

Are there any general heuristics, tips, tricks, or common design paradigms that can be employed to convert a recursive algorithm to an iterative one? I know it can be done, I'm wondering if there are practices worth keeping in mind when doing so.
fbrereto
  • 35,429
  • 19
  • 126
  • 178
40
votes
5 answers

A* Admissible Heuristic for die rolling on grid

I need some help finding a good heuristic for the following problem: You are given an R-by-C grid and a six-sided die. Let start and end be two distinct cells on this grid. Find a path from start to end such that the sum of the faces of the…
Paul Manta
  • 30,618
  • 31
  • 128
  • 208
36
votes
5 answers

Split speech audio file on words in python

I feel like this is a fairly common problem but I haven't yet found a suitable answer. I have many audio files of human speech that I would like to break on words, which can be done heuristically by looking at pauses in the waveform, but can anyone…
user3059201
  • 775
  • 2
  • 7
  • 11
32
votes
3 answers

Algorithm to detect photo orientation

I would like to rotate photos automatically, even when EXIF metadata about the image orientation is not available. Are there any good algorithms for detecting the orientation of a photo? The images are photographs from a digital camera. The…
Luke Francl
  • 31,028
  • 18
  • 69
  • 91
31
votes
8 answers

Travelling Salesman with multiple salesmen?

I have a problem that has been effectively reduced to a Travelling Salesman Problem with multiple salesmen. I have a list of cities to visit from an initial location, and have to visit all cities with a limited number of salesmen. I am trying to…
dustin ledezma
  • 615
  • 2
  • 6
  • 10
26
votes
11 answers

PacMan: what kinds of heuristics are mainly used?

Beside A*, BFS, DFS and the like, what are other good path-finding algorithms/heuristics popularly used in Pacman? I don't think the ones I mentioned will work if there're more than one fruits for pacman to find. I need some good path-finding…
IcySnow
  • 851
  • 2
  • 14
  • 23
26
votes
5 answers

What's the difference between greedy and heuristic algorithm?

What's the difference between greedy and heuristic algorithm? I have read some articles about the argument and it seems to me that they are more or less the same type of algorithm since their main characteristic is to choose the best (local) option…
Giuseppe Pes
  • 7,772
  • 3
  • 52
  • 90
1
2 3
…
45 46