| Eugene,
Thanks for your request for clarification. I'll try to explain it more
clearly.
We want to be able to determine if 'n' (0<n<10) people can all stay in
the same hotel. The hotel has rooms of different sizes (types). Each
room type has a minimum and maximum occupancy 0<min_occ<10 and
min_occ <= max_occ < 10. There are specified numbers of unoccupied
rooms of each type. The room occupancy rules must be obeyed, that is
the number of people staying in a room must be between the inclusive
range of the room's min_occ and max_occ.
What is required is an efficient algorithm that simply indicates if
this is possible. My current ideas include presetting an array with the
minimum number of rooms required for different room types and numbers of
people: min_rooms(min_occ,max_occ,num_people) I have already got a
working algorithm for this. As far as I can see to determine if the
holiday request can be satisfied you have to do some sort of
combinatorial process.
In .0 I mentioned an additional problem of a prime room type that had
to figure in any valid solution since it is the basis of a lead-in
price quote. I think you can ignore this for now.
EXAMPLE of what is meant by occupancy:
For a room type with min_occ=2, max_occ=3
Number Number
of of
people rooms
1 0 (can't be done)
2 1
3 1
4 2 (of occupancy 2)
5 2 (2+3)
6 2 (3+3)
7 3 (2+2+3)
8 3 (2+3+3)
9 3 (3+3+3)
So the data to start with is a set of arrays like above for each room
type and a count of the available rooms for each room type.
(some room_types may have the same occupancy min/max as others)
Room Avail Min Max Rooms for
Occ Occ 1 2 3 4 5 6 7 8 9 people
------------------------------------
RT1 1 2 3 0 1 1 2 2 2 3 3 3
RT2 2 1 1 1 2 3 4 5 6 7 8 9
Does this help at all?
Philip
|
| > What is required is an efficient algorithm that simply indicates if
> this is possible.
I find it difficult to separate this off from the algorithm that is
used to determine which rooms are actually going to be allocated. Even if
you are just putting together a query system, then this will rest on the
back of a booking system, and you will have to take account of that in
your design.
So issues become important like how the manager of the hotel wants to
allocate rooms to give himself the maximum flexibility to accept future
visitors, or to maximize use of the most expensive accommodation, or to
rotate occupancy of the rooms in low season.
You should also think of what kind of dialogue the customer is going to
be involved in: suppose three couples are going skiing together: they are
not going to be happy with two triple rooms, are they? Also, the pricing
business needs to be addressed. Once you've identified all the business
requirements for the system like this, then it becomes possible to determine
the logical data structures you will require, the attributes they will have
asssociated with them, and you can represent your algorithms for room
allocation and vacancy queries. If you can find information on any previous
Digital systems on airline booking, for instance, they may be very relevant.
Sorry, perhaps I'm getting this completely wrong, but I get the
strong feeling that in the question you pose you are focussing prematurely
on an interesting but secondary part of your problem.
On the other hand, maybe it makes business sense for you in this
case to put together a prototype, in order to convince management or to
explore what are likely to be tricky TP issues. But that's a different case.
Hope this helps,
Andrew Buchanan.
|
| Re .4
Most of what you say is true. A little background might help.
At the moment the customer lets the users (travel agents) match up
the transport (flights) and accommodation _manually_. They are also
responsible for allocating the rooms to the various members of a
group wishing to go on holiday - presumably by guessing or asking them
about their social arrangements (who sleeps with whom).
What our customer wants is to present the travel agent with valid and
available combinations of transport (there and back) and accommodation.
For them this will be a big leap forward. The will still leave it up
to the travel agent to allocate the rooms in a socially acceptable
fashion. What they want to avoid is presenting holiday styles that they
know are either not valid or not available.
Because of the lack of automated link up between the two components of
a holiday (transport and accommodation) and during the summer when
people buy last minute holidays and there's not much left, the
semi-manual searches jumping between transport and accommodation take
up to 90% of the cpu and disk i/o of a cluster of about 10 8650s.
It is also true, what you say about the algorithm coming up with a
solution in order to answer the yes/no question I suppose. This is a
bit of a side issue though.
My current algorithm allocates some rooms from the prime room type then
calls a recursive routine to find the rest from the other room types.
If this fails it allocates a different number of rooms from the prime
room type and tries again with different number of rooms from the prime
room type.
Philip.
|
| > My current algorithm allocates some rooms from the prime room type then
> calls a recursive routine to find the rest from the other room types.
This sounds like a pretty good way to handle it. (Note, FWIW, that you don't
really need recursion for this: you could keep your own stack, one element for
each of the 9 different room types).
> So the data to start with is a set of arrays like above for each room
> type and a count of the available rooms for each room type.
Accessing that `set of arrays' may be awkward. If it's not, fine.
You aren't refetching the `count of the available rooms' every time, are you?
Your routine should be plenty fast enough. Why not use some typical data, and
see just how fast it is?
|