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
-1
votes
0answers
26 views

How to know suitable search algorithm from heuristic values?

If we consider the following evaluation function with path cost $g(n)$ and admissible heuristic $h(n)$ for a heuristic search problem. $ f(n) = (w*g(n)) + ((1-w) + h(n)) $ Where the value of w is $ 0....
2
votes
0answers
27 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 ...
2
votes
1answer
71 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 ...
3
votes
1answer
102 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 ...
1
vote
1answer
187 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 ...
2
votes
1answer
407 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; ...
5
votes
1answer
465 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 ...
2
votes
1answer
499 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 ...