У меня возникла такая задачка. Есть кубическая решетка, на ней куб скажем 4*4*4. Нужно придумать какой-нибудь алгоритм проведения по поверхности этого куба ломаной (длина ребра ломаной = длине ребра решетки) длиной, скажем, 14 звеньев таким образом, чтобы она себя не пересекала. При этом необходимо, чтобы она была "как можно более случайной", т.е. тривиальные варианты (например, с зафиксированной одной из координат) не подходят. Глобальная идея в том, чтобы потом после этого изменять куб, забирая один из внешних кубов и пристраивая его еще где-нибудь и проводя ломаную вновь — чтобы у такой цепочки была уже другая конформация. У кого-нибудь есть какие-нибудь идеи?

Здравствуйте, SpaceAce, Вы писали:

SA>У меня возникла такая задачка. Есть кубическая решетка, на ней куб скажем 4*4*4. Нужно придумать какой-нибудь алгоритм проведения по поверхности этого куба ломаной (длина ребра ломаной = длине ребра решетки) длиной, скажем, 14 звеньев таким образом, чтобы она себя не пересекала. При этом необходимо, чтобы она была "как можно более случайной", т.е. тривиальные варианты (например, с зафиксированной одной из координат) не подходят. Глобальная идея в том, чтобы потом после этого изменять куб, забирая один из внешних кубов и пристраивая его еще где-нибудь и проводя ломаную вновь — чтобы у такой цепочки была уже другая конформация. У кого-нибудь есть какие-нибудь идеи?


Есть такая задача: обойти конем все клетки шахматного поля произвольных размеров (и конфигурации). Там алгоритм простой — ходи туда, откуда меньше всего выходов. Скорей всего этот алгоритм подойдет и здесь...

Здравствуйте, SpaceAce, Вы писали:

SA>У меня возникла такая задачка. Есть кубическая решетка, на ней куб скажем 4*4*4. Нужно придумать какой-нибудь алгоритм проведения по поверхности этого куба ломаной (длина ребра ломаной = длине ребра решетки) длиной, скажем, 14 звеньев таким образом, чтобы она себя не пересекала. При этом необходимо, чтобы она была "как можно более случайной", т.е. тривиальные варианты (например, с зафиксированной одной из координат) не подходят. Глобальная идея в том, чтобы потом после этого изменять куб, забирая один из внешних кубов и пристраивая его еще где-нибудь и проводя ломаную вновь — чтобы у такой цепочки была уже другая конформация. У кого-нибудь есть какие-нибудь идеи?

Пожалуйста:
каждая ломаная уникально идентифицируется (случайной) последовательностью выборов построения очередного звена.
Сколько всего вариантов — затрудняюсь сказать, но много

Шаг 1. Выбираем начальную точку. Всего на поверхности куба 4*4*4 имеются 6*3^2 + 12*3 + 8 точек.
Для простоты можно совершить выбор из 6 сторон и 4*4 точек на выбранной стороне (при этом точки на ребрах и вершинах куба имеют бОльшую вероятность, чем точки на гранях).
Пометим выбранную точку.

Шаг 2. Выбираем направление из списка доступных. На ребрах и гранях — это 4 направления, на вершинах — 3.
Обобщенно: рассмотрим 6 точек-соседей данной. Некоторые из них лежат за пределами поверхности; некоторые — уже помечены (провести линию до них означает самопересечение).

Если доступно только 1 направление — идем туда.
Если ничего недоступно — стираем точку, возвращаемся назад и следующий ход совершаем принудительно (все 6 направлений пронумерованы; берем следующее доступное). При этом мы фиксируем в точке значение свободного выбранного хода.
Если принудительные ходы закончились — возвращаемся еще дальше.

Вот и вся механика.

Структура данных:

enum DIR
{
  up, down, left, right, forth, back
};

struct PT
{
  bool busy; // занята ли точка
  DIR free_choise, choise; // указатель направления - результат свободного выбора и результат отката
  // изначально choise = free_choise
};

const side = 4;
const surface_count = 6*(side-1)*(side-1) + 12*(side-1) + 8;
PT surface[surface_count];

void i2xyz(int pt_index, int& x, int& y, int& z); // функция для определения координат
int xyz2i(int x, int y, int z); // получение индекса по координатам (-1 в случае неудачи)
// достаточно произвольные реализации; большого значения не имеют

int next(int pt_index, DIR dir) // функция, вычисляющая индекс следующей точки; -1 если точка за пределами
{
  if(pt_index < 0 || pt_index >= surface_count) return -1;

  int x,y,z; i2xyz(pt_index, x,y,z);

  switch(dir)
  {
  case up: ++z; break;
  case down: --z; break;
  case left: --x; break;
  case right: ++x; break;
  case forth: --y; break;
  case back: ++y; break;
  default: return -1;
  }

  if(x < 0 || x > side || y < 0 || y > side || z < 0 || z > side) return -1;
  // здесь именно >side, поскольку крайние значения координат узлов сетки - это 0 и side включительно

  return xyz2i(x,y,z);
}