Artificial Intelligence Stack Exchange
Artificial Intelligence Stack Exchange

Questions tagged [heuristic-functions]

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

13 questions
7
votes
1 answer

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 distances. Which other heuristic functions are…
m2rik
  • 333
  • 1
  • 9
4
votes
1 answer

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 heuristic for the problem and explain with a few…
user3758749
  • 41
  • 1
  • 3
4
votes
2 answers

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 mind the values, but the solution says it's not…
Awa
  • 41
  • 1
  • 2
3
votes
1 answer

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 player, -1 is a blocked cell and some positive value is a bonus. You can move up, down, left, or right. Also, each bonus has a…
vesii
  • 81
  • 3
3
votes
2 answers

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}$ and the depth of the solution ${d}$. I'm not able…
KGhatak
  • 165
  • 6
2
votes
0 answers

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 conditions, with a shape having priority over…
Errata
  • 21
  • 2
2
votes
1 answer

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?
hello
  • 21
  • 1
2
votes
0 answers

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 a board game with grid as a basic layout. Each…
s1624210
  • 121
  • 1
2
votes
1 answer

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 long as the optimal path. $h_2(n) + 1$ is…
Jia Rong
  • 21
  • 2
2
votes
1 answer

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; so the vehicle $i$ that starts in $(i, 1)$ must…
Mostafa Ghadimi
  • 177
  • 12
2
votes
1 answer

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 function isn't admissible.
Jay Critch
  • 343
  • 1
  • 7
1
vote
1 answer

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 identifying an evaluation function. The heuristic is…
Slowat_Kela
  • 287
  • 2
  • 9
0
votes
0 answers

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}^{*}(2)[5]$…
user46328
  • 3
  • 2