Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [search]

For questions involving search algorithms and their use in artificial intelligence

Filter by
Sorted by
Tagged with
0 votes
0 answers
12 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 ...
hegash's user avatar
  • 101
0 votes
1 answer
15 views

Could someone give a simple example of nondeterministic sensing?

The Artificial Intelligence: A Modern Approach, 4th edition book introduces a PERCEPTS function that returns a set of possible percepts when the sensing is nondeterministic. Could someone please give ...
user153245's user avatar
1 vote
1 answer
25 views

Time complexity of BFS in O(b^n) - Constant of Big-O-Notation?

Section 3.4.1 (Breadth-first search) of the book "Artificial Intelligence: A Modern Approach" (4th edition, by Norvig and Russell) estimates the total number of generated nodes for time ...
DasElias's user avatar
  • 111
2 votes
2 answers
166 views

What is the state space of digit recognition agent on a grid of 28 x 28 pixels?

I encountered the following problem as part of a quiz: Imagine you are designing a digit recognition agent and you want to analyze the state space of this problem. Given a binary image of 28 x 28 grid ...
Dawood Ahmad's user avatar
2 votes
2 answers
39 views

Why does an action cost function dependes on result state in search problems?

In the famous AI book Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig (4th edition), in chapter 3, the action cost function of a problem solver agent denoted as $c(s, a, ...
user153245's user avatar
0 votes
1 answer
55 views

Does Breadth-First Graph Search need to store all all unique generated states?

I am reading Artificial Intelligence: A Modern Approach by Russel & Norvig. As I understood it, a breadth-first graph search stores explored states instead of explored nodes (where "nodes&...
ddk's user avatar
  • 1
0 votes
1 answer
94 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$ ...
Hugh Mann's user avatar
1 vote
0 answers
27 views

Search recall optimization - what appropriate loss function to use?

I am studying machine learning and wanted to work on a project of my own so that I have better chances after graduating college. I'm studying the application of ML to improve searches using a toy ...
user9343456's user avatar
0 votes
0 answers
28 views

Query modification for search using AI

I have a problem statement that I'm struggling to formulate as a machine learning framework. There is a huge client database of documents - we're trying to come up with an efficient way of querying ...
user9343456's user avatar
0 votes
1 answer
383 views

What does the branching factor mean in the time complexity of Breadth-First Search (BFS)

Can someone explain where my math is off here? I am confused on the b - Branching Factor and how to calculate the worst-case scenario when running BFS. In a worst-case scenario BFS would have to hit ...
ImposterX1's user avatar
1 vote
2 answers
2k views

What is the best Text-to-speech model available open-source?

I tried a couple of different websites and libraries. Also found this topic from 3.5 years ago - What are the current open source text-to-audio libraries? It looks like nobody published anything in ...
Yevhen Salitrynskyi's user avatar
0 votes
1 answer
77 views

Which search algorithm expands nodes closest to the goal?

I want to know which search algorithm among A* and Best-First Search and Greedy First Search expands nodes closest to the goal. I have three opinions about A* and Best-First Search and Greedy First ...
ndycuong's user avatar
1 vote
0 answers
158 views

Is there an ANN vector-search index that supports incremental ingestion and deletion of elements?

I have looked at a few libraries for ANN search of high dimensional vectors. Although impressive, they come with a huge baggage of fine print. Many of them only support ingesting the vectors in one ...
morpheus's user avatar
  • 294
0 votes
0 answers
107 views

How do I construct a state space that shows that Greedy Best First Search is not complete while A* is?

Construct a state space with appropriate heuristics and local costs. Show that Greedy Best First search is not complete for the state space. Also illustrate A* is complete and guarantees solution for ...
npsulav's user avatar
0 votes
0 answers
46 views

How many iterations are required for iterative-lengthening search when step costs are drawing from a continuos range [0, 1]?

I just started studying the book AI A modern Approach and I am lost on the following question. Could someone explain please or provide reference paper to understand. Consider the step costs drawn from ...
Mihai Șerban 's user avatar
1 vote
2 answers
80 views

Is manual binding output to input also an AI?

I know AI is primarly training a machine by samples of input-output in order it would learn itself about relations between the input and the output. What if I manually add the relations? Is that still ...
stkuser's user avatar
  • 13
0 votes
1 answer
535 views

Can A* be non-optimal if it uses an admissible but inconsistent heuristic with graph search?

The book "Artificial Intelligence: A Modern Approach" (4th edition, global version) says "With an admissible heuristic, A* is cost-optimal...". An admissible heuristic is one ...
numq's user avatar
  • 1
0 votes
0 answers
50 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 ...
Angelo's user avatar
  • 211
0 votes
2 answers
3k views

What does consistency of heuristic intuitively mean in the A* algorithm and why are consistent heuristics monotonic?

Could someone give the intuition behind consistency of heuristic function in the A* algorithm? From wikipedia: Every node i will give an estimate that, after accounting for the cost to reach i + 1, ...
learner's user avatar
  • 13
1 vote
0 answers
526 views

Does iterative deepening depth-first search expand at most twice as many nodes as breadth-first search?

My understanding is that iterative deepening search is roughly equivalent to breadth-first search, except instead of keeping all visited nodes in memory, we regenerate nodes as needed, trading off ...
xojfqa's user avatar
  • 101
0 votes
0 answers
620 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 ...
Nova's user avatar
  • 133
1 vote
0 answers
126 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 ...
Baffo rasta's user avatar
1 vote
1 answer
518 views

How to find the order in which DFS algorithm will inspect the nodes?

I have been taking Artificial Intelligence course in College. I came upon this problem. Now here I have to find the order in which DFS algorithm inspects the nodes and what is the path from Start to ...
astraltrinity's user avatar
0 votes
1 answer
3k views

Why is depth-limited is preferable to minimax without depth limited

I have read about a question that says the following: Why is depth-limited minimax preferable to minimax? One of the wrong answers was: The depth-limited minimax will achieve the same output as ...
Ahmed's user avatar
  • 1
1 vote
0 answers
169 views

Best algorithm for the Word Ladder puzzle

What would be the best performing algorithm to solve the Word Ladder problem, in terms of guaranteed finding of the shortest solution in the shortest possible time? Is it BFS, DFS, A*, IDA* or another ...
Bill Kavvas's user avatar
0 votes
1 answer
555 views

Where can I find Norvig's version of the pseudocode for the A* search algorithm?

Can anybody point me to a link to Peter Norvig's version of the A* pseudocode. I've googled it interminably but found nothing. It's the version that uses the Unexplored/Frontier/Explored data ...
Fred Friendly's user avatar
0 votes
0 answers
116 views

Hierarchical Navigable Small World Graphs : Expected Number of Steps in a Layer

Paper: Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs In the Search Complexity section, the author estimates that the expected number of steps ...
p1p13 's user avatar
3 votes
1 answer
207 views

Is there an error in A* optimality proof Russel-Norvig 4th edition?

In "AI: A Modern Approach", 4th edition, by Russell and Norvig, they give a purported proof that A* is cost-optimal for any admissible heuristic. The given proof seems most certainly wrong. ...
vdbuss's user avatar
  • 81
3 votes
1 answer
754 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 ...
user153245's user avatar
2 votes
2 answers
1k 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 ...
Sergio's user avatar
  • 123
3 votes
1 answer
169 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 ...
Commander's user avatar
  • 137
1 vote
1 answer
509 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, ...
Gerhardus Carinus's user avatar
2 votes
1 answer
198 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?
hello's user avatar
  • 21
1 vote
0 answers
176 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 ...
Hamed's user avatar
  • 21
0 votes
1 answer
66 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/...
gator's user avatar
  • 75
0 votes
1 answer
1k 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?
user avatar
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 ...
Mahesha999's user avatar
1 vote
2 answers
2k 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*?
JackoJackie's user avatar
0 votes
0 answers
44 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 ...
Manny's user avatar
  • 21
1 vote
1 answer
2k 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 ...
Slowat_Kela's user avatar
2 votes
0 answers
650 views

Why do we use the tree-search version of breadth-first search or A*?

In Artificial Intelligence A Modern Approach, search algorithms are divided into tree-search version and graph-search version, where the graph-search version keeps an extra explored set to avoid ...
Gu Liqi's user avatar
  • 21
2 votes
1 answer
365 views

When does IDA* consider the goal has been found?

I was reading about IDA* and I found this link explaining IDA* and providing an animation for it. Here is a picture of the solution. I know what is the cutoff condition (it depends on F), and the ...
yaminoyuki's user avatar
2 votes
2 answers
2k views

What is the difference between the uniform-cost search and Dijkstra's algorithm?

Every computer science student (including myself, when I was doing my bachelor's in CS) probably encountered the famous single-source shortest path Dijkstra's algorithm (DA). If you also took an ...
nbro's user avatar
  • 40.8k
4 votes
1 answer
2k views

Why is the completeness of UCS guaranteed only if the cost of every step exceeds some small positive constant?

I was reading Artificial Intelligence: A Modern Approach 3rd Edition, and I have reached to the UCS algorithm. I was reading the proof that UCS is complete. The book state that: Completeness is ...
Kais Hasan's user avatar
3 votes
2 answers
4k views

If uniform cost search is used for bidirectional search, is it guaranteed the solution is optimal?

If uniform cost search is used for both the forward and backward search in bidirectional search, is it guaranteed the solution is optimal?
user avatar
1 vote
1 answer
1k views

What is the space complexity of bidirectional search?

Is the space complexity of the bidirectional search, where the breadth-first search is used for both the forward and backward search, $O(b^{d/2})$, where $b$ is the branching factor and $d$ the length ...
user avatar
2 votes
1 answer
6k views

What is the space complexity of breadth-first search?

When using the breadth-first search algorithm, is the space complexity $O(b^d)$, where $b$ is the branching factor and $d$ the length of the optimal path (assuming that there is indeed one)?
user avatar
1 vote
1 answer
2k views

What is the space complexity of iterative deepening search?

When using iterative deepening, is the space complexity, $O(d)$, where $b$ is the branching factor and $d$ the length of the optimal path (assuming that there is indeed one)?
user avatar
2 votes
1 answer
427 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 ...
Fraser Gilbert's user avatar
1 vote
0 answers
60 views

Which method of tree searching should be used for this board game?

Suppose the following properties of a board game: High branching factor in the beginning of the game (~500) which slowly tends towards 0 at the end of the game Evaluation of the any given board ...
Tauist's user avatar
  • 111