Questions tagged [search]

For questions involving search algorithms and their use in artificial intelligence

Filter by
Sorted by
Tagged with
2
votes
1answer
163 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
2answers
974 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
1answer
7k 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
533 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 $...
3
votes
1answer
375 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
0answers
135 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
452 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 ...
1
vote
1answer
128 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 ...
12
votes
3answers
717 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
667 views

Why is informed search more efficient than uninformed search?

Why does informed search more efficiently finds a solution than an uninformed search?
2
votes
1answer
98 views

What kind of search method is A*?

What kind of search method is A*? Explain to me with an example.
3
votes
1answer
429 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
2answers
136 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 ...
1
vote
0answers
113 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?
2
votes
1answer
42 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 ...
6
votes
1answer
5k 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
106 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
446 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.
10
votes
8answers
4k 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?
6
votes
1answer
8k 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 ...
5
votes
2answers
1k 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....
4
votes
1answer
3k 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
118 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
1k 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 ...
1
vote
1answer
81 views

Should the mutation be applied with the hill climbing algorithm?

As far as I understand, the hill climbing algorithm is a local search algorithm that selects any random solution as an initial solution to start the search. Then, should we apply an operation (i.e., ...
4
votes
2answers
2k views

How can I formulate the map colouring problem as a hill climbing search problem?

I have a map. I need to colour it with $k$ colours, such that two adjacent regions do not share a colour. How can I formulate the map colouring problem as a hill climbing search problem?
3
votes
1answer
4k 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 ...
6
votes
2answers
601 views

Why is the larger value, as opposed to the smaller one, chosen, in the hill climbing algorithm?

In the hill climbing algorithm, the greater value, compared to the current value, is selected, but I cannot understand why it takes the larger value instead of the smaller one. Why is that? I greatly ...
1
vote
1answer
549 views

What should I do when the new generated state has bigger distance to the goal than the parent state?

I have implemented the hill climbing algorithm, with side away steps, which can increase the rate of success, because, when you don't have new generated states, you can go back to previous level and ...
8
votes
2answers
2k 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 ...
9
votes
2answers
15k 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?
2
votes
0answers
321 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 ...
2
votes
2answers
4k 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?
11
votes
5answers
932 views

Are methods of exhaustive search considered to be AI?

Some programs do exhaustive searches for a solution while others do heuristic searches for a similar answer. For example, in chess, the search for the best next move tends to be more exhaustive in ...
5
votes
1answer
640 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 ...
7
votes
3answers
1k 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 ...
6
votes
2answers
2k views

Are leaf nodes included in the calculation of average branching factor for search trees?

In the search tree below, there are 11 nodes, 5 of which are leaves. There are 10 branches. Is the average branching factor given by 10/6, or 10/11? Are leaves included in the calculation? ...
2
votes
1answer
250 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-...
1
vote
1answer
74 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 ...
2
votes
1answer
126 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 <...
5
votes
1answer
212 views

Illustration of Von Neumann's Minimax theorem in games?

The Von Neumann's Minimax theorem gives the conditions that make the max-min inequality an equality. I understand the max-min inequality, basically ...
3
votes
1answer
313 views

How does a google choose it's autocomplete solution

While writing a paper yesterday this strange thing happened to me. I was wrtiting it in Word, and wasn't satisfied with the repeated usage of word "relesase" in last few senteces. So I've decided to ...

1 2
3