<div dir="ltr"><div>Hi Gerd,</div>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. <div>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.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, 1 Jul 2021 at 11:54, Ticker Berkin <<a href="mailto:rwb-mkgmap@jagit.co.uk">rwb-mkgmap@jagit.co.uk</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi Gerd<br>
<br>
Is this of any relevance -<br>
<br>
<a href="https://en.wikipedia.org/wiki/Branch_and_bound" rel="noreferrer" target="_blank">https://en.wikipedia.org/wiki/Branch_and_bound</a><br>
<br>
Ticker<br>
<br>
On Wed, 2021-06-30 at 16:08 +0000, Gerd Petermann wrote:<br>
> Hi all,<br>
> <br>
> I've started this branch to further improve the split results. <br>
> Splitter has two different algorithms to find good splits. <br>
> 1) Algo FULL tries first to split in the middle and then continues<br>
> with the next positions (mid+1, mid-1, mid+2, mid-2, ...) <br>
> The resulting parts are split again recursively. This should find the<br>
> best possible split but can take very long when the only good split<br>
> starts far from the middle. <br>
> <br>
> 2) Algo SOME uses some heuristics to test only some of the possible<br>
> splits. This is typically much faster but sometimes doesn't find any<br>
> solution and sometimes the FULL algo finds a better solution. <br>
> <br>
> The trunk version tries first the one that is more promising and - if<br>
> that fails to find a good split - tries the other. So, sometimes the<br>
> FULL algo works for 2 minutes and then SOME finds a good result in a<br>
> few seconds.<br>
> <br>
> This branch executes both algorithms in parallel and uses the better<br>
> result. <br>
> <br>
> One of the open problems is to decide under what conditions the<br>
> execution should stop.<br>
> If the SOME algo finds a good solution within 20 secs should we still<br>
> continue the FULL algo to find the best solution? If yes, how long?<br>
> I'm playing with this, any input is welcome.<br>
> <br>
> Gerd<br>
> _______________________________________________<br>
> mkgmap-dev mailing list<br>
> <a href="mailto:mkgmap-dev@lists.mkgmap.org.uk" target="_blank">mkgmap-dev@lists.mkgmap.org.uk</a><br>
> <a href="https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev" rel="noreferrer" target="_blank">https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev</a><br>
_______________________________________________<br>
mkgmap-dev mailing list<br>
<a href="mailto:mkgmap-dev@lists.mkgmap.org.uk" target="_blank">mkgmap-dev@lists.mkgmap.org.uk</a><br>
<a href="https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev" rel="noreferrer" target="_blank">https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev</a><br>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div>Felix Hartman - Openmtbmap.org & VeloMap.org<br></div><br></div></div></div></div></div></div>