Questions tagged [search]

For questions involving search algorithms and their use in artificial intelligence

142 questions
Filter by
Sorted by
Tagged with
182 views

A* is similar to Dijkstra with reduced cost

According to this Wikipedia article If the heuristic $h$ satisfies the additional condition $h(x) \leq d(x, y) + h(y)$ for every edge $(x, y)$ of the graph (where $d$ denotes the length of that edge),...
3k views

What are the state space and the state transition function in AI?

I'm studying for my AI final exam, and I'm stuck in the state space representation. I understand initial and goal states, but what I don't understand is the state space and state transition function. ...
40 views

Which "assumptions" made about the state space are Russell and Norvig referring to in their book?

I am reading the cornerstone book, "Artificial Intelligence, A Modern Approach" by Stuart Russel, and Peter Norvig, and there is a passage in the book on page 98: The complexity results ...
420 views

Why does the 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 ...
790 views

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

How could we solve the TSP using a hill-climbing approach?
4k views

When to choose Stochastic Hill Climbing over Steepest Hill Climbing?

Stochastic Hill Climbing generally performs worse than Steepest Hill Climbing, but what are the cases in which the former performs better?
104 views

When does IDA* consider the goal has been found?

I was reading about IDA* and I found this link explaining IDA* and providing an animation for it. Here is a picture of the solution. I know what is the cutoff condition (it depends on F), and the ...
1k views

If uniform cost search is used for bidirectional search, is it guaranteed the solution is optimal?

If uniform cost search is used for both the forward and backward search in bidirectional search, is it guaranteed the solution is optimal?
5k views

What heuristic to use when doing A* search with multiple targets? [closed]

Usually, using the Manhattan distance as a heuristic function is enough when we do an A* search with one target. However, it seems like for multiple goals, this is not the most useful way. Which ...
60 views

Why do we use the tree-search version of breadth-first search or A*?

In Artiﬁcial 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 ...
661 views

What is the difference between the uniform-cost search and Dijkstra's algorithm?

Every computer science student (including myself, when I was doing my bachelor's in CS) probably encountered the famous single-source shortest path Dijkstra's algorithm (DA). If you also took an ...
2k 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 ...
238 views

Why is the completeness of UCS guaranteed only if the cost of every step exceeds some small positive constant?

I was reading Artificial Intelligence: A Modern Approach 3rd Edition, and I have reached to the UCS algorithm. I was reading the proof that UCS is complete. The book state that: Completeness is ...
426 views

What is the space complexity of iterative deepening search?

When using iterative deepening, is the space complexity, $O(d)$, where $b$ is the branching factor and $d$ the length of the optimal path (assuming that there is indeed one)?
343 views

What is the space complexity of bidirectional search?

Is the space complexity of the bidirectional search, where the breadth-first search is used for both the forward and backward search, $O(b^{d/2})$, where $b$ is the branching factor and $d$ the length ...
1k views

What is the space complexity of breadth-first search?

When using the breadth-first search algorithm, is the space complexity $O(b^d)$, where $b$ is the branching factor and $d$ the length of the optimal path (assuming that there is indeed one)?
551 views

Is A* with an admissible but inconsistent heuristic optimal?

I understand that, in tree search, an admissible heuristic implies that $A*$ is optimal. The intuitive way I think about this is as follows: Let $P$ and $Q$ be two costs from any respective nodes $p$ ...
1k views

Is the 'direction' considered, when determining the branching factor in bidirectional search?

If I am correct, the branching factor is the maximum number of successors of any node. When I am applying bidirectional search to a transition graph like this one below If 11 is the goal state and I ...
252 views

Which heuristics guarantee the optimality of A*?

The following is a statement and I am trying to figure out if it's true or false and why. Given a non-admissible heuristic function, A* will always give a solution if one exists, but there is no ...
192 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 ...
5k 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 ...
13k views

What is the fringe in the context of search algorithms?

What is the fringe in the context of search algorithms?
37k 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?
312 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 ...
25 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 ...
1k views

Why is depth-first search an artificial intelligence algorithm?

I'm new to the artificial intelligence field. In our first chapters, there is one topic called "problem-solving by searching". After searching for it on the internet, I found the depth-first ...
585 views

Can I prune the tree if alpha-beta pruning finds 10 to the left of the root node?

I have an AI class this semester. For our exam, we also cover alpha-beta pruning. I found an old example, where I think we can stop already earlier. Here is a picture of it. I think, because $X$ ...
66 views

Doesn't the number of explored nodes with IDA* increase linearly?

I think I'm misunderstanding the description of IDA* and want to clarify. IDA* works as follows (quoting from Wiki): At each iteration, perform a depth-first search, cutting off a branch when its ...
417 views

Is there any website that allows you to choose an algorithm, code it and visualise how it works?

I would like to do some practical implementation of a planning algorithm (of course, something a bit simple and easy). Is there any website where I can pick an algorithm (e.g. A* or hill climbing), ...
121 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 ...
278 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). Those are problems that have some conditions to fulfill and the ...
3k 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?
54 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 ...
854 views

Are iterative deepening, principal variation search or quiescence search extensions of alpha-beta pruning?

I know that there are several optimizations for alpha-beta pruning. For example, I have come across iterative deepening, principal variation search, or quiescence search. However, I am a little bit ...
701 views

Does quiescence search even improve the minimax algorithm?

Consider this game state: d5 captures c6 Quiescence search returns about 8.0 as evaluation because after dxc6 and bxc6 Qxd6 would be played (then Qxd6 by black). A normal player would not play this ...
668 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 ...
3k views

What is the difference between hill-climbing and greedy best-first search algorithms?

While watching MIT's lectures about search, 4. Search: Depth-First, Hill Climbing, Beam, the professor explains the hill-climbing search in a way that is similar to the best-first search. At around ...
81 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 ...
44 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,...
1k 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 ...