Seat allocator, By Binh Tran

For AI class PSU Fall 2012

Suppose you are given a set of n people (with n even) to be seated at a dinner party. The people will be seated along the two sides of a long table.

      o   o   o      o
   +-------------   ----+
   |             ...    | 
   +-------------   ----+ 
      o   o   o      o
Half are male, half are female. The given function g(p) identifies the gender of a given person.
As the host, you also know an integer-valued "preference function" h(p1, p2) for a pair of people p1, p2. The preference function indicates how much the first person likes the second; it may be negative.

The "score" of a table is determined by the following criteria:

1 point for every adjacent pair (seated next to each other) of people with one female and the other male.
2 points for every opposite pair (seated across from each other) of people with one female and the other male.
h(p1, p2) + h(p2, p1) points for every adjacent or opposite pair of people p1, p2.
Your job as host is to write a search that will find a "good" table score for a given set of people and preference function.

The data is given to you in the form of an ASCII text file that has the even number n of people on the first line. The first n/2 people are assumed to be female, the rest male. The preference matrix follows on the remaining lines: rows with values separated by spaces. The people are assumed to be numbered 1..n. The seats are assumed to be numbered such that the top half of the table has seats 1..n/2 left-to-right, and the bottom half of the table has seats n/2+1..n left-to-right; thus seat n/2 is opposite seat n.

The output should be a score, then a series of n rows, each with a person number, then a space, then a seat number.

=================================================================================================================================================================

Write up

First I tried to code the complete search. The code is fairly simple, but heuristic in complete search doesn't help as much as I'd hoped for: since the space is discreet and not continuous, a carefully crafted test case will trip it easily. However it works farily well with 10-person case. 11 is a strech and it doesn't run very well beyond that.

Coding a local search w/ random factor is another way to do it. First it initialize a random configuration and then search within the neighbour of the configuration (swapping 2 people) for a better result. The code uses system time's milisecond(even or odd) to determine whether it'll do a "good" move or a random move, but it keeps track of how many time a move (any move) result in a "better" result or not. If this happens more than 100 times consecutively, then it resets the process by reinitialize another random seating. The result is pretty good: of every run I've tried, it managed to get the best result fron the 10-person test some time and results within 10~15% of each other with the 30-person test.

I also tried the annealing method. For this one I actually managed to not be sloppy and code a separate class for storing the seating configuration (instead of using a simple array only). The annealing doesn't give very good result I'm afraid: it never managed to find our the best result in the 10-person, highest so far was 94, with average around 70~80. My assumption is that annealing doesn't have enough entropy compare to local search: only 1 initial random seating vs upward 1.5 million resets in local search. Moreover, the random/good move ratio is less than 50/50: due to the geometric nature of the temperature function, the program spends more time in low temperature than high temperature, and thus spends more time making good moves than random move; my local search uses system time even/odd-ness and can be "hand-wavy" shown to be approximately 50/50 ratio.

Finally I incorporated an "auto" mode that choose the most suitable method based on the size of the test. A seatiing info generator is also written for testing purpose, but it's fairly useless as far as making sure I got a good solution (since verifying the correct solution requires complete search, which takes too long anyway).

Program was written and tested mostly on the PSU lab machine (Intel Core 2 Quad Q9550, 4gb ram, Windows 7 Enterprise, VS 2010). It actually run worse on my personal laptop (Intel i7 M620, 8gb ram, Winidows 7 Pro, VS 2010 - about 30~50% worse, which is to be expected as I didn't use any parallelism technique thus raw power matters) so I wouldn't recommend grading on anything less than a lab PC.

Binh Tran - [email protected] - PSU Fall 2012