Kirkman Tabu Search

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

Problem Description

This program is a rewrite of the previous program to solve Kirkman's Schoolgirl problem and includes a  search all distinct solutions with discovery speed many times faster that the original version.

Background & Techniques

The fascinating Kirkman's Schoolgirl problem asks for 7 arrangements of 15 girls so that they can walk in 5 groups of 3 each day for a week with no girl in a group walking with another girl more than once. Since each girl will be in a group with 2 other girls for each of 7 days, this means that she will be paired with each of the other 14 girls exactly once.

Using a breadth first or depth first search of the "state space" for solution of this problem is generally impractical because of the very large number of possible arrangements to check. For such problems, various "heuristic" (from Greek "discovery") techniques have been developed.   A 2005 paper "A Simple and Efficient Tabu Search Heuristics for Kirkman Schoolgirl Problem", (Dameng Deng, Jun Ma, and Hao Shen), provided the inspiration for this Delphi program which can indeed find all 7 distinct solutions in less than 60 seconds.  The paper was published by the Turku Center for Computer Science as TUCS Technical rReport #704.  It is quite readable as mathematical papers go,  and is currently (September, 2008) available online.  .  

Heuristics - Hill Climbing

A "state" describes a particular configuration of the board or puzzle being investigated. In our case, a 7 particular arrangements of the 15 girls defines a state. A "state space" is the set of all possible states for the problem, a very large number for this problem. One of the heuristic techniques for solving these problems when the space is too large to search is called "Hill Climbing". We need some function that tells us how far we are from the solution. It searches the neighborhood of a current states, (the states we can reach from this state with a single move), and make the move that takes us the largest step closer to the goal state. Hill climbing is successful for many problems, but there are times when the method gets stuck on top a "little hill" next to the mountain we want to climb, but we cannot climb any higher without moving "downhill", further away from our final goal. 

In Kirkman's problem, our measure of distance to the solution is the number of pairs of girls that end up walking together more than once during the week under the current arrangement, we'll call it the "Conflict Score". A "move" is defined as swapping the positions of a pair of girls within a day and the desired moves are those which reduce the conflict score.
 

Heuristics II - Tabu Search

 When we reach the top of one of those "little hills" where no swap will reduce the count further we need to expand the technique . At that point, the Tabu search kicks in and we'll make a move that increases, or at least does not reduce the conflict score. The "Tabu" part means that a particular pair swap for a particular day is "taboo" (not allowed) for the next "Tabu tenure" moves. Tabu tenure is an arbitrary number which depends on the nature of the problem and the techniques used to choose the next move to be made.  In this implementation, 400 works well, the TUCS paper says they used 30, so clearly their selection technique is different, and probably even better, than mine. I was unable to track down the authors for more information.

The "Solution search" page of the program investigates finding solutions. Starting with a random arrangement of girls for each day, solutions will be found at about 2 per second on most computers.


The 7 "Real" Solutions

The second part of the problem once we know how to find solutions rapidly, is to identify the 7 distinct solutions, those which cannot be mapped into another already identified solution by renaming the girls, rearranging the groups within a day or rearranging order of the days. The "Search for unique solutions" page accomplishes this in time which varies depending on the random starting arrangement, but usually within few few minutes. The best "random seed" found so far finds the 7 unique solutions in under a minute after checking only 14 solved cases. The uniqueness check uses only the first of the techniques described in the paper "Solving the Kirkmanís Schoolgirl Problem in a Few Seconds", (Nicolas Barnier and Pascal Brisset).  When searching for a mapping that converts a new solution to an existing unique solution, each pair of a day in the new case must map to the same target day in the existing unique case.   This is a somewhat complicated piece of code (meaning I wrote it  a couple of years ago while "in the zone", but can't really understand it now J).    Perhaps I'll add an option with extra output  to help visualize the mapping check process.  

Addendum September 9, 2008:  Version 3, posted today, adds a 4th tabbed page to the program to further investigate the algorithm which searches for a mapping between two solutions.  The mapping search algorithm finds cases which are distinct much faster than it finds those which map to each other because it takes advantage of the fact that each pair of girls which are together on a day in Case1 , must map to the same day in Case2.   The first discrepancy found is enough to stop checking that possible configuration of girls and move on the the next.  The algorithm used is presented in the Barnier and Brisset paper mentioned above. In brief, it works like this:

  1. For each day of  Case 2, start permuting the  groups within that day, There are  5! or 120 of these arrangements for each day.    (The algorithm starts with day 2 assuming that both cases have been normalized.)
  2. For each of these arrangements, start permuting the girls within their groups. There are 6 ways to arrange the three girls in their group (ABC, ACB, BAC, BCA, CAB, and CBA).  For the current arrangement of 5 groups there are 6x6x6x6x6 or 7,660 permutations to consider.
  3. For each of these 120 x 7,660 arrangements for that day, form a trial mapping from of Case 1.
  4. With the trial map, check the target page for each pair of girls within their groups for each of days 2 through 7 of Case 1.   Each pair within a day must map to the same day of Case 2 as every other pair from that day.  Note that is probably not the same day as where they currently reside.  The forst pait of girls that do not map to the same page declares this mapping as invalid and the algorithm can move back to step 1 for the next permutation.
  5. If step 4 ends without finding a mismatch, we have found the desired mapping from Case1 to Case 2.

In the worst case, day 1 of Case 1 maps to the last permutation of day 7 of Case 2  over 300,000,000 pair comparison tests would have been made.   In practice the mapping, if one exists, is generally found to day 2 or 3 with "only" a few million comparisons.      

 The "Search for unique solution" page now has an option to save all solutions found, unique of not, to a text file.   These file may be read into the "Checking Ismorphisms" page, and two cases selected for checking.  Case labels indicate existing mappings so it is easy to select cases that will map to each other.  When a mapping is found, details of the mapping are displayed as well as other run statistics.

By the way, DFF library unit  UCombV2 is used by Kirkman_Tabu and for permuting groups is required to recompile.  Download the  library zip file, DFFLibV11 or later to get access.   

Addendum September 10, 2008:  one more small update, making version 3.1, which adds a button to help find short  solutions for the 7 unique cases.  the "Checking Isomorphisms"  page also now shows the reverse mapping from "normalized" back to "as read" versions of the cases read.  

November 23, 2012: A small cosmetic upgrade today to Version 3.2 which improves view-ability of the pages.

 

Running/Exploring the Program 

Suggestions for Further Explorations

The current implementation of the algorithm for checking isomorphism could be made faster.       

 

Original Date: September 2, 2008

Modified: February 18, 2016

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright © 2000-2017, Gary Darby    All rights reserved.