[mkgmap-dev] new splitter branch solve-parallel

Thu Jul 1 10:53:18 BST 2021

Hi Gerd,
well setting initial search limit to 1000000 solves already loads of bad
solutions and is still quite fast. Albeit using v 408 it was the best
universal value I felt. Not much slower but in many cases getting better
results. Going for much bigger initial value actually then caused also
worse splits. I do not know how right now it determines the max value. but
maybe increasing it would be good. And I feel it should increase/wait if
the split obviously is not good. If it is good (all tiles except one within
80% of maxnodes) or very good (all except one 85%) it could stop earlier in
order not to waste resources.
I do not know how easy such a solution is to be implemented however. So far
most bad splits are really realy bad (e.g. Norway 210 vs 135 tiles - in
such cases a much longer time taken to find a good split is reasonable.
Also as mkgmap will run faster if the split is better, compressing the maps
will produce a smaller overall size if the split is better.

On Thu, 1 Jul 2021 at 11:54, Ticker Berkin <rwb-mkgmap at jagit.co.uk> wrote:

> Hi Gerd
>
> Is this of any relevance -
>
> https://en.wikipedia.org/wiki/Branch_and_bound
>
> Ticker
>
> On Wed, 2021-06-30 at 16:08 +0000, Gerd Petermann wrote:
> > Hi all,
> >
> > I've started this branch to further improve the split results.
> > Splitter has two different algorithms to find good splits.
> > 1) Algo FULL tries first to split in the middle and then continues
> > with the next positions (mid+1, mid-1, mid+2, mid-2, ...)
> > The resulting parts are split again recursively. This should find the
> > best possible split but can take very long when the only good split
> > starts far from the middle.
> >
> > 2) Algo SOME uses some heuristics to test only some of the possible
> > splits. This is typically much faster but sometimes doesn't find any
> > solution and sometimes the FULL algo finds a better solution.
> >
> > The trunk version tries first the one that is more promising and - if
> > that fails to find a good split - tries the other. So, sometimes the
> > FULL algo works for 2 minutes and then SOME finds a good result in a
> > few seconds.
> >
> > This branch executes both algorithms in parallel and uses the better
> > result.
> >
> > One of the open problems is to decide under what conditions the
> > execution should stop.
> > If the SOME algo finds a good solution within 20 secs should we still
> > continue the FULL algo to find the best solution? If yes, how long?
> > I'm playing with this, any input is welcome.
> >
> > Gerd
> > _______________________________________________
> > mkgmap-dev mailing list
> > mkgmap-dev at lists.mkgmap.org.uk
> > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>

-- 
Felix Hartman - Openmtbmap.org & VeloMap.org
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20210701/377f5618/attachment.html>