Questions tagged [search]
For questions involving search algorithms and their use in artificial intelligence
32
questions with no upvoted or accepted answers
4
votes
1
answer
320
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?
- 41
4
votes
2
answers
306
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 ...
- 351
3
votes
0
answers
329
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 ...
- 161
3
votes
0
answers
343
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 ...
2
votes
0
answers
640
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 ...
- 21
2
votes
0
answers
917
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 ...
- 21
2
votes
0
answers
112
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 ...
2
votes
0
answers
409
views
How does DARTS compare to ENAS?
How does DARTS compare to ENAS? Which one is better or what advantages does they each have?
Links:
DARTS: Differentiable Architecture Search
Efficient Neural Architecture Search via Parameter ...
- 121
1
vote
1
answer
22
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 ...
- 111
1
vote
0
answers
25
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 ...
- 151
1
vote
0
answers
144
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 ...
- 284
1
vote
0
answers
499
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 ...
- 101
1
vote
0
answers
123
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
0
answers
161
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 ...
- 11
1
vote
0
answers
173
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 ...
- 21
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
58
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 ...
- 111
1
vote
0
answers
414
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 ...
- 11
1
vote
0
answers
485
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 ...
- 63
1
vote
0
answers
77
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,...
- 131
1
vote
1
answer
667
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 ...
- 11
1
vote
0
answers
3k
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?
- 566
1
vote
0
answers
227
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$ ...
- 121
0
votes
1
answer
10
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 ...
- 143
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 ...
- 151
0
votes
0
answers
105
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 ...
- 1
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 ...
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 ...
- 211
0
votes
2
answers
2k
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, ...
- 13
0
votes
0
answers
601
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 ...
- 133
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 ...
- 1
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 ...
- 21