Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Questions tagged [search]

For questions involving search algorithms and their use in artificial intelligence

Filter by
Sorted by
Tagged with
1
vote
1answer
65 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 ...
9
votes
3answers
7k 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 ...
0
votes
1answer
252 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 ...
2
votes
1answer
81 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) ...
6
votes
1answer
53 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 ...
4
votes
1answer
227 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 ...
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$?
3
votes
2answers
478 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 ...
2
votes
2answers
8k views

What are the differences between greedy best-first and the A* search algorithms? [duplicate]

What are the differences between greedy best-first and the A* search algorithms? How is A* better than the greedy best-first search algorithm?
2
votes
1answer
629 views

What are the differences between uniform-cost search and greedy best-first search?

What are the differences between the uniform-cost search (UCS) and greedy best-first search (GBFS) algorithms? How would you convert a UCS into a GBFS?
2
votes
1answer
42 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 ...
1
vote
1answer
578 views

What is the difference between the breadth-first search and recursive best-first search?

What is the difference between the breadth-first search and recursive best-first search? How can I describe the key difference between them?
5
votes
2answers
179 views

How does A* search work given there are multiple goal states?

When I have read through the fundamentals of AI, I saw a situation (i.e., a search space) which is illustrated in the following picture. These are the heuristic estimates: ...
4
votes
2answers
4k views

How does the uniform-cost search algorithm work?

What is the uniform-cost search (UCS) algorithm? How does it work? I would appreciate seeing a graphical execution of the algorithm. How does the frontier evolve in the case of UCS?
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
66 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 $...
4
votes
1answer
74 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. ...
7
votes
1answer
6k views

Why is A* optimal if the heuristic function is admissible?

A heuristic is admissible if it never overestimates the true cost to reach the goal node from $n$. If a heuristic is consistent, then the heuristic value of $n$ is never greater than the cost of its ...
4
votes
2answers
105 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
1answer
136 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
77 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 ...
3
votes
0answers
27 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 ...
3
votes
1answer
26 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 ...
2
votes
3answers
1k 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 ...
3
votes
1answer
277 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 ...
4
votes
1answer
7k views

What are the 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?
1
vote
1answer
31 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 ...
0
votes
1answer
52 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 ...
5
votes
1answer
5k views

What is the fringe in the context of search algorithms?

What is the fringe in the context of search algorithms?
9
votes
3answers
455 views

Why teaching only search algorithms in a short introductory AI course?

I understood that the concept of search is important in AI. There's a question on this website regarding this topic, but one could also intuitively understand why. I've had an introductory course on ...
2
votes
1answer
89 views

Why is informed search more efficient than uninformed search?

Why does informed search more efficiently finds a solution than an uninformed search?
1
vote
1answer
46 views

What kind of search method is A*?

What kind of search method is A*? Explain to me with an example.
3
votes
1answer
104 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 ...
4
votes
1answer
60 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?
2
votes
2answers
63 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
51 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?
8
votes
2answers
132 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
21 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 ...
8
votes
2answers
106 views

Memory intensive local search methods

I have been studying local search algorithms such as greedy hill climbing, stochastic hill climbing, simulated annealing etc. I have noticed that most of these methods take up very little memory as ...
4
votes
1answer
1k views

What is the difference between local search and global search algorithms?

What is the difference between local search and global (or complete) search algorithms?
1
vote
1answer
85 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
58 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.
8
votes
8answers
2k views

Why is search important in AI?

Why is search important in AI? What kinds of search algorithms are used in AI? How do they improve the result of an AI?
4
votes
1answer
2k 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 ...
0
votes
1answer
63 views

How could we solve the TSP using an hill-climbing approach?

How could we solve the TSP using an hill-climbing approach?
2
votes
2answers
215 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....
3
votes
1answer
33 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 ...
4
votes
1answer
1k views

How do I solve the knapsack problem using the hill climbing algorithm?

I need to solve the knapsack problem using hill climbing algorithm (I need to write a program). But I'm clueless about how to do it. My code should contain a method called ...
4
votes
1answer
89 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?
2
votes
2answers
530 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 ...