Рассадить учеников по партам

[Булат Шакиров]

Имеется:
класс - n рядов по m парт в каждом
n*m ученика из разных школ -
k1 - из 1-й
k2 - из 2-й
k3 - из 3-й
k4 - из 4-й
k1+k2+k3+k4 = m*n
Необходимо рассадить учеников по партам таким образом, чтобы ученики из одной школы не сидели рядом ни по вертикали, ни по горизонтали (по диагонали можно).
Например так.

Цитата

 12    15    17
 15    12    20
 12    15    17
 15    20    12

Задачу я решил использованием генератора случайных чисел, но выяснилось, что существуют такие комбинации расстановок, при которых задача не решается (примерно половина).
Существует ли общий метод (алгоритм), позволяющий решить эту задачу?

Сообщение отредактировано: ozzy - 02.05.03, 12:14

[Demo_S]

оптимизированный перебор (aka  методо ветвей и границ).

Возможно что-нить более оптимальное, но так сходу не придумывается:)

спрошу в понедельник у знающих людей:)

[Булат Шакиров]

Цитата Demo_S, 02.05.03, 14:05:31

спрошу в понедельник у знающих людей:)

Спросил?

[Demo_S]

пока нет, люди от меня (вдвоем) прячутся.
ну сегодня то (среда уже) им точно не отвертеться:)

[Demo_S]

так, конкретно решения не услышаь, так, только мысли умные и не очень:) еще поспрошаю, благо есть у кого:)

а мысли
1) очень похожа на задачу о раскраске, только с ограничением
2) если свести ее к графу, будет легче решать (искать решение)

3) вполне возможно, что прокатит жадный алгоритм.
4) вроде бы рассадить невозможно, только если учеников из какой-нить школы больше половины...

ЗЫ насколько я понял, нужно "раскрасить" клетки шахматной доски так, чтобы никакие две сосдение (по вертикали или горизонтали) не были одного цвета.
но количество "раз которые можно красить" ограничено.

[Фауст]

Предположим, что учеников никакой школы не настолько много, чтобы задача не решалась (грубая оценка - половина всех учеников, точнее будет понятно по ходу решения).
Тогда красим прямоугольник в шахматном порядке в два цвета - чёрный и белый.
Группируем учеников по школам - в порядке уменьшения численности и сажаем все школы по очереди - сначала в чёрные клетки, затем в белые - слева-направо, сверху-вниз. Очевидно, что два ученика одной школы станут соседами только если школа будет последней, которую начали сажать в чёрные клетки, продолжили сажать в белые, и учеников было настолько много, что они встретились - с теми учениками, которых рассадили первыми.
Существует ли решение в таких случаях - не знаю. Возможно удастся доказать, что нет.

[Булат Шакиров]

Количество учеников по школам в сотношении 4:4:2:2 (4:3:3:2).
Где можно почитать про
а) жадный алгоритм
б) задачу о раскраске?

[GrAnd]

Задача Раскраска карты.
Имеется географическая карта, на которой расположено n стран. Каждую страну надо раскрасить в один из k цветов так, чтобы соседние страны были раскрашены в разные цвета.


Географическую карту будем задавать в виде матрицы C размером nґ n. Элемент Ci,j равен 1, если страны i и j – соседние и равен 0 иначе.

Пространство перебора состоит из наборов (x1,...,xn), xi О {1, ...,k}. Условие совместимости m-го элемента с предыдущими: если Ci,m=1 (1 Ј i < m), то xi № xm.

Рекурсивная процедура, осуществляющая перебор с возвратом запишется по рассмотренной схеме:



 procedure перебор_с_возвратом(m : integer);
 var i : integer;
 begin
   if m > n  then
      <найдено решение>
   else
      for i := 1  to k  do begin
         цвет[m] := i;
         if <цвета стран 1,...,m-1 соседних с m-ой не i>  then
          перебор_с_возвратом(m+1);
         end;
 end;

Однако в отличие от задачи о ферзях, в данной задаче перебор можно сократить ещё больше за счёт симметрии решений задачи. Предположим, мы нашли решение задачи. Если мы теперь в этом решении у всех вершин поменяем местами i-ую и j-ую краску, то получившаяся раскраска тоже будет решением. Из таких симметричных решений нам достаточно найти одно. Таким образом, при выборе краски для очередной страны нам достаточно перебрать все уже используемые краски и всего одну (первую) из новых.



 procedure перебор_с_возвратом(m : integer);
 var i : integer;
 begin
    if m > n  then
       <найдено решение>
    else begin
        for i := 1  to кол_красок  do begin
           цвет[m] := i;
           if <цвета стран 1,...,m-1 соседних с m-ой не i>  then
               перебор_с_возвратом(m+1);
        end;
        if кол_красок < k  then begin
           кол_красок := кол_красок+1;
           цвет[m] := кол_красок;
           перебор_с_возвратом(m+1);
           кол_красок := кол_красок-1;
        end;
    end;
 end;