Questions tagged [search]

For questions involving search algorithms and their use in artificial intelligence

14 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
1answer
96 views

A* is similar to Dijkstra with reduced cost

According to this Wikipedia article If the heuristic $h$ satisfies the additional condition $h(x) ≤ d(x, y) + h(y)$ for every edge $(x, y)$ of the graph (where $d$ denotes the length of that edge), ...
4
votes
2answers
40 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 ...
3
votes
0answers
27 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 ...
3
votes
0answers
57 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 ...
2
votes
0answers
48 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 ...
2
votes
0answers
59 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 ...
2
votes
1answer
22 views

Agents meeting in a directed connected graph

I've just started learning AI and I have a certain problem: We have directed connected graph, where nodes are places one can go to and edges are the "roads" between places. We have K agents whose ...
2
votes
0answers
196 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 ...
1
vote
0answers
17 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
0answers
31 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,...
1
vote
1answer
43 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 ...
1
vote
0answers
77 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?
1
vote
1answer
148 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 ...
0
votes
0answers
28 views

Constraint Satisfaction for light switches problem

While revising on the topic of constraint satisfaction, I came across a question on light switches which asks us to formulate the problem as a CSP. This problem was taken from stanford's cs221 ...