Лента Мой малыш
Городские форумы
Автофорумы
Халявный
Домоводство
Проф. и бизнес форумы
Строительные форумы
Технофорумы
Собачий форум
Велофорумы Нижнего Новгорода
Наши дети
Туризм, отдых, экстрим Творческий
Путешествия Спортивные форумы
Нижегородская область Недвижимость
Форумы по интересам
Частные форумы Форумы домов Жилые районы
Отзывы и предложения (техподдержка)
Реклама на NN.RU
+7 (831) 261-37-60
Техподдержка Полная версия

Переход от табличного задания _изменений_ матриц/списков смежности к аналитическому для вычисления промежуточных состояний - как осуществить?

Дано (очень упрощённый пример):

1) объекты на определённых позициях, на самом деле это 3D объект, но проще задать описание вот такой 1D матрицей в примере:
int[] p = new int[]{0,1,2,3,4,5,6,7}; // initial positions

2) N (а данном случае 6, но может быть больше, гораздо сильно больше), скажем так, "простых воздействий", которые меняют исходную матрицу смежности:
private void anim_X_CW_end() { p = new int[]{p[0], p[2], p[7], p[3], p[1], p[5], p[6], p[4]}; }
private void anim_X_CCW_end() { p = new int[]{p[0], p[4], p[1], p[3], p[7], p[5], p[6], p[2]}; }
(ну и для Y и Z аналогично)

3) Ну и в итоге после шага 2 - считаем листы смежности тоже влёгкую (с матрицей смежности - аналогично, просто чуть более громоздко, здесь приводить потому не буду):
adj_list = new int[][]
{
{p[1],p[3],p[5]}, // x,y,z neighbours for 0
{p[0],p[2],p[4]}, // x,y,z neighbours for 1
{p[3],p[1],p[7]},
{p[2],p[0],p[6]},
{p[5],p[7],p[1]},
{p[4],p[6],p[0]},
{p[7],p[5],p[3]},
{p[6],p[4],p[2]}, // x,y,z neighbours for 7
};

Тут с табличным заданием изменений и подсчётом списков смежности проблем ваще никаких (уже готово, демка пашет, всё замечательно) в виду очень малой размерности задачи.

При росте же размерности (как кол-ва объектов, так и возможных воздействий для изменения их смежности) задавать таблично становится проблемой (ограничение по памяти) - надо задавать как-то аналитически это, формулой/функцией/etc...

Или, допустим, мы имеем:
{0,1,2,3,4,5,6,7}
и хотим получить все промежуточные шаги для перехода в:
{3,4,1,0,5,6,4,7}
с помощью некой формулы.

Важный момент: эта штука должна быть 100% детерминированной, конечной, т.е. "брутфорс рулит!", "посчитать генетическими алгоритмами!" (за хз какое время и хз с какой вероятностью успеха) и т.п. не подходят, увы.

Вопрос: есть ли какие-то формальные способы (чем проще тем лучше, я не вот прям математик) как перейти от табличного задания (хотя бы тот простой пример выше) к аналитическому?

Задача сугубо практическая, т.е. буду очень-очень признателен за любые подсказки!!!
Заранее большое спасибо всем откликнувшимся!!!

P.S. На вопросы "а для чего это?" я к моему великому сожалению ответить напрямую не могу, но могу ближайшими общеизвестными аналогиями: промежуточные кадры при морфинге 3D объектов (кто с 3D работал в курсе, что это очень просто если тупо по прямым и нету ограничений какая точка перейдёт в какую и будет ли пересекать внутренности объекта или нет), фолдинг белков, swarm intelligence, изменяемые mesh топологии, робототехника/механика с N элементов у каждого из которых есть 3-5 степени свободы и т.д. - кому что нравится и что "ближе" :)
0
Ответить
А какое свойство-то у этого "шага"? Или какие-то ограничения?
Если что-то типа "не сильно менять матрицу за шаг", то можно попробовать алгоритмы сортировки.
Грубо говоря, ставим веса по порядку в целевой матрице и начинаем сортировку пузырьком. За каждый шаг там только одна пара (причем соседняя) меняется.
0
Ответить
Похоже, что задача хорошо решается с помощью разреженной матрицы. Если используются поверхности в 3Д, то большая часть элементов будут пустыми, а пустые элементы в разреженной матрице не хранятся. Правда будет некоторый вычислительный оверхед, но его можно минимизировать. Если это не слишком критично, то должно хорошо работать.

Аналитически, наверное, можно посчитать только для простых объектов.
0
Ответить
там несколько ближе, если проводить аналогии, к "роботоруке" сложной конфигурации.

т.е. менять один элемент за раз не вариант, т.к. из N объектов сразу несколько в пространстве конфигурацию меняют (как бы "атомарно") и соответственно матрица на конец итерации вся пересчитывается и уже передаётся в "решалку".
есть эмуляция физ.объекта (о ней речь) и отдельно "решалка" (автомат обычный), которая понимает по adjscency какое конечное состояние достигнуто и выполняет некие действия (ок, проговорюсь тут немного) с поверхностью всего объекта или его части.
хотя... более атомарные действия... возможно и вариант, спасибо! :)

p.s. ок, проговорюсь ещё: stealth tank в command&conquer видели? :)) ну вот он корпус/башню повернул и должен пересчитать что врагам показывать на своих боках.
0
Ответить
да, была такая мысль со sparse matrix [ netlib.org/linalg/html_templates/node90.html ], но всё равно довольно много (для памяти МК) их получается, плюс промежуточные состояния надо бы считать...
ну т.е. там если "языком домохозяек" мне надо "при воздействии переставлять элементы по индексам (понять каким) местами" - вопрос по каким индексам (как-то формализовать) и можно ли это формулой делать (и главное как к этой формуле/формулам привести)
т.е. для 8 элементов я эти перестановки подобрал вручную, но если элементов будет 100, то боюсь я годами буду подбирать какие индексы в матрице менять с какими :)))
0
Ответить
ну что я на это могу сказать - тут думать надо, а думать - это время, а время - это, как всегда, деньги... сами понимаете...
0
Ответить
я понимаю, вот думаю... :)
просто думал вдруг моя "проблема" в мире проблемой давно не является и мне дадут ссылку на алгоритм уже давно изобретёный (конечно же я не ожидал что кто-то тут будет думать за меня, скорее ожидал что поржут над "вот проблемища то!..." да кинут в меня ссылкой на общеизвестный алгоритм) ...
0
Ответить
Ну так это 3д движок по сути. Если коротко - то строятся нормали к полигонам сначала. При этом будем полагать для простоты, что полигоны образуют замкнутый объем. Затем от воображаемой камеры проводим линию к основанию каждой нормали и вычисляем угол. В зависимости от угла принимаем решение рисовать или нет полигон. Тут еще возможны всякие оптимизации - не силен в этой области.

А так вроде даже на хабре были статьи типа "пишем свой 3д движок".
0
Ответить
да, примерно так, но это железяка (и эмулятор железяки) на самом деле будет...
0
Ответить
девел0пер писал(а)
Или, допустим, мы имеем:
{0,1,2,3,4,5,6,7}
и хотим получить все промежуточные шаги для перехода в:
{3,4,1,0,5,6,4,7}
с помощью некой формулы.


можно ли задачу в такой постановке свести к преобразованию между двумя облаками точек?
если да - то есть исп - en.wikipedia.org/wiki/Iterative_closest_point
на вход два облака точек,
на выходе вектор сдвига и матрица поворота
0
Ответить
девел0пер писал(а)
Важный момент: эта штука должна быть 100% детерминированной, конечной, т.е. "брутфорс рулит!", "посчитать генетическими алгоритмами!" (за хз какое время и хз с какой вероятностью успеха) и т.п. не подходят, увы.

Вопрос: есть ли какие-то формальные способы (чем проще тем лучше, я не вот прям математик) как перейти от табличного задания (хотя бы тот простой пример выше) к аналитическому?


Вообще говоря любые дискретные операции задаются таблицами истинности. А насколько я понимаю, речь как раз идет о дискретной аналитике. Соответственно, любое аналитическое выражение подразумевает наличие этих таблиц истинности или соответствия элементов во множествах.
И получается что вы хотите рассмотреть задачу с точки зрения оптимизации способа записи ее решения , то есть как записать решение задачи максимально коротко. Для этого обычно вводятся понятие и, соответственно, обозначение некоторой операции которая все равно задана таблицей.
Все процессоры поддерживают примерно одинаковый набор таких операций в виде инструкций ассемблера,
А вот видеокарты (например) или ПЛИС-микросхемы, позволяют конструировать более широкий класс дискретных операций. То есть есть разные устройства которые реализуют готовые дискретные операции, соответственно для этих операций не надо хранить таблицы.
Соответственно любая аналитика здесь должна быть основана на возможностях выбранной аппаратной платформы, ну и задачу (или класс задач) нужно все таки сформулировать с необходимой степенью полноты.
Ну а вы пытаетесь сформулировать задачу совершенно оторванную от реальности, в этом ваша ошибка, мне кажется!
0
Ответить
всем спасибо, оказалось задача решается проще через обычные "кагбэ проекции": набор выпуклых полигонов как бы разворачивается на плоскость, задача становится 2-мерной (ну на самом деле из 4-мерной в 3-мерную переходит).
да, не так удобно как adjacency, увы, в итоге придётся небольшое API написать на "взятие", зато с shift'ом при вращении (а я SW эмулирую набор HW объектов) - никаких головоломок (ну почти) :)))
0
Ответить
вообще не в тему, уж извините.
0
Ответить
спасибо, вы ближе всех подошли к решению, я выбрал такое: развернуть полигоны на плоскость, типа проекции, выполнять shift'ы при вращении там для поддержания модели системы, но само взятие результатов конечно не такое удобное получается как у adjacency matrix.
0
Ответить