[mkgmap-dev] new splitter branch solve-parallel

Thu Jul 1 15:17:59 BST 2021

Hi Ticker,

yes, I think splitter implements something like that.
A a start we have a grid with a given resolution and a single rectangle that covers (part of) this grid. Several criteria tell us if this "tile" has to be split or not.
A split can be horizontal or vertical, but only where the grid is. A simple straightforward approach is to always split in the middle, but that will produce (almost) empty areas in the sea or in deserts.  Therefore other splits have to be tested.  Goal is to find a good split in a reasonable time.
One problem: It is not clear if a valid solution exists  unless one is found.

Gerd

________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap at jagit.co.uk>
Gesendet: Donnerstag, 1. Juli 2021 10:54
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] new splitter branch solve-parallel

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