|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
17.05.2011, 22:56 | #1 |
Новичок
Джуниор
Регистрация: 17.05.2011
Сообщений: 2
|
Создание дважды стохастической матрицы
Думаю все знают что это такое. Это матрица, сумма значений элементов по строкам и столбцам которой равна 1.
Вот я решил написать некий генератор таких матриц, вот пока без идей Подкиньте кто нибудь мыслишек, буду очень благодарен. |
18.05.2011, 08:26 | #2 |
Software Developer
Участник клуба
Регистрация: 01.03.2011
Сообщений: 1,098
|
Хм...
Ну, как начальный вариант, разве что. Причем для квадратной матрицы. Кстати, я не совсем уверен, может ли дважды стохастическая матрица быть _не_квадратной... Так вот. В начале "засеваем" всю матрицу одинаковыми значениями 1/n (n - размерность матрицы). Затем выбираем случайный элемент Pij и изменяем его на некоторую случайную величину, например, (0 < Δ < 1/2n). Соответственно, меняем один случайный элемент из этого же столбца и один случайный элемент из этой же строки. То есть, если к элементу Pij мы прибавили Δ, то из случайных элементов в строке и столбце мы эту Δ вычитаем. И наоборот. Затем делаешь коррекцию для элемента, находящегося на пересечении строки и столбца этих двух случайно выбранных элементов. То есть, по идее, ты меняешь четыре элемента, образующие прямоугольник внутри матрицы. При этом, если я не ошибаюсь, матрица должна остаться дважды стохастической В общем -- муторное дело получается -) Этот пункт повторить некоторое, сравнительно большое количество раз. Можно просто пройтись циклом по всем элементам по очереди, изменяя их на случайную Δ и коррегировать матрицу указанным способом. Так, наверное, будет лучше. Или вообще -- совместить оба способа -) Сначала циклом, потом случайно. А вообще, задача интересная -) Если будут более рациональные идеи -- отпишись.
Болтовня ничего не стоит. Покажите мне код. (c) Linus Torvalds
Помог ответ? -- Поставьте отзыв. Выражения особой благодарности в рублевом эквиваленте отправлять сюда --> R269634919062 Последний раз редактировалось Mandrivnyk; 18.05.2011 в 10:10. |
18.05.2011, 12:17 | #3 |
Новичок
Джуниор
Регистрация: 17.05.2011
Сообщений: 2
|
Делюсь мыслями:
Сначала я решил попробовать генерировать числа, в сумме дающие скажем 100 и делать матрицу из них(потом просто нормировать их), но этот вариант провалился, т.к. задача свелась к проблеме перечисления латинских квадратов, которая пока что насколько я знаю является нерешенной. С дважды стохастичностью все оказалось проще. Известны следующие факты: -дважды стохастическая матрица квадратная; -произведение дважды стохастических матриц есть дважды стохастическая матрица; -справедлива теорема Биркгофа-фон Неймана(точнее следствие из нее): матрица М является дважды стохастической тогда и только тогда когда она представляется в виде суммы матриц перестановок умноженных на коэффициенты c, в сумме дающие единицу. Отсюда следует следующий алгоритм: 1)сгенерировать случайные подстановки(это не сложно, если надо могу выложить код функции, делающей это); 2)поставить в соответствие сгенерированным подстановком матрицы(матрица подстановок-матрица в каждой строке и столбце которой стоит ровно одна единица, а остальные нули, причем единицы соответствуют переходам в подстановке); 3)сгенерировать коэффициенты, т.е. числа, в сумме дающие 1, и каждое умножить на одну из матриц; 4)просуммировать полученные матрицы и получим искомую дважды стохастическую. Алгоритм собственно такой, может это поможет, если у кого нибудь возникнет потребность в чем то подобном. К сожалению сейчас пока нет времени написать программу и выложить код, но возможно через пару недель сяду напишу. |
18.05.2011, 14:09 | #4 |
Software Developer
Участник клуба
Регистрация: 01.03.2011
Сообщений: 1,098
|
Реализовал свой алгоритм.
Вроде, работает -) Код:
Болтовня ничего не стоит. Покажите мне код. (c) Linus Torvalds
Помог ответ? -- Поставьте отзыв. Выражения особой благодарности в рублевом эквиваленте отправлять сюда --> R269634919062 |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Как использовать SimpleDataSet дважды... | Kudryavtsev | Общие вопросы Delphi | 3 | 04.05.2011 08:58 |
Создание матрицы | dukesoteg | Помощь студентам | 10 | 12.06.2010 18:19 |
Дважды два. | jojahti | Свободное общение | 68 | 29.01.2010 10:53 |
Почему выполняется дважды? | MAKEDON | Помощь студентам | 1 | 17.05.2009 15:06 |
Как програмно дважды кликнуть в RichEdit? | apromix | Общие вопросы Delphi | 10 | 23.05.2008 17:09 |