Questions tagged [search]

For questions involving search algorithms and their use in artificial intelligence

Filter by
Sorted by
Tagged with
0 votes
0 answers
9 views

Image suggestions using feature extractor + ANN index

I am trying to build an image suggestion engine using resnet151 as a feature extractor and right now I am testing Annoy and Faiss as the ANN. I am having some issues with images that have similar ...
user avatar
1 vote
0 answers
21 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 ...
user avatar
1 vote
1 answer
41 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 ...
user avatar
0 votes
1 answer
324 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 ...
user avatar
  • 1
1 vote
0 answers
58 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 ...
user avatar
0 votes
1 answer
75 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 ...
user avatar
0 votes
0 answers
44 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 ...
user avatar
0 votes
0 answers
34 views

What is the relationship between classical searching algorithms in AI and machine learning?

I think the relationship between the local search algorithms in AI for continuous spaces and Machine Learning is somewhat clear, as most of these search algorithms use gradient-based methods for ...
user avatar
  • 101
2 votes
1 answer
94 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. ...
user avatar
  • 71
3 votes
1 answer
96 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 ...
user avatar
1 vote
2 answers
164 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 ...
user avatar
  • 113
3 votes
1 answer
90 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 ...
user avatar
  • 137
0 votes
0 answers
19 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 ...
user avatar
0 votes
0 answers
15 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 ...
user avatar
  • 1
1 vote
1 answer
170 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, ...
user avatar
2 votes
1 answer
76 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?
user avatar
  • 21
1 vote
0 answers
60 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 ...
user avatar
  • 21
0 votes
1 answer
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/...
user avatar
  • 75
0 votes
1 answer
397 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
461 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 ...
user avatar
  • 131
1 vote
2 answers
393 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*?
user avatar
0 votes
0 answers
34 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 ...
user avatar
  • 21
1 vote
1 answer
838 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 ...
user avatar
2 votes
0 answers
126 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 ...
user avatar
  • 21
2 votes
1 answer
167 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 ...
user avatar
2 votes
1 answer
926 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 ...
user avatar
  • 34.3k
4 votes
1 answer
421 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 ...
user avatar
3 votes
2 answers
2k 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
565 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
1 vote
1 answer
2k 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
742 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
1 vote
1 answer
231 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 ...
user avatar
1 vote
0 answers
32 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 ...
user avatar
  • 111
9 votes
2 answers
1k views

Why is depth-first search an artificial intelligence algorithm?

I'm new to the artificial intelligence field. In our first chapters, there is one topic called "problem-solving by searching". After searching for it on the internet, I found the depth-first ...
user avatar
  • 93
2 votes
1 answer
970 views

Is A* with an admissible but inconsistent heuristic optimal?

I understand that, in tree search, an admissible heuristic implies that $A*$ is optimal. The intuitive way I think about this is as follows: Let $P$ and $Q$ be two costs from any respective nodes $p$ ...
user avatar
3 votes
1 answer
3k views

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

How does best-first search differ from hill-climbing?
user avatar
1 vote
1 answer
497 views

Which heuristics guarantee the optimality of A*?

The following is a statement and I am trying to figure out if it's true or false and why. Given a non-admissible heuristic function, A* will always give a solution if one exists, but there is no ...
user avatar
  • 25
1 vote
1 answer
85 views

Doesn't the number of explored nodes with IDA* increase linearly?

I think I'm misunderstanding the description of IDA* and want to clarify. IDA* works as follows (quoting from Wiki): At each iteration, perform a depth-first search, cutting off a branch when its ...
user avatar
1 vote
0 answers
175 views

Can we solve an $8 \times 8$ sliding puzzle using hill climbing?

Can we solve an $8 \times 8$ sliding puzzle using a random-restart hill climbing technique (steepest-ascent)? If yes, how much computing power will this need? And what is the maximum $n \times n$ that ...
user avatar
  • 11
1 vote
0 answers
125 views

What is a example showing that the tree-based variant for the greedy best-first search is incomplete?

I understand that a tree-based variant will have nodes repeatedly added to the frontier. How do I craft an example where a particular goal node is never found. Is this example valid. On the other ...
user avatar
2 votes
0 answers
761 views

Wooden railway search problem AI

I have this problem. A basic wooden railway set contains the pieces shown in Figure 3.32. The task is to connect these pieces into a railway that has no overlapping tracks and no loose ends where a ...
user avatar
  • 21
2 votes
1 answer
4k views

What is the difference between hill-climbing and greedy best-first search algorithms?

While watching MIT's lectures about search, 4. Search: Depth-First, Hill Climbing, Beam, the professor explains the hill-climbing search in a way that is similar to the best-first search. At around ...
user avatar
  • 1,221
1 vote
0 answers
53 views

2 Partition Problem

I want to solve the two partition problem (https://en.wikipedia.org/wiki/Partition_problem) using an uninformed search algorithm (BFS or uniform cost). The states can be represented by three sets S1,...
user avatar
  • 131
2 votes
0 answers
84 views

How can I apply the alpha-beta pruning algorithm to the "1-2 steal marbles" problem?

I have the following problem called "1-2 steal marbles". Initially, there are 6 marbles on the board. One of the players can choose to remove 1 or 2 marbles leaving 5 or 4. After that, the other ...
user avatar
3 votes
0 answers
160 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 ...
user avatar
  • 161
1 vote
1 answer
234 views

What does a consistent heuristic become if an edge is removed in A*?

For the A* algorithm, a consistent heuristic is defined as follows: if, for every node $n$ and every successor $m$ of $n$ generated by any action $a$, $h(n) \leq c(n,m) + h(m)$. Suppose the edge $c(...
user avatar
  • 1,221
2 votes
1 answer
75 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 ...
user avatar
  • 161
4 votes
1 answer
426 views

What does the statement with the max do in the recursive best-first search algorithm?

I am reading the book "Artificial Intelligence: A Modern Approach" by Stuart and Norvig. I'm having trouble understanding a step of the recursive best-first search (RBFS) algorithm. Here's the ...
user avatar
  • 166
3 votes
1 answer
669 views

Is the summation of consistent heuristic functions also consistent?

Imagine that we have a set of heuristic functions $\{h_i\}_{i=1}^N$, where each $h_i$ is both admissible and consistent (monotonic). Is $\sum_{i=1}^N h_i$ still consistent or not? Is there any proof ...
user avatar
3 votes
2 answers
3k views

Why is the space-complexity of greedy best-first search is $\mathcal{O}(b^m)$?

I am reading through Artificial Intelligence: Modern Approach and it states that the space complexity of the GBFS (tree version) is $\mathcal{O}(b^m)$. While I am reading, at some points, I found ...
user avatar