Re: FN-FORUM: "Network" analysis

date posted 24th January 2005 18:51

Charles Lecklider writes:

> Alex Farran wrote:
>> Charles Lecklider writes:
>>
>>> Starting with the cheapest heap (read: pitch) (or most expensive, or
>>> random, or whatever) allocate the longest period of time you can,
>>> starting on the day they want. You'll get 0 or more days. Calculate the
>>> next starting date, pick the next heap. Lather, rinse, repeat.
>>
>> That's an example of an heuristic algorithm, where the heuristic you
>> 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?
> How much easier is it to debug? Would the network version not be a 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
> availability on any given day (can we stay an extra day please?),
> performance, and maximising resource usage. My feeling is that a
> network-based solution will maximise resource usage, but at the expense
> of availability, and most certainly hurt performance. I think 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
> only valid test is to feed in the previous few years' data and see 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.

--

__o Alex Farran - Open source software specialist
_`\