Questions tagged [search]
For questions involving search algorithms and their use in artificial intelligence
2
votes
1answer
21 views
Proof Branch and Bound 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, but I haven't been able to find a proof on ...
1
vote
1answer
27 views
Using graph searching to solve peg solitaire?
Problem:
I've been reading research papers on how to solve a peg solitaire using graph searching, but all the papers kind of assume you know how to do the reduction(polynomial time conversion) from ...
1
vote
1answer
20 views
what are the similarity measure use for both continuous and categorical data?
I have searched but found that some similarity measures are for continuous data and some are for categorical data. But i want to know the similarity measures which are use for both data, continuous ...
1
vote
1answer
79 views
How do I choose the search algorithm for a particular task?
How do I choose the search algorithm for a particular task? Which criteria should I take into account?
0
votes
2answers
48 views
How can the A* algorithm be optimized?
How can the A* algorithm be optimized?
Any references that shows the optimization of A* algorithm are also appreciated.
1
vote
1answer
38 views
Why is informed search more efficient than uniformed search?
Why does informed search more efficiently finds a solution than uniformed search?
If there was an example, it would be easy to understand.
8
votes
2answers
101 views
What is the difference between search and learning?
I came across an article, The Bitter Truth, via the Two Minute Papers YouTube Channel. Rich Sutton says...
One thing that should be learned from the bitter lesson is the great
power of general ...
1
vote
0answers
32 views
Is the minimum and maximum of a set of admissible and consistent heuristics also consistent and admissible?
Let's suppose I have a set of heuristics $S$ = {$h_1, h_2, ..., h_n$}.
If all heuristics in $S$ are admissible, does that mean that a heuristic that takes the $MIN(S)$ (or $MAX$ for that matter) is ...
0
votes
1answer
44 views
How could we solve the TSP using an hill-climbing approach?
How could we solve the TSP using an hill-climbing approach?
1
vote
1answer
26 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
16 views
In which situation hill climbing searching will be more appropriate?
There are various heuristic search algorithms, like hill climbing, greedy search, A* algorithm, but when it is best preferred to use hill climbing?
0
votes
1answer
38 views
How do I model the blocked N queens problem as a search problem?
The blocked N-queens is a variant of the N-queens problem. In the blocked N-queens problem, we also have a NxN chess board and N queens. Each square can hold at most one queen. Some squares on the ...
1
vote
2answers
142 views
Difference between Graph Search and Tree Search
First of all, there is a lot of misunderstanding about the Graph search and Tree search. The difference between these two is not about Graph and Tree. They have two different algorithms. You can find ...
3
votes
2answers
116 views
What is the difference between search and planning?
I'm studying Artificial Intelligence. A Modern Approach, Stuart Russell, Peter Norvig, specifically about search and planning arguments.
I don't understand the difference between the two terms. I was ...
2
votes
0answers
79 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 ...
4
votes
3answers
355 views
Can someone help me to understand the alpha-beta pruning algorithm?
I understand the minimax algorithm, but I am unable to understand deeply the minimax algorithm with alpha-beta pruning, even after having looked up several sources (on the web) and having tried to ...
2
votes
2answers
112 views
When should I use simulated annealing as opposed to a genetic algorithm?
What kind of problems is simulated annealing better suited for compared to genetic algorithms?
From my experience, genetic algorithms seem to perform better than simulated annealing for most problems....
1
vote
0answers
20 views
which search methods belongs to A*
A* algorithm is based on which search methods?Explain me with example and is it optimal or complete if yes then how explain briefly?
2
votes
2answers
282 views
What are examples of daily life applications that use simulated annealing?
In AIMA, 3rd Edition on Page 125, Simulated Annealing is described as:
Hill-climbing algorithm that never makes “downhill” moves toward states with lower value (or higher cost) is guaranteed to be ...
3
votes
1answer
42 views
how we find the length(depth) of game tik tok toe in Adversarial search?
when we perform tik tok toe game using adversarial search i know how make tree
My Question is :
is there any way to find the depth of tree which level is the last level.
2
votes
1answer
78 views
Why does hill climbing algorithm only produce a local maximum?
Apparently, the hill climbing algorithm just produces a local maximum, and not necessarily a global optimum. It's stuck on a local maximum. Why does hill climbing algorithm only produce a local ...
0
votes
1answer
322 views
Why we use LIFO(Last in First Out) queue in depth first search?
As, we use FIFO(First In First Out) queue in breadth search algorithm but in depth first search we use LIFO.Why we use LIFO instead of FIFO in depth first search?
2
votes
1answer
902 views
How do I show that uniform-cost search is a special case of A*?
How do I show that uniform-cost search is a special case of A*? How do I prove this?
0
votes
1answer
54 views
Is the parent cost in A* added in every extended child?
How do we determine the cost of the parent path to its child in A* ("A star") search?
3
votes
1answer
70 views
What is the basic purpose of local search methods?
I read about the hill climbing algorithms, the simulating annealing algorithm, but I am confused. What is the basic purpose of local search methods?
0
votes
1answer
140 views
Breadth first search VS recursive best first search?
What is the difference between breadth first search and recursive best first search ? How can I describe the key difference between them?
3
votes
2answers
836 views
What is an objective function?
Local search algorithms are useful for solving pure optimization problems, in which the aim is to find the best state according to an objective
function. My question is what is the objective function ?...
9
votes
2answers
4k views
What are the limitations of the hill climbing algorithm and how to overcome them?
What are the limitations of the hill climbing algorithm? How can we overcome these limitations?
1
vote
1answer
796 views
How is simulated annealing better than hill climbing methods?
In hill climbing methods, at each step, the current solution is replaced with the best neighbour (that is, the neighbour with highest/smallest value). In simulated annealing, "downhills" moves are ...
3
votes
1answer
3k views
What are the practical differences between A* and greedy best-first search?
What are the differences between the A* algorithm and the greedy best-first search algorithm? Which one should I use? Which algorithm is the better one, and why?
3
votes
1answer
691 views
How is iterative deepening A* better than A*?
The iterative deepening A* search is an algorithm that can find the shortest path between a designated start node and any member of a set of goals.
The A* algorithm evaluates nodes by combining the ...
2
votes
2answers
105 views
Which Algorithm is best for Robots?
I am a student and I study Algorithms like
tree search algorithm
graph search algorithm
Then apply
BFS
DFS
UCS
IDS
DLS
Where are all these algorithms are used?
I know there is a long list of ...
4
votes
2answers
2k views
How does the uniform-cost search algorithm work?
What is the uniform-cost search algorithm? How does it work? I would appreciate to see a graphical execution of the algorithm. How does the "frontier" evolve in the case of UCS?
2
votes
2answers
1k 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
2answers
3k views
Greedy best first Search Algorithm vs A* search Algorithm
Greedy best first search Algorithm take the history and then check value ans then reach to goal.
In A* search Algorithm take history and also cost then calculate value then reach to goal.
When we ...
0
votes
2answers
64 views
Any problems/games/puzzles in which exhaustive search cannot show that a solution does not exist?
Introduction
Exhaustive search is a method in AI planning to find a solution for so called Constraint Satisfaction Problems. (CSP). That are problems which have some conditions to fulfill and the ...
3
votes
1answer
78 views
Transposition table is only used for roughly 17% of the nodes - is this expected?
I'm making a Connect Four game using the typical minimax + alpha-beta pruning algorithms. I just implemented a Transposition Table, but my tests tell me the TT only helps 17% of the time. By this I ...
1
vote
2answers
628 views
What heuristic to use when doing A* search with multiple targets?
The problem of multi-goal path planning was introduced in an ICRA paper in the year 2011:
“Multi-goal planning is a task which arises in many robotics
applications. It combines the challenging ...
2
votes
1answer
64 views
In the implementation of AI programming, does DFS always stop when it has found the leftmost solution?
I'm a fresh learner of AI. I was told that depth-first search is not an optimal searching algorithm since "it finds the 'leftmost' solution, regardless of depth or cost". Therefore, does it mean that ...
5
votes
2answers
256 views
More effective way to improve the heuristics of an AI… evolution or testing between thousands of pre-determined sets of heuristics?
I'm making a Connect Four game where my engine uses Minimax with Alpha-Beta pruning to search. Since Alpha-Beta pruning is much more effective when it looks at the best moves first (since then it can ...
0
votes
1answer
52 views
Which is more important, doubt or reinforcement?
Reinforcement?
We hear much about reinforcement, which is, in my opinion a poor choice of a term to describe a type of artificial network that continues to acquire or improve its behavioral ...
4
votes
1answer
395 views
Exploration Strategies for Reinforcement Learning w/ Continuous Action Space
I'm building a deep neural network to serve as the policy estimator in an Actor-Critic reinforcement learning algorithm for a continuing (not episodic) case. I'm trying to determine how to explore ...
0
votes
1answer
670 views
How do you calculate the heuristic value in this specific case?
The A* algorithm uses the "evaluation function" $f(n) = g(n) + h(n)$, where
$g(n)$ = cost of the path from the start node to node $n$
$h(n)$ = estimated cost of the cheapest path from $n$ to the ...
1
vote
1answer
74 views
AI to recognize keyword in a phrase within a context
I am building a search engine and I am looking for an open source AI algorithm to recognize the keyword in a search phrase within a particular context. So if a user passes something in the line of <...
6
votes
3answers
782 views
Why does Monte Carlo work when a real opponent's behavior may not be random
I am learning about Monte Carlo algorithms and struggling to understand the following:
If simulations are based on random moves, how can the modeling of the opponent's behavior work well?
For ...
3
votes
1answer
106 views
Minimax with only max
If both the players want to increase their score (by selecting the highest/best cost path) can this be done using Minimax Algorithm and not other algorithms?
4
votes
3answers
4k 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 ...
4
votes
1answer
102 views
Why is breadth search only optimal when the cost solution is a non-decreasing function?
I am learning about searching strategies in AI and I was reading that Breadth first search is only optimal when the cost solution is a non-decreasing function? I am not really sure what this refer to, ...
3
votes
1answer
209 views
How many iterations are required for iterative-lengthening search when step costs are drawing from a continuos range [ϵ, 1]?
This is AI: A Modern Approach, 3.17c. The solution manual gives the answer as $\frac{d}{\epsilon}$, where $d$ is the depth of the shallowest goal node.
Iterative lengthening search uses a path cost ...
2
votes
1answer
128 views
Adversarial search in the game '2048'
If we model the game '2048' using a max-min game tree, what is the maximal path from a start state to a terminal state? (Assume the game ends only when the board is full
This is one of the sub-...
