Questions tagged [search]

For questions involving search algorithms and their use in artificial intelligence

Filter by
Sorted by
Tagged with
2
votes
1answer
62 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 ...
4
votes
1answer
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 ...
3
votes
1answer
187 views

Can minimax be used when both players want to increase their score?

If both the players want to increase their score (by selecting the highest or best cost path), can this be done using the minimax algorithm, or are there other algorithms for this purpose?
3
votes
1answer
1k views

Which are more memory efficient: uninformed or informed search algorithms?

I have extensively researched now for three days straight trying to find which algorithm is better in terms of which algorithm uses up more memory. I know uninformed algorithms, like depth-first ...
1
vote
0answers
53 views

How can we formulate a state-space search problem as a Markov decision process?

A Markov Decision Process (MDP) is a mathematical model for sequential decision-making in stochastic environments. Formally, we can define an MDP as a tuple $M = (S, A, p, \gamma)$, where $S$ is the ...
7
votes
2answers
3k views

What is the difference between search and planning?

I'm reading the book Artificial Intelligence: A Modern Approach (by Stuart Russell and Peter Norvig). However, I don't understand the difference between search and planning. I was more confused when I ...
3
votes
1answer
47 views

How DFS may expand the same state many times via different paths in an acyclic state space?

I am reading the book titled Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig (4th edition) and came across this sentence about depth-first search (page 79, line 12): For ...
5
votes
1answer
221 views

Why do zero-sum perfect information games satisfy the conditions of Von Neumann's theorem?

The Von Neumann's Minimax theorem gives the conditions that make the max-min inequality an equality. I understand the max-min inequality, basically ...
1
vote
2answers
4k views

When should the iterative deepening search and the depth-limited search be used?

When should the iterative deepening search (IDS), also called iterative deepening depth-first search (IDDFS), and the depth-limited search be used?
1
vote
0answers
116 views

How can we find the number of node expansions performed by BFS in this hexagonal map?

An agent aims to find a path on a hexagonal map, with an initial state $s_0$ in the center and goal state $s^*$ at the bottom as depicted below. The map is parametrized by the distance $n \geq 1$ ...
6
votes
2answers
2k views

Are leaf nodes included in the calculation of average branching factor for search trees?

In the search tree below, there are 11 nodes, 5 of which are leaves. There are 10 branches. Is the average branching factor given by 10/6, or 10/11? Are leaves included in the calculation? ...
3
votes
0answers
141 views

How can I formulate a nonogram problem as a constraint satisfaction problem?

I've just started learning CSP and I find it quite exciting. Now I'm facing a nonogram solving problem and I want to solve it using backtracking with CSP. The first problem that I face is that I ...
2
votes
2answers
818 views

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

For search algorithms with heuristic functions, performance of heuristic functions are measured by effective branching factor ${b^*}$ which involves total nodes expanded ${N}$ and depth of the ...
1
vote
0answers
42 views

What would happen if we set the evaluation function in the best-first search algorithm as the cost of paths taken to new nodes?

I am reading Artificial Intelligence: A Modern Approach. In Chapter 3, Section 3.3.1, The best-first search algorithm is introduced. We learn that in each iteration, this algorithm chooses which node ...
2
votes
1answer
3k views

Why do we use a last-in-first-out queue in depth-first search?

Why do we use a last-in-first-out (LIFO) queue in the depth-first search algorithm? In the breadth-first search algorithm, we use a first-in-first-out (FIFO) queue, so I am confused.
4
votes
1answer
186 views

How do I train a bot to solve Katona style problems?

Cognitive psychology is researched since the 1940s. The idea was to understand human problem solving and the importance of heuristics in it. George Katona (an early psychologist) published in the ...
8
votes
2answers
218 views

Are there local search algorithms that make use of memory to give better solutions?

I have been studying local search algorithms such as greedy hill-climbing, stochastic hill-climbing, simulated annealing, etc. I have noticed that most of these methods take up very little memory as ...
1
vote
1answer
177 views

How does the MCTS tree look like?

I have come across the Monte Carlo tree search (MCTS) algorithm, but I can't find what the tree should look like. For example, does it still represent a minimax process, i.e. player 1 from the root ...
1
vote
1answer
163 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 ...
1
vote
1answer
347 views

Is this ExpectiMinimax Tree correctly drawn?

I need help with ExpectiMinimax problem: Start a game. The first player flips a coin. The second player flips a coin. The first player decides if he wants to flip another coin. The second player ...
1
vote
2answers
41 views

How do the BFS and DFS search algorithms choose between nodes with the "same priority"?

I am currently taking an Artificial Intelligence course and learning about DFS and BFS. If we take the following example: From my understanding, the BFS algorithm will explore the first level ...
4
votes
2answers
133 views

What is the proof that the branch and bound algorithm always finds optimal path in a graph?

I've been studying Branch and Bound's graph algorithm and I hear it always finds the optimal path because it uses previously found solutions to find others However, I haven't been able to find a ...
5
votes
1answer
7k views

How does the uniform-cost search algorithm work?

What is the uniform-cost search (UCS) algorithm? How does it work? I would appreciate seeing a graphical execution of the algorithm. How does the frontier evolve in the case of UCS?
3
votes
1answer
2k views

How does best-first search differ from hill-climbing?

How does best-first search differ from hill-climbing?
3
votes
1answer
70 views

What does "unknown search spaces" mean in the context of Evolutionary Algorithms?

In the article Multi-Verse Optimizer: a nature-inspired algorithm for global optimization (DOI 10.1007/s00521-015-1870-7), it's written The results of the real case studies also demonstrate the ...
0
votes
0answers
15 views

What is an efficient way to implement an contextual search for a search engine?

So I am working on a search engine and want to implement a contextual search for my search engine but would like to get some advice before I start working on it. I have a basic knowledge of A.I. like ...
0
votes
0answers
12 views

Are ranking models considered discriminative?

I'm developing a model that ranks entries based on cosine similarity to a query. Since it doesn't actually define a boundary between x and y I initially believed that such ranking models are not ...
1
vote
1answer
76 views

How do I create the search tree for DFS applied to a grid map?

I have been working through some search tree problems and came across this one: Assume that that the algorithm has a closed list and that nodes are added to the frontier in the following order: Up, ...
0
votes
0answers
34 views

Fine tuning a BERT model for text classification

An article written by Jay Alammar (http://jalammar.github.io/a-visual-guide-to-using-bert-for-the-first-time/) on using a BERT transformer for text classification. The article mentions the following ...
3
votes
1answer
2k views

Why does the adversarial search minimax algorithm use Depth-First Search (DFS) instead of Breadth-First Search (BFS)?

I understand that the actual algorithm calls for using Depth-First Search, but is there a functionality reason for using it over another search algorithm like Breadth-First Search?
4
votes
1answer
257 views

How do we find the length (depth) of the game tic-tac-toe in adversarial search?

When we perform the tic-tac-toe game using adversarial search, I know how to make a tree. Is there a way to find the depth of the tree, and which level is the last level?
18
votes
1answer
25k views

What is the difference between tree search and graph search?

I have read various answers to this question at different places, but I am still missing something. What I have understood is that a graph search holds a closed list, with all expanded nodes, so ...
12
votes
1answer
17k views

Why is A* optimal if the heuristic function is admissible?

A heuristic is admissible if it never overestimates the true cost to reach the goal node from $n$. If a heuristic is consistent, then the heuristic value of $n$ is never greater than the cost of its ...
2
votes
1answer
53 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?
4
votes
2answers
4k 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 ...
0
votes
1answer
61 views

Does a differential evolution algorithm mutate its population during a generation?

I'm implementing a differential evolution algorithm and when it comes to evolving a population, the page I am referencing is vague on how the new population is generated. https://en.wikipedia.org/wiki/...
0
votes
1answer
85 views

Are hill climbing variations always optimal and complete?

Are hill climbing variations (like steepest ascent hill climbing, stochastic hill climbing, random restart hill climbing, local beam search) always optimal and complete?
1
vote
2answers
187 views

Is there any situation in which breadth-first search is preferable over A*?

Is there any situation in which breadth-first search is preferable over A*?
2
votes
1answer
5k views

What is a successor function (in CSPs)?

In Constraint Satisfaction Problems (CSPs), a state is any data structure that supports a successor function, a heuristic function, and a goal test. In this context, what is a successor function?
2
votes
0answers
1k views

How to improve the efficiency of the backtracking search in CSPs?

Backtracking search is the basic uninformed search algorithm for constraint satisfaction problems (CSPs). How could we improve the efficiency of the backtracking search in CSPs?
3
votes
1answer
58 views

What are the common techniques one could use to deal with collisions in a transposition table?

Consider an iterative deepening search using a transposition table. Whenever the transposition table is full, what are common strategies applied to replace entries in the table? I'm aware of two ...
0
votes
0answers
32 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 ...
1
vote
1answer
558 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 ...
4
votes
1answer
251 views

Given an image and two points $A$ and $B$ on that image, how could we find a path from $A$ to $B$?

If we have a search or path-finding problem, A* and Dijkstra's algorithm require that we formulate it as a search in a graph with nodes and connections between these nodes. If there are obstacles, we ...
2
votes
1answer
222 views

How to transform a PDDL to search?

I have a question about search and planning: I still haven't understood the difference from the two, but they seem very similar to me; here is a question I am struggling with: "Having formulated a ...
6
votes
1answer
822 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 ...
0
votes
0answers
25 views

Satisficing searches - how does speedy search compensate for higher execution costs

While reading AI: A Modern Approach (4th ed), I have some difficulty in coming to terms with the usefulness of a satisficing search. Generally speaking, I understand that in real life situations we ...
3
votes
2answers
309 views

Is a good evaluation function as good as any of the extensions of alpha-beta pruning?

I would like to know if having a really good evaluation function is as good as using any of the extensions of alpha-beta pruning, such as killer moves or quiescence search?
1
vote
1answer
122 views

How can I calculate the shortest path between two 2d vector points in an environment with obstacles?

I have a 2D plane, with a fixed height and width of 10M. The plane has an agent (or robot) in the point $(1, 2.2)$, and an electric outlet in the point $(8.2, 9.1)$. The plane has a series of ...
6
votes
1answer
285 views

To deal with infinite loops, should I do a deeper search of the best moves with the same value, in alpha-beta pruning?

I have implemented minimax with alpha-beta pruning to play checkers. As my value heuristic, I am using only the summation of material value on the board regardless of the position. My main issue lays ...