Questions tagged [search]
For questions involving search algorithms and their use in artificial intelligence
140
questions
0
votes
0answers
15 views
Why is that the heuristic is not admissible, then it is not consistent [duplicate]
I don't understand why if the heuristic is not admissible then it is not consistent?
2
votes
1answer
45 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?
1
vote
0answers
28 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 AI: 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 to expand based on ...
0
votes
1answer
56 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
47 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
1answer
35 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
2answers
68 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*?
0
votes
0answers
27 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 ...
0
votes
0answers
23 views
Can an inadmissable heuristic be consistent? [duplicate]
If something is inadmissible, can we just assume it's also inconsistent?
Also, I understand how to check if a heuristic is inadmissible, but I'm still a bit confused on checking consistency.
If I have ...
0
votes
0answers
22 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 ...
0
votes
0answers
26 views
How to interpret the output of alpha-beta pruning in terms of which position to play next in a game
I'm trying to understand question 4 of this paper.
This is a tree pruned with alpha-beta pruning:
I understand technically how this pruning worked (i.e. calculating mix/max/alpha/beta values). My ...
1
vote
1answer
291 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 ...
2
votes
0answers
44 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 ...
2
votes
1answer
91 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 ...
2
votes
1answer
404 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 ...
2
votes
1answer
139 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 ...
2
votes
2answers
744 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?
1
vote
1answer
187 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 ...
1
vote
1answer
719 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)?
0
votes
0answers
21 views
Optimal path finding in multiagent game with collision avoidance
What algorithm to use when to find the optimal path from a starting point to the end point in a multiagent game with collision avoidance? I am in control of the agent while having zero ideas of where ...
1
vote
1answer
246 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)?
0
votes
1answer
121 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 ...
0
votes
0answers
25 views
How does the second phase of the evaluation function described in this article work?
I am trying to create an evaluation function for a general game player based on the research from this article An Automatically-Generated Evaluation Function in General Game Playing. I can't ...
1
vote
0answers
22 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 ...
9
votes
2answers
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 ...
0
votes
0answers
36 views
Suggestion for an Enterprise search engine: What are all the way I can use machine learning/dnn/nlp to enhance elasticsearch results?
We are building an enterprise search engine for about 130,000 documents. It includes FAQs, Small articles to 3-4 page documents, all of them are stored in structured JSON.
We were originally planning ...
2
votes
1answer
269 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$ ...
0
votes
1answer
1k views
How does best-first search differ from hill-climbing?
How does best-first search differ from hill-climbing?
1
vote
1answer
117 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 ...
1
vote
1answer
58 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 ...
0
votes
0answers
37 views
How to implement NLP for ecommerce product search
I'm implementing an ecommerce search using nlp. there is a lack of clear documentation anywhere online about implementation and flow. this is what i'm doing.
Search query comes in
Do spellcheck
Do ...
1
vote
0answers
95 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 ...
1
vote
0answers
34 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 ...
2
votes
0answers
442 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 ...
2
votes
1answer
2k 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 ...
1
vote
0answers
43 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,...
2
votes
0answers
76 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 ...
3
votes
0answers
98 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 nonogram solving problem and I want to solve it using backtracking with CSP.
The first problem that I face is that I cannot ...
1
vote
1answer
121 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(...
2
votes
1answer
41 views
Agents meeting in a directed connected graph
I've just started learning AI and I have a certain problem:
We have directed connected graph, where nodes are places one can go to and edges are the "roads" between places. We have K agents whose ...
3
votes
1answer
185 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 ...
3
votes
1answer
324 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 ...
2
votes
2answers
1k 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 ...
1
vote
1answer
136 views
How to report the solution path of a search algorithm on a graph?
I'm working on a problem where we are given a graph and asked to perform various search algorithms (BFS, DFS, UCS, A*, etc.) and the goal state is to visit all nodes in the graph. After all nodes are ...
2
votes
1answer
532 views
Understanding the pseudocode of uniform-cost search from the book “Artificial Intelligence: A Modern Approach”
On page 84 of Russell & Norvig's book "Artificial Intelligence: A Modern Approach Book" (3rd edition), the pseudocode for uniform cost search is given. I provided a screenshot of it here for your ...
1
vote
1answer
132 views
FastDownward PDDL Planner Limitations [closed]
I recently had a look at automated planners and experimented a little bit with FastDownward. As I wanted to start a toy project, I created a PDDL model for the ordinary 3D Rubik's Cube (of course ...
4
votes
1answer
328 views
Why is it possible to eliminate this branch with alpha-beta pruning?
Can someone explain to me why it is possible to eliminate the rest of the middle branch in this image for alpha-beta pruning? I am confused because it seems the only information you know is that Helen ...
3
votes
1answer
1k 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?
6
votes
1answer
180 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 ...
1
vote
1answer
599 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 ...
