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.
20 questions with no upvoted or accepted answers
3
votes
0
answers
592
views
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, (...
- 413
3
votes
0
answers
1k
views
Can the degree and minimum remaining values heuristics be used in conjunction?
I am currently studying constraint satisfaction problems and have come across two heuristics for variable selection. The minimum remaining values(MRV) heuristic and the degree heuristic.
The MRV ...
- 1,291
3
votes
0
answers
359
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 ...
3
votes
0
answers
442
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. ...
- 31
2
votes
0
answers
158
views
How does heuristic work with multiple agents?
I have a question for heuristic search with multiple agents. I know how heuristic search works with one agent (ex. one Pacman) but I don't really understand it with multiple agents. Let's say we have ...
- 121
2
votes
0
answers
64
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 ...
- 143
2
votes
0
answers
55
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 ...
- 121
2
votes
0
answers
58
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 ...
- 29
1
vote
0
answers
137
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 ...
- 111
1
vote
1
answer
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 ...
- 151
1
vote
0
answers
34
views
CSP heuristic to simultaneously reduce conflicts and find near optimal assignment
I am trying to design a good heuristic to solve a constraint satisfaction problem (CSP). I think that a possible heuristic to use is
$$h_1(\text{state}) = \text{number of conflicts in state}$$
However,...
- 11
1
vote
0
answers
29
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 ...
- 111
0
votes
0
answers
54
views
Train AI to schedule a league with certain constraints
I need some suggestions on options to look into to train an AI model to schedule sporting events based on certain constraints. Contraints like no back to back games, 2 games per day, 1 per week, keep ...
- 101
0
votes
0
answers
116
views
Minimum remaining values heuristic more powerful than degree heuristic
When selecting a new variable to assign a value to in CSP assignment backtracking search, common heuristics include:
MRV heuristic: pick the unassigned variable with the fewest remaining values in ...
- 101
0
votes
0
answers
141
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 ...
- 1
0
votes
0
answers
71
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 ...
- 211
0
votes
0
answers
806
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 ...
- 143
0
votes
0
answers
327
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 ...
- 21
-1
votes
0
answers
59
views
Incorrect node expansion in game board with A* search
I have the following game board below, and we're using A* search to find the optimal path from the agent to the key. There are 8 directions. Up, down, left, right have a cost of 1, and diagonal ...
- 19
-1
votes
0
answers
806
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 ...
- 6,233