Ощущается как 0

Новая тема

Вы не можете создавать новые темы.
Т.к. вы неавторизованы на сайте. Пожалуйста назовите себя или зарегистрируйтесь.

Список тем

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

Серьёзная тема

330

С друзьями на NN.RU

У вас пока нет друзей на NN.RU, поэтому ссылка на тему не может быть отправлена.

Воспользуйтесь поиском, чтобы найти новых друзей.

В социальных сетях

девел0пер

17.02.2018

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

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 степени свободы и т.д. - кому что нравится и что "ближе" :)

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

alxumuk2

17.02.2018

А какое свойство-то у этого "шага"? Или какие-то ограничения?
Если что-то типа "не сильно менять матрицу за шаг", то можно попробовать алгоритмы сортировки.
Грубо говоря, ставим веса по порядку в целевой матрице и начинаем сортировку пузырьком. За каждый шаг там только одна пара (причем соседняя) меняется.

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

девел0пер

17.02.2018

там несколько ближе, если проводить аналогии, к "роботоруке" сложной конфигурации.

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

p.s. ок, проговорюсь ещё: stealth tank в command&conquer видели? :)) ну вот он корпус/башню повернул и должен пересчитать что врагам показывать на своих боках.

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Ivanushka-durachok

17.02.2018

Ну так это 3д движок по сути. Если коротко - то строятся нормали к полигонам сначала. При этом будем полагать для простоты, что полигоны образуют замкнутый объем. Затем от воображаемой камеры проводим линию к основанию каждой нормали и вычисляем угол. В зависимости от угла принимаем решение рисовать или нет полигон. Тут еще возможны всякие оптимизации - не силен в этой области.

А так вроде даже на хабре были статьи типа "пишем свой 3д движок".

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

девел0пер

18.02.2018

да, примерно так, но это железяка (и эмулятор железяки) на самом деле будет...

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

девел0пер

22.02.2018

спасибо, вы ближе всех подошли к решению, я выбрал такое: развернуть полигоны на плоскость, типа проекции, выполнять shift'ы при вращении там для поддержания модели системы, но само взятие результатов конечно не такое удобное получается как у adjacency matrix.

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Ivanushka-durachok

17.02.2018

Похоже, что задача хорошо решается с помощью разреженной матрицы. Если используются поверхности в 3Д, то большая часть элементов будут пустыми, а пустые элементы в разреженной матрице не хранятся. Правда будет некоторый вычислительный оверхед, но его можно минимизировать. Если это не слишком критично, то должно хорошо работать.

Аналитически, наверное, можно посчитать только для простых объектов.

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

девел0пер

17.02.2018

да, была такая мысль со sparse matrix [ netlib.org/linalg/html_templates/node90.html ], но всё равно довольно много (для памяти МК) их получается, плюс промежуточные состояния надо бы считать...
ну т.е. там если "языком домохозяек" мне надо "при воздействии переставлять элементы по индексам (понять каким) местами" - вопрос по каким индексам (как-то формализовать) и можно ли это формулой делать (и главное как к этой формуле/формулам привести)
т.е. для 8 элементов я эти перестановки подобрал вручную, но если элементов будет 100, то боюсь я годами буду подбирать какие индексы в матрице менять с какими :)))

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Ivanushka-durachok

17.02.2018

ну что я на это могу сказать - тут думать надо, а думать - это время, а время - это, как всегда, деньги... сами понимаете...

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

девел0пер

17.02.2018

я понимаю, вот думаю... :)
просто думал вдруг моя "проблема" в мире проблемой давно не является и мне дадут ссылку на алгоритм уже давно изобретёный (конечно же я не ожидал что кто-то тут будет думать за меня, скорее ожидал что поржут над "вот проблемища то!..." да кинут в меня ссылкой на общеизвестный алгоритм) ...

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Жданный Гость

20.02.2018

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

можно ли задачу в такой постановке свести к преобразованию между двумя облаками точек?
если да - то есть исп - en.wikipedia.org/wiki/Iterative_closest_point
на вход два облака точек,
на выходе вектор сдвига и матрица поворота

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

ruhi

21.02.2018

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

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

Вообще говоря любые дискретные операции задаются таблицами истинности. А насколько я понимаю, речь как раз идет о дискретной аналитике. Соответственно, любое аналитическое выражение подразумевает наличие этих таблиц истинности или соответствия элементов во множествах.
И получается что вы хотите рассмотреть задачу с точки зрения оптимизации способа записи ее решения , то есть как записать решение задачи максимально коротко. Для этого обычно вводятся понятие и, соответственно, обозначение некоторой операции которая все равно задана таблицей.
Все процессоры поддерживают примерно одинаковый набор таких операций в виде инструкций ассемблера,
А вот видеокарты (например) или ПЛИС-микросхемы, позволяют конструировать более широкий класс дискретных операций. То есть есть разные устройства которые реализуют готовые дискретные операции, соответственно для этих операций не надо хранить таблицы.
Соответственно любая аналитика здесь должна быть основана на возможностях выбранной аппаратной платформы, ну и задачу (или класс задач) нужно все таки сформулировать с необходимой степенью полноты.
Ну а вы пытаетесь сформулировать задачу совершенно оторванную от реальности, в этом ваша ошибка, мне кажется!

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

девел0пер

21.02.2018

вообще не в тему, уж извините.

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

девел0пер

21.02.2018

всем спасибо, оказалось задача решается проще через обычные "кагбэ проекции": набор выпуклых полигонов как бы разворачивается на плоскость, задача становится 2-мерной (ну на самом деле из 4-мерной в 3-мерную переходит).
да, не так удобно как adjacency, увы, в итоге придётся небольшое API написать на "взятие", зато с shift'ом при вращении (а я SW эмулирую набор HW объектов) - никаких головоломок (ну почти) :)))

Ответить

Ссылка на сообщение

открыть ссылку в новом окне

В социальных сетях

Новая тема

Список тем

Последние темы форумов

Форум Тема (Автор) Последний ответ Ответов

Юридический "Преюдиция" ранее признанных обстоятельств одной из сторон спора - apmmap 06.05.2024 в 12:56:38 9

Разработчики ПО Почему здешний rss тем пустой? - Qavai 05.05.2024 в 14:28:29 1

Подбор персонала Подработка на 6 мая. - Lebron4igg 04.05.2024 в 16:54:59 2

Недвижимость Сдам комнату в квартире в центре Сормова - brodaga74 02.05.2024 в 12:05:45 5

Бухучет и аудит Адрес статистики Нижегородского района - Наталья Витальевна 02.05.2024 в 21:02:55 6

Бизнес форум польза Б24; BPM; ERP, откликнитесь пожалуйста - REPTe 29.04.2024 в 13:45:18 17

Банковский форум Почему ставки по долларовым вкладам увеличились? - Tracker 28.04.2024 в 09:02:55 12

Web-разработчики Нужен сайт визитка - leopink 22.04.2024 в 18:22:53 17

Форум трейдеров Очередное обострение ублюдка - поар принять меры - Юристище 13.04.2024 в 23:30:51 14

Медицина Дюфастон 10мг 112 таблеток продаю - AleXey 84 22.04.2024 в 12:30:26 6

Объявления на НН.РУ - Бизнес

Добавить объявление

Пресс-пакетировщик вертикальный Кубер-4ВА из стали AISI 304

Габарит формируемой кипы, мм 300х600х400 (ВхШхД) Габарит пресса, мм 1940х750х580 (ВхШхГ) Габарит модульной...
Цена: 793 000 руб.

Разгрузчик нерудных материалов ТР-2Д

Продается оборудование (в г. Пенза): Разгрузчик нерудных материалов ТР-2Д с двумя отвальными конвейерами в комплекте с ж/д путем под...
Цена: 6 500 000 руб.

Восстановление отверстий спецтехники

Услуга мобильного наплавочно-расточного комплекса по восстановлению, ремонту отверстий на спецтехнике и промышленном...
Цена: 10 000 руб.

Гидравлика сервис.

Гидравлика сервис ООО на протяжении 13 лет занимается ремонтом гидронасосов, гидромоторов и гидрораспределителей. За время работы наше...

Добавить вакансию Добавить резюме Работа для разработчиков ПО в Нижнем Новгороде

Разработчик .net Profit Search

70000 -
100000 руб.

Неполное среднее образование, стаж работы 3-5 лет, полная занятость

Программист 1С НПП ПРО-М

от 110 000 руб.

Высшее образование, стаж работы 3-5 лет, полная занятость

Программист-разработчик Full-Stack ГК "Kolobox"