commit | bb561286031d7827979d62b49b223fbc52ab67f1 | [log] [tgz] |
---|---|---|

author | Paul King <paulk@asert.com.au> | Fri Feb 09 16:30:10 2024 +1000 |

committer | Paul King <paulk@asert.com.au> | Fri Feb 09 16:30:10 2024 +1000 |

tree | 7e36c37affad4781c06622ecd7b9bf73596dba1d | |

parent | e7aae13b9cf1f38446e3b8312f9d9c524dec76e2 [diff] |

move towards generating graphviz images

diff --git a/generator/build.gradle b/generator/build.gradle index 13c22e1..8455590 100644 --- a/generator/build.gradle +++ b/generator/build.gradle

@@ -17,15 +17,19 @@ * under the License. */ -apply plugin: 'groovy' +plugins { + id 'groovy' +} repositories { mavenCentral() } +ext.groovyVersion = '3.0.20' +ext.asciidocVersion = '2.5.11' +ext.asciidoctorDiagram='2.2.10' + dependencies { - ext.groovyVersion = '3.0.20' - ext.asciidocVersion = '2.5.7' implementation "org.codehaus.groovy:groovy:$groovyVersion" implementation "org.codehaus.groovy:groovy-dateutil:$groovyVersion" implementation "org.codehaus.groovy:groovy-json:$groovyVersion" @@ -37,6 +41,7 @@ // you might need to use a custom jruby version //exclude(group: 'org.jruby', module: 'jruby-complete') } + implementation "org.asciidoctor:asciidoctorj-diagram:$asciidoctorDiagram" //compile "org.jruby:jruby-complete:9.1.17.0" }

diff --git a/generator/src/main/groovy/generator/SiteGenerator.groovy b/generator/src/main/groovy/generator/SiteGenerator.groovy index 5a2bddd..1406cbb 100644 --- a/generator/src/main/groovy/generator/SiteGenerator.groovy +++ b/generator/src/main/groovy/generator/SiteGenerator.groovy

@@ -230,7 +230,7 @@ } private void renderBlog() { - def asciidoctor = AsciidoctorFactory.instance + def asciidoctor = AsciidoctorFactory.instanceasciidoctor.requireLibrary('asciidoctor-diagram') println "Rendering blogs" def blogDir = new File(sourcesDir, "blog")

diff --git a/site/src/site/blog/groovy-knapsack.adoc b/site/src/site/blog/groovy-knapsack.adoc index de40f5f..d22c532 100644 --- a/site/src/site/blog/groovy-knapsack.adoc +++ b/site/src/site/blog/groovy-knapsack.adoc

@@ -1,8 +1,7 @@ = Solving the Knapsack Problem with Groovy Paul King -:revdate: 2024-02-03T20:08:00+00:00 -:keywords: knapsack, optimisation -:draft: true +:revdate: 2024-02-09T15:00:00+00:00 +:keywords: knapsack, optimisation, choco, genetic algorithms, dynamic programming :description: This post looks at solving the knapsack problem with Groovy. The @@ -48,8 +47,8 @@ This is known as the 0/1 knapsack variation of the problem. We'll look at some other variations later. -Our goal then is to find out which gems we place into the knapsack to maximise -the value. +Our goal then is to find out which gems we place into the knapsack to +maximise the value. image:img/knapsack.jpg[A knapsack and some gems] @@ -141,8 +140,11 @@ It is useful to visualize the above process as a solution tree (shown for capacity 10): -[graphviz] ----- +image:img/brute-force-tree.png[brute force tree] + +//[graphviz,brute-force-tree] +[comment] +-- digraph unix { fontname="Helvetica,Arial,sans-serif" node [fontname="Helvetica,Arial,sans-serif"] @@ -260,7 +262,9 @@ n____ -> n____1 [label="Gem1"]; n____ -> n_____ [label=<<s>Gem1</s>>]; } ----- +-- + +The light red nodes indicate where subsequent processing of the solution tree can be skipped. We calculate here the result for 3 different knapsack weight limits (6, 8, and 10). The output looks like this: @@ -299,16 +303,22 @@ == Using Branch and Bound -Another technique often used for optimisation is branch and bound. +Another technique often used for optimisation is +https://en.wikipedia.org/wiki/Branch_and_bound[branch and bound]. It's a special form of the general principle of divide and conquer; solving a big problem by turning it into smaller problems. Divide and conquer is similar to what we did for the recursive solution above, but with branch and bound, we perform smarter elimination. Before processing the children of a branch, the branch is checked against -upper and lower estimated bounds of some optimal solution and is discarded -if it cannot produce a better solution. For the knapsack problem, -we could find an optimal "greedy" solution if we could use fractional +upper and lower estimated bounds of some optimal solution. Processing for +a given path is terminated if we can determine that heading down that +path can't possibly be better than heading done some alternative path. +For the knapsack problem, +we can work out those bounds by finding the optimal "greedy" solution if +we were allowed to use fractional quantities of a given knapsack item. +We'll look at fractional quantities as the last example in this blog. +It turns out we can calculate them very efficiently. First, we'll create an `Item` record for holding our weights and values. @@ -418,8 +428,11 @@ Which has this visualization (for capacity 10): -[graphviz] ----- +image:img/branch-and-bound-tree.png[branch and bound tree] + +//[graphviz,img/branch-and-bound-tree] +[comment] +-- digraph unix { fontname="Helvetica,Arial,sans-serif" node [fontname="Helvetica,Arial,sans-serif"] @@ -511,11 +524,11 @@ n34__ -> n34___ [label=<<s>Gem1</s>>]; n3___ -> n3____ [label=<<s>Gem1</s>>]; } ----- +-- We should note that as well as discarding the -infeasible paths which exceed the weight limit, -we now also discard unfruitful paths which our bound +infeasible paths which exceed the weight limit (light red), +we now also discard unfruitful paths (light purple) which our bound value tells us can never exceed some alternative _best_ path we already know about. @@ -527,7 +540,9 @@ == Using Dynamic Programming -You can think of dynamic programming as a special case of the +You can think of +https://en.wikipedia.org/wiki/Dynamic_programming[dynamic programming] +as a special case of the branch and bound technique. It can also be thought of as similar to the memoization we looked at earlier. In this case, rather than Groovy providing us with the cache, we track it ourselves @@ -558,6 +573,14 @@ } ---- +To solve the knapsack problem, we break it into smaller pieces. +If we have already cached the solution to the smaller piece, we use +the cached value. Because of the way we have structured our problem, +we are actually sharing the cached results for the different +knapsack sizes. + +When we run this script, it produces the following output: + ---- Total value for capacity 6 = 17 Total value for capacity 8 = 25 @@ -642,7 +665,7 @@ Total value for capacity 10 = 30 ---- -Most often bitsets are used not just to save memory but +Most often, bitsets are used not just to save memory but because for certain problems we can perform operations on entire bitsets. You can think of this as bulk operations with _free_ parallelism when compared to performing @@ -678,6 +701,8 @@ Which has the same output for this case study, so luckily, our crude optimisation step didn't reject the best solution. +In ths example, we just shifted an integer. Depending on the +particular problem, we might wan tto instead shift a long or bitset. Groovy 5 adds support for `<<` (left shift),`>>` (right shift), and `>>>` (right shift unsigned) operators for bitsets. This kind of functionality will make working on such @@ -685,16 +710,22 @@ == Using Constraint Programming -Another technique we could consider is constraint programming. +Another technique we could consider is +https://en.wikipedia.org/wiki/Constraint_programming[constraint programming]. Here we define some constraints and let a solver find solutions -for us. Here we have used the Choco solver. +for us. Here we have used the +https://choco-solver.org/[Choco solver]. We thought we would also spice up the example and illustrate -what is known as the bounded knapsack problem. Instead of +what is known as the _bounded knapsack problem_. Instead of either taking the gem or leaving it out, we now consider gems to be readily available commodities and the weight and value would apply to all gems of a particular type. +In general, we can take as many gems of a particular type as we want +(this would be unbounded), or as we'll do here take as many +gems of a particular type up to some bound. + In our example, we'll set the bound for our solver's domain variables to be between `0` and `W`. We could easily set the upper bound to be `1` and @@ -787,7 +818,9 @@ == Using OrTools Other libraries also have built-in solvers for knapsack. -Here is another implementation using the OrTools library: +Here is another implementation using the +https://developers.google.com/optimization[OrTools] +library: [source,groovy] ---- @@ -829,7 +862,9 @@ == Using Jenetics -We can also use Genetic Algorithms to find a solution. +We can also use +https://en.wikipedia.org/wiki/Genetic_algorithm[Genetic Algorithms] +to find a solution. When creating solutions based on genetic algorithms, a series of steps take place which mimic evolution in nature. We typically start with some random guesses, @@ -1029,5 +1064,8 @@ == Conclusion We have seen how to solve the knapsack problem in Groovy -using several approaches. In the references, there are even +using several approaches. In the +https://www.hindawi.com/journals/mpe/2023/1742922/[references], there are even more exotic algorithms which can be used to solve the knapsack problem. +If you have a great way to solve the knapsack problem using Groovy, +let us know and we can add it to this blog!