Форум на Исходниках.RU

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

GrAnd — Wed, 14 May 2003 10:40:16 +0000

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;

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

Булат Шакиров — Wed, 14 May 2003 10:16:55 +0000

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

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

volatile — Tue, 13 May 2003 09:02:48 +0000

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

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

Demo_S — Wed, 07 May 2003 19:40:40 +0000

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

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

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

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

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

Demo_S — Tue, 06 May 2003 22:04:12 +0000

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

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

Булат Шакиров — Tue, 06 May 2003 04:17:05 +0000

Булат Шакиров:

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

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

Спросил? :)

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

Demo_S — Fri, 02 May 2003 10:05:31 +0000

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

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

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

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

Булат Шакиров — Fri, 02 May 2003 07:00:48 +0000

Булат Шакиров: Имеется:
класс - 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

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