2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 плоскость и матрицы (задача алгебраического программирования
Сообщение03.10.2007, 16:09 
Всем привет!
У меня мимоходом возникла одна задачка. Никак не могу в ней разобраться. Может, кто что подскажет? Может, кто-то уже такое делал?

Вот предположим, что на плоскости у нас отмечено некоторое конечное количество точек. Эти точки мы можем перенумеровать. Теперь фиксируем некоторое $R$ и строим матрицу $A$: если расстояние между точками $i, j$ больше $R$, то $a_{ij}=0$, иначе $a_{ij}=1$.

Итак, по каждому набору точек и фиксированному "радиусу" мы можем построить матрицу.
Вопрос: для каких матриц возможна обратная процедура?

Это возможно отнють не для всех матриц.
1) если в фиксированном ряду не менее 7 единиц (включая диагональ) (пусть это в столбиках с1, с2, с3, с4, с5, с6 и тот, который пересекает ряд на диагонали), то существуют i и j (от 1 до 6 каждый), такие, что Асiсj = 1.

Заранее благодарна за любые соображения на этот счет...

 
 
 
 
Сообщение03.10.2007, 18:22 
Задача не простая и вряд ли можно дать необходимое и достаточное условие. Для небольших n (до 10) можно анализировать все варианты. Для больших n можно только разные необходимые условия составить. Очевидное необходимое условие - матрица симметричная и на диагонали 1. Если i,j,k попарно отдалены (т.е. все соответствующие элементы матриц равны 0), то все элементы n,m принадлежащие окружностям в точках i,j,k (т.е. a(i,n)=a(i,m)=a(j,n)=a(j,m)=a(k,m)=a(k,n)=1), то a(n,m)=1.

 
 
 
 General idea
Сообщение04.10.2007, 13:29 
Аватара пользователя
Представляем точки в виде (x_1,y_1), ..., (x_n,y_n). Нам нужно проверить, есть ли набор (x_1,y_1,...,x_n,y_n), удовлетворяющий системе неравенств типа
$(x_i-x_j)^2+(y_i-y_j)^2>1$ или $(x_i-x_j)^2+(y_i-y_j)^2 \le 1$.
Замена R на 1 мало что меняет. :)

Это задача алгебраического программирования - обобщение задачи линейного программирования. Плохо, что есть строгие неравенства - придётся повозиться с окрестностями точек. Но это потом.
Сначала заменяем некоторое количество неравенств на равенства, чтобы количество решений было конечным, но при этом любая подвыборка равенств ещё не давала конечности - надо будет перебрать все такие выборки. Для каждой выборки проверяем, согласуется ли хотя-бы одно её решение с оставшимися неравенствами. Если да - проверяем, можно ли "пошевелить" решение, чтобы строгие неравенства, заменённые на равенства, снова стали строгими.
Системы алгебраических уравнений можно анализировать с помощью алгоритма Евклида (подробнее - в некоторых учебниках по алгебраической геометрии). Чтобы проверить, можно ли сделать неравенство строгим, нужно использовать производные в точках решений.

В общем, принципиальная алгоритмичность есть, но для реальных вычислений - легче повесицца. :x

А для прямой решать не пробовала?

 
 
 
 
Сообщение04.10.2007, 14:36 
Саша, огромное спасибо за такую идею!
Я что-то зациклилась на поиске допустимых и недопустимых подграфов. на самом деле подход со стороны линейного программирования естественный и надежнее :)
Супер!

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group