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@lists.mkgmap.org.uk > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
