From: kym@sdf.lonestar.org   
      
   Michael Hart  wrote:   
   > Hi all,   
   > I've got a problem trying to maximise the score for an n x n grid of   
   > integers where only one value from each row and column can be chosen   
   > (the score is the sum of the n chosen values). I've tried to find   
   > algorithms to solve this problem by searching the web, however   
   > searching for "grid optimization" or similar yields many results that   
   > are irrelevant to this problem - and unfortunately I don't know how   
   > else to describe it.   
      
   "grid optimisation" is liable to bring up almost anything. ;-)   
      
   This is a classic combinatorial problem and looks like a kind of TSP.   
      
   Essentially, you want to find the permutation of p_0.. p_n-1 that   
   is assigned the greatest value from a table eval[][] using sum eval[i][p_i].   
      
   You can order the permutations using the known locations of the maxima and   
   minima in your table -- if these are "well defined". But I'm pretty sure   
   there's nothing that can shortcut a large number of checks if you want to   
   GUARANTEE an optimum.   
      
   For approximate TSP there are some very fast methods if you don't care   
   if the found "solution" differs from the optimum by a factor (e.g. 2).   
      
   Danes and Hungarians have insights into such things (under suitable   
   definition of induction :).   
      
   ---   
   kym@kym.massbus.org   
   SDF Public Access UNIX System - http://sdf.lonestar.org   
      
   [ comp.ai is moderated.  To submit, just post and be patient, or if ]   
   [ that fails mail your article to , and ]   
   [ ask your news administrator to fix the problems with your system. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)