отображение целых чисел на плоскость. есть идеи?

[slaros]

Вопрос к коллективному разуму!

Дано: есть n целых чисел от 1 до 256 и квадратная таблица размера 16x16 (256 ячеек).
Задача:
а. расставить цифры в таблице так, чтобы средняя разность между соседними числами (по горизонтали и вертикали) была минимальна.
Или, в крайнем случае
б. расставить цифры в таблице так, чтобы средняя разность между соседними числами (по горизонтали и вертикали) была меньше некоторого известного d.

Если есть идеи -- буду благодарен.

[Xaositect]

Хорошая задача.
К среде курсовую допишу, подумаю.
Пока никаких мыслей нет, кроме того, что вот такая конфигурация:

...
 10...
  6  9...
  3  5  8...
  1  2  4  7...

может быть оптимальной.

[slaros]

Дополнение:

Очень хочется получить обоснованное решение, в идеале -- АНАЛИТИЧЕСКОЕ доказательство "оптимальности" получаемого отображения.

Также ясно, что можно решить задачу перебором для таблиц меньшего размера (например, для 8x8 перебором) и перейти к большему размеру по-аналогии. Но тогда говорить об оптимальности, к сожалению, не приходится.

Кстати, если бы интересовал минимум ХЭМИНОГОВА расстояния по всем соседним ячейками, то ответ -- коды Грея. Знатоки, отзовитесь, есть что для метрики |x - y|?

[Watchman]

Так вы найдите перебором оптимальную схему для 8x8, 7x7, 6x6... уловите закономерность. Когда она будет ясна, будет проще придумать доказательство.

[Vassil]

Если не ошибаюсь, то упорядочивание первых 256 натуральных чисел, как предлагается выше, т.е. раскручивая ряд естественных чисел с одного угла квадрата, приводит к среднему "расстоянию" равному 10.696615.

А если раскрутит те же числа, начиная с $ N(1,8), N(1,9), N(1,7), N(1,10),$, и так далее, то есть если расположить чисел построчно, начиная с первой строки, симетрично относительно вертикальной оси после 8-ого столбика, то кажется среднее "расстояние" еще меньше, чем при сжатии к одному углу, и равняется уже 8.967448.

Этого можно увидеть запуская "глупую" программку например в SciLab:

// Дано: есть n целых чисел от 1 до 256 и квадратная таблица размера 16x16 (256 ячеек).
// Задача:
// а. расставить цифры в таблице так, чтобы средняя разность между соседними числами (по горизонтали и вертикали) была минимальна.
// Или, в крайнем случае
// б. расставить цифры в таблице так, чтобы средняя разность между соседними числами (по горизонтали и вертикали) была меньше некоторого известного d.
//
  Y=zeros(16,16);
  co = 1; ce = 2;
  for i = 1:16, for j = 8:-1:1, Y(i,j) = co; co = co + 2;end;end;
  for i = 1:16, for j = 9:16, Y(i,j) = ce; ce = ce + 2;end;end;
  Y
  A_D=zeros(16,16);
  for i = 2:15, for j = 2:15, A_D(i,j) = mean([abs(Y(i-1,j)-Y(i,j)),abs(Y(i,j)-Y(i+1,j)),abs(Y(i,j-1)-Y(i,j)),abs(Y(i,j)-Y(i,j+1))]);end;end;
  for j = 2:15, A_D(1,j) = mean([abs(Y(1,j)-Y(2,j)),abs(Y(1,j-1)-Y(1,j)),abs(Y(1,j)-Y(1,j+1))]);end;
  for j = 2:15, A_D(16,j) = mean([abs(Y(15,j)-Y(16,j)),abs(Y(16,j-1)-Y(16,j)),abs(Y(16,j)-Y(16,j+1))]);end;
  for i = 2:15, A_D(i,1) = mean([abs(Y(i-1,1)-Y(i,1)),abs(Y(i,1)-Y(i+1,1)),abs(Y(i,1)-Y(i,2))]);end;
  for i = 2:15, A_D(i,16) = mean([abs(Y(i-1,16)-Y(i,16)),abs(Y(i,16)-Y(i+1,16)),abs(Y(i,15)-Y(i,16))]);end;
  A_D(1,1) = mean([abs(Y(1,1)-Y(2,1)),abs(Y(1,1)-Y(1,2))]);
  A_D(1,16) = mean([abs(Y(1,16)-Y(2,16)),abs(Y(1,16)-Y(1,15))]);
  A_D(16,1) = mean([abs(Y(16,1)-Y(15,1)),abs(Y(16,1)-Y(16,2))]);
  A_D(16,16) = mean([abs(Y(16,16)-Y(15,16)),abs(Y(16,16)-Y(16,15))]);
  md = mean(A_D);
 minmd = md;
printf('Result is:\minmd=%f",minmd)

-- Пт май 22, 2009 12:46:08 --

Еще немного короче будет среднее расстояние, если слегка усовершенствовать то упорядочивание, которое я предложил выше, т.е. симетрично относительно центральной вертикальной оси, притом изнутри во внешность. При нем, припоминаю среднее "расстояние" равнялось 8.967448.
Вопросное совершенствование заключается в следующем. Первая строка делается как было (начиная с $ N(1,8), N(1,9), N(1,7), N(1,10),$ и так далее).Вторая строка принципно такая же, как при прежнем способе, только числа расставляются извне - во внутренность (т.е. (начиная с $ N(2,1), N(2,16), N(2,2), N(2,15),$ и так далее). Третяя строка - как первая, т.е. изнутри - во внешность, ...
Среднее "расстояние" уже 8.930990.
Можно проверить при помощью не менее "глупой" программкой в SciLab:

// Дано: есть n целых чисел от 1 до 256 и квадратная таблица размера 16x16 (256 ячеек).
// Задача:
// а. расставить цифры в таблице так, чтобы средняя разность между соседними числами (по горизонтали и вертикали) была минимальна.
// Или, в крайнем случае
// б. расставить цифры в таблице так, чтобы средняя разность между соседними числами (по горизонтали и вертикали) была меньше некоторого известного d.
//
  Y=zeros(16,16);
  co = 1; ce = 2;
  for i = 1:2:15, for j = 8:-1:1, Y(i,j) = co; co = co + 2;end;co = co + 16;end;
  for i = 1:2:15, for j = 9:16, Y(i,j) = ce; ce = ce + 2;end;ce = ce + 16;end;
  co = 17; ce = 18;
  for i = 2:2:16, for j = 1:8, Y(i,j) = co; co = co + 2;end;co = co + 16;end;
  for i = 2:2:16, for j = 16:-1:9, Y(i,j) = ce; ce = ce + 2;end;ce = ce + 16;end;
  Y
  A_D=zeros(16,16);
  for i = 2:15, for j = 2:15, A_D(i,j) = mean([abs(Y(i-1,j)-Y(i,j)),abs(Y(i,j)-Y(i+1,j)),abs(Y(i,j-1)-Y(i,j)),abs(Y(i,j)-Y(i,j+1))]);end;end;
  for j = 2:15, A_D(1,j) = mean([abs(Y(1,j)-Y(2,j)),abs(Y(1,j-1)-Y(1,j)),abs(Y(1,j)-Y(1,j+1))]);end;
  for j = 2:15, A_D(16,j) = mean([abs(Y(15,j)-Y(16,j)),abs(Y(16,j-1)-Y(16,j)),abs(Y(16,j)-Y(16,j+1))]);end;
  for i = 2:15, A_D(i,1) = mean([abs(Y(i-1,1)-Y(i,1)),abs(Y(i,1)-Y(i+1,1)),abs(Y(i,1)-Y(i,2))]);end;
  for i = 2:15, A_D(i,16) = mean([abs(Y(i-1,16)-Y(i,16)),abs(Y(i,16)-Y(i+1,16)),abs(Y(i,15)-Y(i,16))]);end;
  A_D(1,1) = mean([abs(Y(1,1)-Y(2,1)),abs(Y(1,1)-Y(1,2))]);
  A_D(1,16) = mean([abs(Y(1,16)-Y(2,16)),abs(Y(1,16)-Y(1,15))]);
  A_D(16,1) = mean([abs(Y(16,1)-Y(15,1)),abs(Y(16,1)-Y(16,2))]);
  A_D(16,16) = mean([abs(Y(16,16)-Y(15,16)),abs(Y(16,16)-Y(16,15))]);
  md = mean(A_D);
  minmd = md;
printf('Result is:\minmd=%f",minmd)