RE: FN-FORUM: "Network" analysis

date posted 24th January 2005 19:18

I think the bit reduction method will go some way to helping with the
size of the problem by limiting the number of records that have to be
included in the network - there's no point in duplicating a record after
all. I'll keep you guys posted as to what's eventually implemented

-----Original Message-----
From: [EMAIL REMOVED] [EMAIL REMOVED] On Behalf Of Alex
Farran
Sent: Monday, January 24, 2005 8:09 PM
To: Andy Macnaughton-Jones
Subject: Re: FN-FORUM: "Network" analysis


Charles Lecklider writes:

> Alex Farran wrote:
>> Charles Lecklider writes:
>>=20
>>> Starting with the cheapest heap (read: pitch) (or most expensive, or

>>> random, or whatever) allocate the longest period of time you can,=20
>>> starting on the day they want. You'll get 0 or more days. Calculate=20
>>> the next starting date, pick the next heap. Lather, rinse, repeat.
>>=20
>> That's an example of an heuristic algorithm, where the heuristic you=20
>> use is the longest period of time available for a pitch starting on a

>> given date. It's quite an extreme example because it relies entirely

>> on the heuristic, with no backtracking to explore other branches. It

>> won't produce the optimal result, but it is fast.

> Yes, but how much worse is it than the complex network-based version?=20
> How much easier is it to debug? Would the network version not be a=20
> good example of "premature optimisation"?

Oh, I'm not arguing against that solution, just putting it in the
context of the problem as it was framed, and my response. The network
diagram is just a way of visualising the problem, and your solution fits
into that visualisation. We're both saying the same thing, don't try
for a perfect fit if it's costly and you can get by with good enough.
Your solution is a practical demonstration of the heuristic approach I
suggested.

> In this case there's a compromise needed between maintaining=20
> availability on any given day (can we stay an extra day please?),=20
> performance, and maximising resource usage. My feeling is that a=20
> network-based solution will maximise resource usage, but at the=20
> expense of availability, and most certainly hurt performance. I think=20
> mine will be more user-friendly in that fewer people will have to move

> less often, but you might have been able to squeeze more people
through the system.
> You can of course come up with a dataset to disprove either, but the=20
> only valid test is to feed in the previous few years' data and see=20
> what happens. I'd be interested to see the results.

Actually I think your solution will fill the pitches just as well as any
other algorithm, but as the number of people booking increases it will
tend towards sub optimal allocation (ie lots of moving and further
between moves) earlier than is absolutely necessary. But that's just a
guess. Gauging the performance of one algorithm against another is what
you need the theory and testing for, but you may decide it's better to
optimise the time spent programming, since that's more expensive than
CPU cycles.

Thinking about the problem again. Another criteria for judging the
algorithm might be the 'evenness' of the solutions it returns. What I
mean is that the algorithms suggested so far will give the best bookings
to the earlier bookings and get progressively worse as the site fills
up. A really smart algorithm might aim to give an even level of service
to every camper, perhaps optimised for the typical number of bookings at
that time of year.

The bit reduction solution is interesting. I need to give that another
look to see if it short circuits the problem, or is simply a good
instruction level optimisation.

--=20

__o Alex Farran - Open source software specialist=20
_`\