# Questions tagged [search]

For questions involving search algorithms and their use in artificial intelligence

24 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
121 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 ...
134 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 ...
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 ...
142 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 ...
56 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 ...
651 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 ...
80 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 ...
53 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 ...
319 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 ...
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 ...
1k 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?
33 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 AI: 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 to expand based on ...
163 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 ...
24 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 ...
116 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 ...
50 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 ...
43 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,...
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?
15 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 ...
11 views

### Are ranking models considered discriminative?

I'm developing a model that ranks entries based on cosine similarity to a query. Since it doesn't actually define a boundary between x and y I initially believed that such ranking models are not ...
31 views

### Fine tuning a BERT model for text classification

An article written by Jay Alammar (http://jalammar.github.io/a-visual-guide-to-using-bert-for-the-first-time/) on using a BERT transformer for text classification. The article mentions the following ...
30 views

### Incorrect node expansion in game board with A* search

I have the following game board below, and we're using A* search to find the optimal path from the agent to the key. There are 8 directions. Up, down, left, right have a cost of 1, and diagonal ...