[Freeciv-Dev] (PR#10203) Greedy CM algorithm

["Per I. Mathisen" <per@xxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=10203 >

On Thu, 16 Sep 2004, Benoit Hudson wrote:
> On Thu, Sep 16, 2004 at 05:30:43AM -0700, Per I. Mathisen wrote:
> > I am working on a different solution (a greedy worker allocation
> > algorithm) that should be extremely fast and can be used for this purpose.
> > It will not be finished in time for release, however, unless someone else
> > want to take over writing it. If so, I can post the pseudo-code design.
>
> I can probably do this.

Ok, here it is:

What user input does a CM (citizen management) algorithm need?

Only two types of input:
 - relative weights (called hereafter "weights")
 - absolute minimums (called hereafter "conditions")

All other kinds of restrictions can be broken down into these two. Want no
unrest? Find the lowest number of luxuries that we need. Want to
celebrate? Again, find the lowest number of luxuries that we need.

The should be capable of doing a full rearrange quickly and with a
reasonably optimal solution. It should also be able to do lightning fast
placement or removal of citizens one by one that does not need to be
globally optimal. In both cases, try hard to fulfill any conditions that
might apply. In both cases, return placement positions, not do any actual
changes.

The CM should be general and not hard-wired to current resource types and
specialists.

The rearrange function shold _only_ be called when the user or the AI
explicitly asks for a rearrange. And don't ever "give up".

Pseudocode:

/* Greedy citizen allocation algorithm */

/*
 * Glossary:
 * source - tile or specialist
 * condition - minimum amount of a resource that we must have
 */

function rearrange {

/* cond_ceil is a special variable that triggers the special
 * fulfill conditions mode; pay attention to its use. */
cond_ceil = num_citizens;

/* Find minimum amount of sources needed to attain each condition. */
for each condition {
  choice = 0;
  val = 0;
  while (val < condition.minimum) {
    if (choice > num_citizens) {
      remove condition;
      break and abort; /* Condition impossible. */
    }
    source = largest_source_by_single_value(condition.resource_type);
    push source on condition.list;
    val += source.value;
    choice++;
  }
  cond_ceil -= condition.list.size;
}

/* Which citizen we are trying to place */
citizen_no = 0;

/* Place citizens loop */
for each citizen {
  if (citizen_no < cond_ceil) {
    /* We can still choose freely, try to do that first and
     * hope that with luck, we fulfill any conditions we have
     * while doing so. */
    source = largest_source_by_all_weights(all_sources.list);
    push source on solution.list;
    if source is tile type {
      pop source from all_sources.list;
      for each condition, if condition.list have source, pop it;
    } /* else source is specialist, and they are unlimited */
  } else {
    /* We must choose from restricted list to ensure fulfillment
     * of condition. */
    condition = find_condition_with_shortest_list_length();
    source = largest_source_by_single_value(condition.list)
    push source on solution.list;
    pop source from condition.list;
  }
  for each condition, if (condition.satisfied) {
    /* Mission accomplished */
    cond_ceil += condition.list.size;
    remove condition;
  }
  citizen_no++;
}
/* The placement of citizens is now in solution.list */

} /* end of rearrange */

If we use cm_parameter for input, we should be able to do very good
comparisons between this algorithm and CMA.

  - Per