2
$\begingroup$

I'm a CS student and I'm trying to understand the searching algorithms used in AI.

My problem is that I don't really understand how to treat a problem like a search problem. I don't know which would be the first steps for solving it and how shall I choose the right algorithm for that.

For example, I have a problem like that:

n vehicles occupy squares (1, 1) through (n, 1) (i.e., the bottom row) of an n×n n grid. The vehicles must be moved to the top row but in reverse order; so the vehicle i that starts in (i, 1) must end up in (n−i+ 1, n). On each time step, every one of the n vehicles can move one square up, down, left, or right, or stay put; but if a vehicle stays put, one other adjacent vehicle (but not more than one) can hop over it. Two vehicles cannot occupy the same square.

I understood that the start state of each car is the bottom row, each car has at most five possible moves from any position and if each car has a 3x3 grid of empty space around it, then all five moves are possible.

My idea is that I should treat the car route like a tree where each node is a position of the car at a time, but I don't know how correct is it.

Which would be my first steps regarding this problem to solve it like a search problem?

I would be very thankful for any advice!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

To treat it as a search problem, you should have a decision tree in mind. In your example, the each node's degree would be the total combination of possible movements for each car (except for the combination in which all cars stay put). Then, each edge of the decision tree would represent a transition from one timestep to the next and each node would represent the positions of all the vehicles at that timestep. One can use the current depth of the tree during the search process to track the current timestep. Using this setup, there are many possible tree search algorithms that may suffice for your problem.

Improve this answer
$\endgroup$
1
  • $\begingroup$ So I was thinking good. It really makes sense! Thank you very much for your help :) ! $\endgroup$
    – John
    Commented May 17, 2020 at 20:03
0
$\begingroup$

So the way I usually simulate these kind of trees on paper is that I make a node for every move. So from starting(parent) node I make one node(child) for Up, one node for Down and you know the rest.

Once it moves to that new space reevaluate again and make more nodes using that new space in the grid. Hope this helps!

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.