# Questions tagged [search]

For questions involving search algorithms and their use in artificial intelligence

29 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
162 views

### What is the proof that the branch and bound algorithm 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 However, I haven't been able to find a ...
• 351
160 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 a nonogram solving problem and I want to solve it using backtracking with CSP. The first problem that I face is that I ...
• 161
198 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 ...
203 views

### Can minimax be used when both players want to increase their score?

If both the players want to increase their score (by selecting the highest or best cost path), can this be done using the minimax algorithm, or are there other algorithms for this purpose?
126 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 ...
• 21
761 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 ...
• 21
84 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 ...
75 views

### Agents meeting in a directed connected graph

We have a directed connected graph, where nodes are places one can go to and edges are the "roads" between places. We have K agents whose goal is to meet in one node. Agents start in ...
• 161
366 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 ...
• 121
2k views

### How to improve the efficiency of the backtracking search in CSPs?

Backtracking search is the basic uninformed search algorithm for constraint satisfaction problems (CSPs). How could we improve the efficiency of the backtracking search in CSPs?
• 536
1 vote
21 views

### Is N the total number of nodes in the frontier plus the number of nodes in the explored list?

I'm studying fundamentals of AI from the classic Russell-Norvig book (3rd edition). I have a small doubt about the effective branching factor, which is defined as follows (section 3.6.1, p. 103): One ...
• 111
1 vote
58 views

### Best algorithm for the Word Ladder puzzle

What would be the best performing algorithm to solve the Word Ladder problem, in terms of guaranteed finding of the shortest solution in the shortest possible time? Is it BFS, DFS, A*, IDA* or another ...
1 vote
60 views

### What would happen if we set the evaluation function in the best-first search algorithm as the cost of paths taken to new nodes?

I am reading Artificial Intelligence: A Modern Approach. In Chapter 3, Section 3.3.1, The best-first search algorithm is introduced. We learn that in each iteration, this algorithm chooses which node ...
• 21
1 vote
460 views

### Determining minimal state representation for maze game

I came across this question set. It asks following question: Let’s revisit our bug friends from assignment 2. To recap, you control one or more insects in a rectangular maze-like environment with ...
• 131
1 vote
230 views

### How does the MCTS tree look like?

I have come across the Monte Carlo tree search (MCTS) algorithm, but I can't find what the tree should look like. For example, does it still represent a minimax process, i.e. player 1 from the root ...
1 vote
32 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 ...
• 111
1 vote
175 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 ...
• 11
1 vote
124 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 ...
1 vote
53 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,...
• 131
1 vote
401 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 ...
• 11
1 vote
129 views

### How can we find the number of node expansions performed by BFS in this hexagonal map?

An agent aims to find a path on a hexagonal map, with an initial state $s_0$ in the center and goal state $s^*$ at the bottom as depicted below. The map is parametrized by the distance $n \geq 1$ ...
• 111
8 views

### Image suggestions using feature extractor + ANN index

I am trying to build an image suggestion engine using resnet151 as a feature extractor and right now I am testing Annoy and Faiss as the ANN. I am having some issues with images that have similar ...
317 views

### Why is depth-limited is preferable to minimax without depth limited

I have read about a question that says the following: Why is depth-limited minimax preferable to minimax? One of the wrong answers was: The depth-limited minimax will achieve the same output as ...
75 views

### Where can I find Norvig's version of the pseudocode for the A* search algorithm?

Can anybody point me to a link to Peter Norvig's version of the A* pseudocode. I've googled it interminably but found nothing. It's the version that uses the Unexplored/Frontier/Explored data ...
44 views

### Hierarchical Navigable Small World Graphs : Expected Number of Steps in a Layer

Paper: Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs In the Search Complexity section, the author estimates that the expected number of steps ...
34 views

### What is the relationship between classical searching algorithms in AI and machine learning?

I think the relationship between the local search algorithms in AI for continuous spaces and Machine Learning is somewhat clear, as most of these search algorithms use gradient-based methods for ...
• 101
19 views

### What is an efficient way to implement an contextual search for a search engine?

So I am working on a search engine and want to implement a contextual search for my search engine but would like to get some advice before I start working on it. I have a basic knowledge of A.I. like ...