In AI, the term "heuristic" is used in the context of non-blind (i.e., informed) search and planning: the problem of finding a sequence of actions to find/generate a desired state from an initial state. Heuristics" are problem relaxations of the original problem. They get as input the current state/search node and output the cost of the relaxed solution from there to goal. This heuristic value is then used for search guidance.
Questions tagged [heuristics]
47 questions
13
votes
1 answer
Why is A* optimal if the heuristic function is admissible?
A heuristic is admissible if it never overestimates the true cost to reach the goal node from $n$. If a heuristic is consistent, then the heuristic value of $n$ is never greater than the cost of its successor, $n'$, plus the successor's heuristic…
Wizard
- 303
- 1
- 2
- 6
11
votes
5 answers
Are methods of exhaustive search considered to be AI?
Some programs do exhaustive searches for a solution while others do heuristic searches for a similar answer. For example, in chess, the search for the best next move tends to be more exhaustive in nature whereas, in Go, the search for the best next…
WilliamKF
- 2,493
- 1
- 24
- 31
11
votes
1 answer
Strategic planning and multi dimensional knapsack problem
I'm trying to find a planning approach to solve a problem that attempts to model learning of new material. We assume that we only have one resource such as Wikipedia, which contains a list of articles represented as a vector of knowledge it contains…
Artem
- 211
- 1
- 3
10
votes
1 answer
Why is my GAN more unstable with bigger networks?
I am working with generative adversarial networks (GANs) and one of my aims at the moment is to reproduce samples in two dimensions that are distributed according to a circle (see animation). When using a GAN with small networks (3 layers with 50…
Mafu
- 144
- 4
7
votes
3 answers
More effective way to improve the heuristics of an AI... evolution or testing between thousands of pre-determined sets of heuristics?
I'm making a Connect Four game where my engine uses Minimax with Alpha-Beta pruning to search. Since Alpha-Beta pruning is much more effective when it looks at the best moves first (since then it can prune branches of poor moves), I'm trying to come…
Inertial Ignorance
- 501
- 3
- 13
7
votes
1 answer
A* is similar to Dijkstra with reduced cost
According to this Wikipedia article
If the heuristic $h$ satisfies the additional condition $h(x) \leq d(x, y) + h(y)$ for every edge $(x, y)$ of the graph (where $d$ denotes the length of that edge), then $h$ is called monotone, or consistent. In…
Shrey Shrivastava
- 71
- 2
6
votes
4 answers
What else can boost iterative deepening with alpha-beta pruning?
I read about minimax, then alpha-beta pruning, and then about iterative deepening. Iterative deepening coupled with alpha-beta pruning proves to quite efficient as compared to alpha-beta alone.
I have implemented a game agent that uses iterative…
Suhail Gupta
- 161
- 1
- 5
6
votes
2 answers
How does A* search work given there are multiple goal states?
When I have read through the fundamentals of AI, I saw a situation (i.e., a search space) which is illustrated in the following picture.
These are the heuristic estimates:
h(B)=9
h(D)=10
h(A)=2
h(C)=1
If we use the A* algorithm, the node $B$ will…
hellojoshhhy
- 163
- 3
6
votes
1 answer
Can two admissable heuristics not dominate each other?
I am working on a project for my artificial intelligence class. I was wondering if I have 2 admissible heuristics, A and B, is it possible that A does not dominate B and B does not dominate A? I am wondering this because I had to prove if each…
JRowan
- 163
- 4
4
votes
1 answer
What are state-of-the-art ways of using greedy heuristics to initially set the weights of a Deep Q-Network in Reinforcement Learning?
I am interested in the current state-of-the-art ways to use quick, greedy heuristics in order to speed up the learning in a Deep Q-Network in Reinforcement Learning. In classical RL, I initially set the Q-value for a state-action pair (S,a) based on…
AlexGuevara
- 263
- 1
- 8
4
votes
1 answer
Is the minimum and maximum of a set of admissible and consistent heuristics also consistent and admissible?
Let's suppose I have a set of heuristics $H$ = {$h_1, h_2, ..., h_N$}.
If all heuristics in $H$ are admissible, does that mean that a heuristic that takes the $\min(H)$ (or $\max(H)$ for that matter) is also admissible?
If all heuristics in $H$ are…
ihavenoidea
- 255
- 2
- 11
3
votes
3 answers
What heuristic to use when doing A* search with multiple targets?
Usually, using the Manhattan distance as a heuristic function is enough when we do an A* search with one target. However, it seems like for multiple goals, this is not the most useful way. Which heuristic do we have to use when we have multiple…
dragan
- 31
- 1
- 2
3
votes
0 answers
Are there heuristics that play Klondike Solitaire well?
Are there heuristics that play Klondike Solitaire well?
I know there are some good exhaustive search solvers for Klondike Solitaire. The best one that I know of is Solvitaire (2019) which uses DFS, (see paper, code).
I searched the web for…
Cohensius
- 403
- 3
- 14
3
votes
1 answer
How to find proper parameter settings for a given optimization algorithm?
Is there any methodology to find proper parameter settings for a given meta-heuristic algorithm, e.g. the firefly algorithm or the cuckoo search? Is this an open issue in optimization? Is extensive experimentation, measurements and intuition the…
Jairo
- 91
- 1
3
votes
1 answer
Is A* with an admissible but inconsistent heuristic optimal?
I understand that, in tree search, an admissible heuristic implies that $A*$ is optimal. The intuitive way I think about this is as follows:
Let $P$ and $Q$ be two costs from any respective nodes $p$ and $q$ to the goal. Assume $P
Harry Stuart
- 161
- 3