# Questions tagged [heuristics]

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.

47 questions
Filter by
Sorted by
Tagged with
84 views

### How do we know that $c(n,a,G) = h^{\ast}(n)$, in the proof that if a heuristic is consistent then it is admissible?

I found a proof that if a heuristic $h$ is consistent, then it is admissible, but I'm confused by one of the steps in the proof. The proof is by induction on $k$, the number of actions from a node $n$ ...
1 vote
57 views

### Knapsack of mixture with constraints

I'm trying to find the optimized mixture for a specific set of substances. Each of those substances have characteristics that I want to optimize in the mixture (some characteristics I want to minimize ...
1 vote
2k views

### Determining minimal state representation for maze game

I came across this question set. It asks following question: Let’s revisit our bug friends from assignment 2. To recap, you control one or more insects in a rectangular maze-like environment with ...
104 views

### How to determine that an heuristic is admissible

An heuristic is admissible if never overestimates the real cost to reach the goal. In order to prove that an heuristic $h$ is admissible we need to prove that for every state $s$ in the state space we ...
538 views

### 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 ...
109 views

### What is a good algorithm (and a heuristic) to find the shortest path in a puzzle game?

In a 3D world, there is a Robot, boxes, and switches. The robot's job is to carry boxes (one box at a time) and put them on top of switches to solve the level. All switches must have a box on top for ...
49 views

### What is the theory behind rejecting too good heuristics in search problems?

Currently I have found that there is an article in which a search problem is posed and to solve it a heuristic is proposed which, in essence, is the solution of the problem itself. I seem to remember ...
336 views

### how to apply crossover and mutation rates in genetic algorithm?

I'm working with genetic programming and let's say I have the following operator: pop_size = 100 Crossover ratio = 0.4 Mutation Ratio = 0.2 Selection Ratio = 0.1 What is exactly the next generation ...
572 views

### Why is the greedy heuristic admissible and consistent for food at corners problem, but not for food anywhere problem?

UCBerkley has a great Intro to AI course (CS188) where you can practice coding up search algorithms. One of the exercises (question 6), asks to generate a heuristic that will have Pacman find all 4 ...
111 views

### Agents meeting in a directed connected graph

We have a directed connected graph, where nodes are places one can go to and edges are the "roads" between places. We have K agents whose goal is to meet in one node. Agents start in ...
1 vote
123 views

### Is N the total number of nodes in the frontier plus the number of nodes in the explored list?

I'm studying fundamentals of AI from the classic Russell-Norvig book (3rd edition). I have a small doubt about the effective branching factor, which is defined as follows (section 3.6.1, p. 103): One ...
251 views

### Is possible to perform an early goal test with A* using a consistent heuristic?

I have a doubt about A* goal test. As far as I know an early goal test is performed when a node (representing a certain state) is inserted in the frontier or, to conform with AIMA terminology, when is ...
3k views

336 views

### How to choose the weights for a linear combination of heuristic functions?

I need to write a minimax algorithm with alpha-beta pruning in limited time for the 2048 game. I know expectimax is better for this work. Assume I wrote different heuristic functions. If I want to ...
206 views

### 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 ...
63 views

### What kind of decision rule algorithm is usable in this situation?

I am trying to write an AI to a game, where there is no real adversary. This means, that only the AI player has choices in which move to perform, his opponent may or may not react to the move the AI ...
1k views

### 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 ...
423 views

### Snake path finding variant : Algorithm choice

I am working on a project which maps to a variant of path finding problem. I am new to this area and I would be very grateful if you could give suggestions/ point to libraries for relevant algorithms. ...
1 vote
27 views

### Approach for data transformation needed

I am looking for an algorithm to transform an input data to a goal data using a series of operations. The shorter the series the better. The following is known: the input data the goal data input ...
51 views

### How to open up a rigid structure made of connected panels?

By open up I mean slightly open up so that a theoretical structure of panels with no width looks three-dimensional. The original structure being an ideal object where any number several panels can ...
800 views

### Has Tic-Tac-Toe been solved with a single heuristic?

By this I mean a single axiom for placement. (I'm working on a solution that involves positional valuation and vectors, and appears to be solid, but my assumption would be this has been done ...