We have a lift with capacity of N (e.g 6) individuals in a building of M(e.g 5) floors.The lift does not necessarily stop at a floor where passenges are waiting.
When it stops at a floor they can get in as many passengers as the sum of them with the existing in the elevator does not exceedits capacity.The lift is originally located at floor I(e.g I=2) and
it has Y(e.g 2) passengers.In every floor k they are waiting Xk (k=1,M) passengers (e.g 2 at first floor,7 at second floor,3 at third floor ,5 at fourth floor and 8 at fifth floor) to get down to the ground floor,as the original passengers of the lift.
The requested is to be found a total set of moves of the lift so that all the passengers get down to the ground floor(the ones in the lift and the ones waiting at the floors).Consider that there will not be other passengers until all the people waiting get down to the ground floor
(close world view)

For the above problem the followings have to be done
1.Description of the problem
2.State Presentation( initial(s) and final(s) state(s))
3.Description of transition Operators.
4.Algorithm 1:
4.1 Description of heuristic function and cost function.
4.2 Description of the algorithm in natural language.
4.3 Description of the algorithm in pseudocode.
4.4 Description of the algorithm in PROLOG
5. The same as 4 for another algorithm(algorithm 2)

The 2 algorithm must be chosen from this list:
-Hill Climbing 1(HC1)
-Hill Climbing 2(HC2)
-Beam Search (BS)
-Branch & Bound (B&B)
-Best First(BF)
-A*.

Why does this look exactly like a school assignment of some kind...

Just Google for a bit and if you really can't solve it ask for hints, not for straight answers, you won't learn a thing from them.

Standing rules around here is that we don't help people with their homework. If you don't know how to do the assignment, then either you aren't paying attention or your teacher really sucks. Study more. Figure it out.

That said, if you have a specific question about a specific technique, you will usually get answers on this board.

ok thanx for the replies, i had no idea how this forum works.I will proceed with the project and if i have some difficulty in a specific part i will ask for something particular..

About the above problem , i have the representation of the state of the problem as follows: (i,x1,x2,x3,x4,x5,y,S) where i is the number of the floor where the lift is , y is the number of the people inside the lift , xi is the people waiting on each floor(1-5) and S is the sum of all the people waiting to get down outside and inside the lift.As a cost function i have made up with this one: g(n,n')=|i-i'| where i is the floor where the lift is and i' is the floor which the lift is heading to.I have some trouble with the heuristic function.So far i have this one: h(n)=(x1+x2+x3+x4+x5)-|xi-xi'| where xi is the people waiting on the current floor and xi' the people waiting at the same floor after some of them get inside the lift.I made this function so that the lift chooses to go to the floor where the most passengers are waiting.
Any better ideas for an heuristic function???
Also i have chosen A* to solve this problem.Could you suggest one more algorithm who is suitable for this broblem(best first,b&b etc).....??
Thanx in advance!!

I have some trouble with the heuristic function.So far i have this one: h(n)=(x1+x2+x3+x4+x5)-|xi-xi'| where xi is the people waiting on the current floor and xi' the people waiting at the same floor after some of them get inside the lift.I made this function so that the lift chooses to go to the floor where the most passengers are waiting.

The problem asks for "a total set of moves of the lift so that all the passengers get down to the ground floor". Presumably, you want to optimize the total time required to bring everyone down, which is the sum of the durations of each elevator move: the duration of a move is the time spent moving (proportional to the number of floors of difference) plus the time spent at a certain floor (a term that is the same for any stop, representing acceleration, braking and minimum duration of the stop; plus terms that are proportional to the number of people that go in or the number of people that go out): the number of people that wait is immaterial.

I strongly recommend leaving the mentioned quantities as arbitrary parameters, solving the most general problem instead of an arbitrary variant.

A* is certainly a good choice, which allows you to find an optimal solution (always nice) and exploit interesting search space constraints: for example, can the optimal solution include people exiting the elevator at floors other than the ground floor? Or the elevator moving upwards with people inside?

For learning purposes, the most interesting alternative algorithm should be something quite different, like random hill climbing.

[quote name='retanas' timestamp='1314872745' post='4856221']
I have some trouble with the heuristic function.So far i have this one: h(n)=(x1+x2+x3+x4+x5)-|xi-xi'| where xi is the people waiting on the current floor and xi' the people waiting at the same floor after some of them get inside the lift.I made this function so that the lift chooses to go to the floor where the most passengers are waiting.

The problem asks for "a total set of moves of the lift so that all the passengers get down to the ground floor". Presumably, you want to optimize the total time required to bring everyone down, which is the sum of the durations of each elevator move: the duration of a move is the time spent moving (proportional to the number of floors of difference) plus the time spent at a certain floor (a term that is the same for any stop, representing acceleration, braking and minimum duration of the stop; plus terms that are proportional to the number of people that go in or the number of people that go out): the number of people that wait is immaterial.

I strongly recommend leaving the mentioned quantities as arbitrary parameters, solving the most general problem instead of an arbitrary variant.

A* is certainly a good choice, which allows you to find an optimal solution (always nice) and exploit interesting search space constraints: for example, can the optimal solution include people exiting the elevator at floors other than the ground floor? Or the elevator moving upwards with people inside?

For learning purposes, the most interesting alternative algorithm should be something quite different, like random hill climbing.
[/quote]

Thanx A lot! I finished with 3 algorithms , Best First , Branch & Bound and of course A*..I have one last problem .I have to represent the solutions that these algorithms provide with a Tree.So far i have the solution in a list form(e.c [State1],[State2],...[GoalState]). Does anybody know a way to represent these with a tree form? I have checked the prolog functions "inorder" and "tree" and i think that they are good enough for this purpose...