Questions tagged [search]
For questions involving search algorithms and their use in artificial intelligence
95
questions
2
votes
0answers
19 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
51 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(...
1
vote
1answer
18 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
41 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
56 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 ...
1
vote
1answer
648 views
What are the properties of hill climbing?
What are the properties of hill climbing? More precisely, does it encounter any of the following phenomena?
Local maxima
Inadmissible heuristic
Ridges
Plateau
2
votes
1answer
54 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
42 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
49 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 ...
0
votes
1answer
25 views
FastDownward PDDL Planner Limitations
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
47 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 ...
1
vote
1answer
69 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 ...
3
votes
1answer
90 views
A* and uniform-cost search are apparently incomplete
Consider the following diagram of a graph representing a search space.
If we start at $B$ and try to reach goal state $E$, the lowest-cost first search (LCFS) (aka uniform-cost search) algorithm ...
5
votes
1answer
306 views
How to create an AI to solve a word search?
This at first sounds ridiculous. Of course there is an easy way to write a program to solve a wordsearch.
But what I would like to do is write a program that solves a word-search like a human.
That ...
4
votes
2answers
447 views
If an heuristic is not admissible, can it be consistent?
I am solving a problem in which, according to the given values, the heuristic is not admissible. According to my calculation from other similar problems, it should be consistent, as well as keeping in ...
3
votes
0answers
45 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 ...
6
votes
1answer
64 views
Can two admissable heuristics not dominate each other?
I am working on a project for my artificial intelligence class. I was wondering if I have 2 admissible heuristics, A and B, is it possible that A does not dominate B and B does not dominate A? I am ...
2
votes
1answer
58 views
In the graph search version of A*, can I stop the search the first time I encounter the goal node?
I am going through Russel and Norvig's Artificial Intelligence: A Modern Approach (3rd edition). I was reading the part regarding the A* algorithm
A* graph search version is optimal when heuristic ...
5
votes
1answer
112 views
How do we determine whether a heuristic is better than another?
I am trying to solve a Maze puzzle using the A* algorithm. I am trying to analyze the algorithm based on different applicable heuristics.
Currently, I explored the Manhattan and Euclidean distances. ...
2
votes
1answer
87 views
Understanding the proof that A* search is optimal
I don't understand the proof that $A^*$ is optimal.
The proof is by contradiction:
Assume $A^*$ returns $p$ but there exists a $p'$ that is cheaper. When $p$ is chosen from the frontier, assume $...
1
vote
1answer
66 views
How to transform a PDDL to search?
I have a question about search and planning:
I still haven't understood the difference from the two, but they seem very similar to me; here is a question I am struggling with:
"Having formulated a ...
2
votes
2answers
81 views
Why is a mix of greedy and random usually “best” for stochastic local search?
I read that a mix of "greedy" and "random" are ideal for stochastic local search (SLS), but I'm not sure why. It mentioned that the greedy finds the local minima and the randomness avoids getting ...
0
votes
0answers
70 views
Can AC-3 algorithm solve N-Queens problem?
I am building CSP NQueens solver and apply the AC-3 algorithm.But,the domain reduction doesn't occur and gets more search time.How does it happen?Is it a nature of AC-3 algorithm?
3
votes
1answer
28 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 ...
3
votes
1answer
193 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 ...
2
votes
1answer
24 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
133 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 ...
1
vote
1answer
88 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
64 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.
2
votes
1answer
173 views
Why is informed search more efficient than uninformed search?
Why does informed search more efficiently finds a solution than an uninformed search?
9
votes
2answers
141 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 ...
2
votes
1answer
237 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 $H$ = {$h_1, h_2, ..., h_N$}.
If all heuristics in $H$ are admissible, does that mean that a heuristic that takes the $\min(H)$ (or $\max(H)$ for that matter) ...
0
votes
1answer
217 views
How could we solve the TSP using an hill-climbing approach?
How could we solve the TSP using an hill-climbing approach?
3
votes
1answer
185 views
How do I find whether this heuristic is or not admissible and consistent?
I was given the following problem to solve.
Given a circular trail divided by $n> 2$ segments labeled $0 \dots n-1$. In the beginning, an agent is at the start of segment number $0$ (the edge ...
3
votes
1answer
36 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
2answers
357 views
How can I solve part b of exercise 3.6 from the book “Artificial Intelligence: A Modern Approach”?
I am trying to solve part b of the exercise 3.6 (page 113) from the book Artificial Intelligence: A Modern Approach.
More specifically, I need to give a complete problem formulation (that is precise ...
0
votes
1answer
74 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 ...
3
votes
0answers
711 views
What is the difference between graph search and tree search? [duplicate]
First of all, there is a lot of misunderstanding about the graph search and tree search. The difference between these two is not about graphs and trees. They have two different algorithms. You can ...
5
votes
1answer
1k 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
172 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 ...
5
votes
3answers
1k 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 ...
3
votes
2answers
431 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....
2
votes
1answer
51 views
2
votes
2answers
709 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 ...
4
votes
1answer
68 views
How do we find the length (depth) of the game tic-tac-toe in adversarial search?
When we perform the tic-tac-toe game using adversarial search I know how make a tree. Is there a way to find the depth of the tree; which level is the last level?
3
votes
1answer
161 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
1k 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?
4
votes
1answer
2k 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?
2
votes
1answer
67 views
How is the cost of the path to each node computed in A*?
How is the cost of the path to each node $n$ computed in the A* algorithm? Do we need to add the cost of the path to the parent node $p$ to the cost of the path of the child node $n$?
4
votes
1answer
99 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?
