Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Диффузия матриц

Автор: ArNic 23.3.2010, 04:54

Дано: Матрица любого размера со случайными значениями.
Найти: Алгоритм диффузии (Через энное число итераций все значения элементов матрицы должны быть равны.)
Текущее решение:
        За итерацию половина значения каждого элемента (Э) распределяется между соседними элементами (СЭ).
        Для "Э": [значение "Э"]/2
        Для "СЭ": [значение "СЭ"]+([значение "Э"]/(2*[количество "CЭ"]))
        Результат расположен на: http://test.sallfy.ru/diffusion.php (вес страницы 232,8 Кб )
        Т.к. я решил не определять количество соседних элементов. Диффузия на ней работает как если бы это был шар.

Задачка сложная.
Половина или там четверть отдается - неважно. Это всего лишь коэффициент, переменная. Всё равно не получается сделать нормально диффузию. Возникает аномалия (назовем так - логическую ошибку smile

)
У кого какие идеи?

P.S.
Поиск в интернете ...
http://www.google.com/search?hl=ru&q=Диффузия+матриц
http://www.google.com/search?hl=ru&q=матрицы+равномерное+распределение
... ничего не дал

Автор: MaxPayneC 23.3.2010, 12:45

А какие требования к результату, помимо равенства значений после работы алгоритма? А то можно и среднее арифметическое посчитать )

Автор: ArNic 23.3.2010, 14:28

Требование такое, чтобы за одну итерацию должны быть обработаны все элементы, но каждый элемент был раздающим только раз за итерацию
Среднее арифметическое - можно для проверки результата использовать.

Добавлено через 1 минуту и 13 секунд
Тем более что тут не мгновенная диффузиия, а итеративная.

Добавлено через 1 минуту и 49 секунд
Извиняюсь, что я придумываю термины типа итеративная диффузия, но это хоть как то передает смыл того что должно быть

Автор: nworm 23.3.2010, 16:40

ограничения надо четко прописать

непонятно, например, почему нельзя среднее арифметическое использовать

Автор: ArNic 23.3.2010, 18:00

Цитата

непонятно, например, почему нельзя среднее арифметическое использовать

В итоге и придет к среднему арифметическому - но это уже в самом конце.

Код


Органичения:
         Обработка элементов матрицы последовательная
         За одну итерацию обработка элемента, как родителя, должна быть произведена только 1 раз
         Элемент не может знать значение далее чем на один элемент в любом направлении.

Например есть квадратная матрица 4х4:

Код


20    1    1    1
1    1    1    1
1    1    1    1
1    1    1    1

Далее цифры должны плавно выравниваться, пока не распределяться по всей площади и не станут равными 2.1875
То есть при энном количестве итерации матрица придет к виду:

Код


2.1875    2.1875    2.1875    2.1875
2.1875    2.1875    2.1875    2.1875
2.1875    2.1875    2.1875    2.1875
2.1875    2.1875    2.1875    2.1875

Модель также должна работать в случае множества неравных значений – напрмиер:

Код


20    1    1    -1
1    1    1    1
1    1    15    1
1    1    1    1

Код


2.9375    2.9375    2.9375    2.9375
2.9375    2.9375    2.9375    2.9375
2.9375    2.9375    2.9375    2.9375
2.9375    2.9375    2.9375    2.9375

Т.е. в данном случае итерация на манер времени диффузии и сразу выравнивать нельзя.
Ну и естественно по ссылке можно увидеть что получилось при среднем арифметическом, применяемом к каждому элементу.

Автор: ArNic 23.3.2010, 20:58

Я сейчас сделал среднее арифметическое для 9 элементов матрицы распределённое равномерно. Что в итоге получается можно глянуть. http://test.sallfy.ru/diffusion2.php

Автор: ArNic 24.3.2010, 18:55

Равномерная диффузия не получилась даже при повторном прогоне элементов рекурсивно (хотя это 2 такта)

Автор: nworm 30.3.2010, 22:30

Не знаю как её решать, в общем ):

Отмечу несколько моментов
1. точное среднее арифметическое может не получиться никогда.
Например,

Код


1 0 0
0 0 0
0 0 0

среднее арифметическое 1/9

а получается при таком подходе всегда число, не делящееся на 3.

Можно искать только приближение (хотя может так и надо?).

2. для всех методов наверняка могут быть специальные расклады, на которых метод будет только ухудшать текущее состояние.

3. даже случайный метод (берём рандомом две соседние цифры и усредняем) наверное будет при большом числе усреднений давать хороший результат.

Автор: nworm 31.3.2010, 13:05

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

Но, похоже, можно действовать только с элементами или нет?

Автор: Domydorogi 7.4.2010, 00:40

Пусть Y[i,j] элемент матрицы после итерации; X[m, n] элемент матрицы до итерации

Правильный алгоритм будет такой .

Y[i,j] = X[i,j]/2 + (сумма по всем парам m, n не равным i, j ) X[mn]/(2(N-1), где N - полное число элементов матрицы. Сканирование по всем i,j, и переход к следующей итерации. Если совет не устарел, то можешь не сомневаться, что сходится ... проверил. Если нет, то ищи ошибку в коде.

Автор: ArNic 18.8.2010, 02:19

Спасибо, попробую