Questions tagged [heuristic-functions]

For questions about heuristic functions in the context of search algorithms (and other AI subfields).

Filter by
Sorted by
Tagged with
2 votes
0 answers
78 views

Which heuristic function should I use for the ColorShapeLinks game?

For learning purposes, I am trying to implement the minimax algorithm for the ColorShapeLinks game, which is similar to connect 4, except the fact that it combines both shape and color as the winning ...
user avatar
  • 21
2 votes
1 answer
69 views

Is $\min(h_1(s),\ h_2(s))$ consistent?

If $h_1(s)$ is a consistent heuristic and $h_2(s)$ is a admissible heuristic, is $\min(h_1(s),\ h_2(s))$ consistent?
user avatar
  • 21
0 votes
0 answers
117 views

Comparing heuristics in A* search and rescue operation

I was reading a research paper titled A Comparative Study of A-star Algorithms for Search and rescue in Perfect Maze (2011). I have some doubts regarding it: 1. The Evaluation Function of $\mathrm{A}^...
user avatar
2 votes
0 answers
35 views

How to find good features for a linear function approximation in RL with large discrete state set?

I've recently read much about feature engineering in continuous (uncountable) feature spaces. Now I am interested what methods exist in the setting of large discrete state spaces. For example consider ...
user avatar
  • 121
2 votes
1 answer
132 views

If $h_1(n)$ is admissible, why does A* tree search with $h_2(n) = 3h_1(n)$ return a path that is at most thrice as long as the optimal path?

Consider a heuristic function $h_2(n) = 3h_1(n)$. Where $h_1(n)$ is admissible. Why are the following statements true? $A^*$ tree search with $h_2(n)$ will return a path that is at most thrice as ...
user avatar
3 votes
1 answer
242 views

Strategy for playing a board game with Minimax algorithm

I want to build a player for the following game: You have a board where position 1 is your player, position 2 is the rival ...
user avatar
  • 81
1 vote
1 answer
784 views

What is the difference between the heuristic function and the evaluation function in A*?

I am reading college notes on state search space. The notes (which are not publicly available) say: To do state-search space, the strategy involves two parts: defining a heuristic function, and ...
user avatar
2 votes
1 answer
822 views

If $h_i$ are consistent and admissible, are their sum, maximum, minimum and average also consistent and admissible?

Consider the following question: $n$ vehicles occupy squares $(1, 1)$ through $(n, 1)$ (i.e., the bottom row) of an $n \times n$ grid. The vehicles must be moved to the top row but in reverse order; ...
user avatar
3 votes
2 answers
1k views

Why is the effective branching factor used for measuring performance of a heuristic function?

For search algorithms with heuristic functions, the performance of heuristic functions are measured by the effective branching factor ${b^*}$, which involves the total number of nodes expanded ${N}$ ...
user avatar
  • 165
4 votes
2 answers
5k views

If an heuristic is not admissible, can it be consistent?

I am solving a problem in which, according to the given values, the heuristic is not admissible. According to my calculation from other similar problems, it should be consistent, as well as keeping in ...
user avatar
  • 41
6 votes
1 answer
1k views

How do we determine whether a heuristic function is better than another?

I am trying to solve a maze puzzle using the A* algorithm. I am trying to analyze the algorithm based on different applicable heuristic functions. Currently, I explored the Manhattan and Euclidean ...
user avatar
  • 303
2 votes
1 answer
937 views

Why isn't Nilsson's Sequence Score an admissible heuristic function?

I understand what an admissible heuristic is, I just don't know how to tell whether one heuristic is admissible or not. So, in this case, I'd like to know why Nilsson's sequence score heuristic ...
user avatar
4 votes
1 answer
3k views

What is a good heuristic function for A* to solve the "blocks world" game?

I am developing a heuristic solution for the blocks world problem. I tried using the number of blocks out of place as my $h(n)$. It seems a little ineffective. Can someone please point out a suitable ...
user avatar