Когда я был близок к завершению моей первой недели в алгоритме 1 Принстонского университета на Coursera, на моем экране появилось имя. Это было «Моделирование Монте-Карло». Я нажал на паузу и подумал, что, черт возьми, за ерунду !. Да, это была та же самая реакция, когда я увидел это имя.
Будучи студентом факультета менеджмента, у меня были надежды только тогда, когда я начал свой путь к изучению искусственного интеллекта (который я успешно завершил, и на сегодняшний день у меня есть несколько проектов, статей на мое имя). Но опять же, у меня возникла эта новая страсть к изучению алгоритмов и данных. -структура.
Хорошо! Хватит обо мне, приступим к кодированию !!! И еще кое-что. Я посчитал, что у вас есть предварительные знания по следующим темам:
- Динамическое подключение
- График
- Союз-Найти (Быстрое объединение, Быстрый поиск)
- Взвешенный поиск союза
- Сжатие пути
Если нет, то вам, вероятно, стоит сначала посетить их. Как обычно, исходный код вы можете найти в моем репозитории здесь. Кроме того, по этой ссылке Принстонский университет предоставляет все необходимые зависимости или структуру каталогов.
Чтобы упростить задачу, я разделю часть объяснения в соответствии с двумя разными постановками задачи:
- Перколяция
- Моделирование Монте-Карло
Перколяция. Общее значение этого слова - это движение воды через поры на любой поверхности. Так с чем мы пытаемся согласиться? Мотивация за этим состоит в том, чтобы создать матрицу размером N * N, представляющую поверхность, и открывать случайные пятна на поверхности до тех пор, пока поверхность не протечет. Все еще не понятно?
Не волнуйся, я тебя понял. Итак, что мы в основном делаем, мы создаем логический массив размером N * N или, другими словами, с количеством N строк и количеством столбцов N, каждая ячейка представляет собой пору на поверхности. Итак, что нам нужно определить, так это порог перколяции или какое среднее количество пор требуется на поверхности, чтобы вода просачивалась сверху вниз.
Как и в показанном выше GIF, он представляет собой поверхность размером 50 на 50. Черные квадраты - это заблокированные поры, белые - открытые поры, а квадраты синего цвета представляют поток воды.
Вы спросите, а зачем нам это ?! Воспринимайте это так, как будто вы проводите эксперимент, в котором вы смешиваете разные типы металлов вместе, чтобы создать новый сплав, и качество этого сплава проверяется путем пропускания через него воды. Если бы вы выполняли это физически, это заняло бы миллионы человеко-часов. Чтобы сэкономить время, вы запускаете его на компьютере и смотрите, какие комбинации дают наилучшие результаты. Теперь, когда дан ответ на вопрос «Почему», давайте начнем с кодирования. В отличие от других моих статей, реализация этой задачи выполняется с использованием Java, поэтому я считаю, что вы тоже немного знакомы с Java.
КОД
В соответствии с требованиями курса мы создаем класс под названием Percolation со следующими свойствами:
private boolean[] grid;
private final WeightedQuickUnionUF gridMap;
private final int n;
private int openCell;
private final int top ;
private final int bottom;
сетка представляет собой часть поверхности, как я объяснил ранее. Сетка заполняется либо истинным, либо ложным. Истинное бытие открыто, а Ложное - заблокировано.
gridMap представляет собой взвешенную структуру быстрого объединения, о которой, как мне кажется, вы уже знакомы. Если нет, рассмотрите это как механизм поиска пути среди сетки, чтобы мы могли найти путь между любыми заданными двумя точками внутри сетки.
openCell эта переменная будет использоваться для подсчета количества открытых ячеек или открытых пор на поверхности, когда мы их случайным образом открываем.
top и bottom - это дополнительные добавленные структуры, чтобы мы могли сопоставить, есть ли между верхом и низом открытый путь. Это помогает нам сделать вывод, что поверхность протекает, если найден какой-либо путь. Здесь мы инициализируем их (верхний и нижний) как начальный и конечный индексы. Итак, при инициализации пояса и карты сетки мы устанавливаем их размер как N * N + 2 для добавления верха и низа.
public Percolation(int n) {
if (n <= 0) throw new IllegalArgumentException();
gridMap = new WeightedQuickUnionUF(n * n + 2);
grid = new boolean[n*n+2];
this.n = n;
openCell = 0;
top = 0;
bottom = n * n + 1;
}
Как правило, мы хотим, чтобы наше N было больше 0, так как никакая структура не имеет отрицательной размерности. Как упоминалось ранее, мы инициализируем размер сетки и карты сетки как N * N + 2. Верх и Низ инициализируются как начальный и конечный индексы.
private void checkRowsColumn(int row, int col) {
if (row < 1 || row > this.n || col < 1 || col > this.n)
throw new IllegalArgumentException();
}
Функция checkRowsColumn просто выдает исключение недопустимого аргумента всякий раз, когда строки и столбцы меньше 1 или больше N, если не проверено, позже в программе будет выдано исключение индекса массива за пределами привязки. Чтобы этого не произошло, у нас есть слой ограничений.
private int indexOf(int row , int col){
checkRowsColumn(row,col);
return (row - 1) * n + (col -1);
}
В методе indexOf мы берем строку и столбец и возвращаем индекс этой конкретной точки пересечения. Например, если row = 2 и col = 2, индекс для этой ячейки будет 3, потому что индекс массива начинается с 0 (исключая логику для Top и Bottom).
public boolean isOpen(int row , int col) {
checkRowsColumn(row , col);
return grid[indexOf(row ,col)];
}
Функция isOpen не требует пояснений. Он проверяет, является ли данная ячейка истинной или ложной. Истинное значение означает, что вода может проходить, а Ложь означает, что она сопротивляется воде.
public boolean isFull(int row , int col) {
checkRowsColumn(row, col);
if(!isOpen(row,col)) return false;
return gridMap.find(indexOf(row,col)) == gridMap.find(top);
}
Аналогичным образом isFull проверяет, есть ли у точки или ячейки путь к вершине, поскольку вершина является источником воды, если существует какой-либо путь между верхней и нижней ячейкой, вода течет через этот путь.
public int numberOfOpenSites(){
return this.openCell;
}
Эта функция просто возвращает общее количество открытых пор или общее количество ячеек, содержащих истинные значения.
public boolean percolates(){
return gridMap.find(top) == gridMap.find(bottom);
}
Считается, что поверхность просачивается, если существует какой-либо путь между верхом и низом.
public void open(int row, int col)
{
........................
}
Так что самая длинная и сложная логика скрывается в функции open. Изначально поверхность не просачивается. Мы случайным образом открываем пору или инициализируем конкретную ячейку, чтобы она была истинной, и проверяем, существует ли путь между верхом и низом. В этой функции мы берем два параметра row и col, которые определяют открываемую ячейку. Случайное открытие рассматривается далее в реализации Монте-Карло. А пока мы рассмотрим логику просачивания.
checkRowsColumn(row,col); int current_cell_index = indexOf(row, col);
Первоначально мы проверяем, находится ли данная строка или столбец в пределах диапазона. Если он проходит диапазон, мы определяем индекс ячейки, которую нужно открыть. Как упоминалось ранее, сетка представляет собой логический массив, поэтому, если значение в этом индексе истинно, оно считается открытым. Поэтому, если значение в ячейке ложно, мы пытаемся открыть эту ячейку. Все не так просто . Алгоритм не работает, если мы заменим только ложное значение на истинное. После замены false на true возникает много условий публикации.
grid[current_cell_index] = true; this.openCell ++ ;
После замены значения false на true мы увеличиваем количество открытых ячеек на единицу. Основная мотивация выяснить, просачивается ли поверхность, - это найти путь между верхом и низом. Поэтому, когда мы открываем ячейку на поверхности, нам нужно проверить различные условия. Нам нужно проверить, открыта ли соседняя ячейка. Если соседняя ячейка открыта, значит, путь существует. Затем мы наносим на карту этот путь до тех пор, пока ему некуда идти или пока он не приведет к финалу.
if(row == 1) gridMap.union(current_cell_index,top);
Первое условие, которое мы проверяем, - это то, что индекс ячейки находится в первой строке. Поскольку каждая ячейка наверху связана с корнем в взвешенном быстром поиске с помощью сжатия пути, или, другими словами, в верхней части поверхности есть вода, поэтому, если есть какое-либо отверстие, вода течет через это отверстие. Чтобы справиться с этой конкретной ситуацией, мы создаем путь между вершиной и ячейкой, которую мы недавно открыли, которая имитирует поток воды.
Чтобы вкратце рассказать, что такое сжатие путей, представьте, что это метод воссоздания заданной древовидной структуры, в которой узлы расположены таким образом, что для достижения листового узла требуется минимальное количество ребер.
if(row == this.n) gridMap.union(current_cell_index,bottom);
Возвращаясь ко второму шагу, мы здесь проверяем, находится ли недавно открытая ячейка в нижнем ряду или нет. Если это так, мы соединяем эту открытую ячейку с нижней ячейкой. Считайте нижнюю ячейку сосудом, используемым для сбора воды, если поверхность протекает.
Вверху
if(row > 1 && isOpen(row - 1 ,col)) {
assert(current_cell_index > n);
gridMap.union(current_cell_index,current_cell_index - n);
}
А что, если недавно открытая ячейка не находится ни вверху, ни внизу. Здесь мы проверяем соседние ячейки. Поскольку недавно открытая ячейка могла иметь открытую ячейку сверху, снизу, справа, слева. Проверяем все условия. В приведенном выше коде он проверяет, открыта ли ячейка сверху, т.е. (строка - 1 строка перед текущей). Если условие совпадает, мы создаем связь между ячейкой над ним. Итак, если на его вершине есть вода, она течет сквозь нее.
Ниже
if (row < this.n && isOpen(row + 1 , col)) {
assert(current_cell_index + n < n * n);
gridMap.union(current_cell_index , current_cell_index + n);
}
Аналогично проверяем ячейку на ее дне. Если ячейка под ней открыта, мы создаем объединение между ними, что означает создание пути между вновь открытой ячейкой и уже открытой ячейкой под ней.
Слева
if(col > 1 && isOpen(row, col - 1)) {
gridMap.union(current_cell_index,current_cell_index- 1);
}
Вправо
if(col < this.n && isOpen(row, col + 1)) { gridMap.union(current_cell_index,current_cell_index + 1); }
Таким же образом мы проверяем потенциальный путь между предыдущей и исходящей ячейкой. Просто, если ячейка справа или слева открыта, мы создаем путь между ними.
Итак, теперь мы успешно создали модель, представляющую поверхность, которая может определить, протекает ли поверхность или нет. Как видите, мы не запускаем эту модель отдельно. Чтобы визуализировать это, Princeton включил файл PercolationVisualization.java.
Моделирование Монте-Карло
Наша модель перколяции - это просто абстрактная структура, представляющая поверхность. Точный анализ события (просачивания) осуществляется путем многократного моделирования возникновения утечки. Теперь приступим к моделированию.
Первый вопрос, который вы можете задать, - зачем нам нужен этот анализ. Можно сказать, что у нас уже есть модель, мы просто запускаем ее и проверяем, протекает ли поверхность или нет!
Вы не ошиблись, но и не совсем правы. Поскольку мы открываем ячейку равномерно и наугад, возникновение утечки может быть разным. Поэтому нам нужен конкретный анализ средней доходности (в данном случае обнаружение утечки), стандартного отклонения, самого высокого и самого низкого уровней достоверности.
Итак, метод Монте-Карло - это математический метод оценки возможного исхода неопределенного события. Доля ячейки, которая открывается при просачивании системы, дает оценку порога просачивания. Итак, наша задача - посмотреть, сколько открытых ячеек требуется, чтобы поверхность просачивалась.
Все математические уравнения приведены Принстоном на этой странице. Как они упоминают, нам нужно найти среднее значение, стандартное отклонение, нижнюю конечную точку 95% доверительного интервала и, наконец, верхнюю конечную точку 95% доверительного интервала. Для этого мы инициализируем 4 переменные, а именно:
private final double mean ;
private final double sd;
private final double highConfidence;
private final double lowConfidence;
Основная логика этого моделирования заключается в том, что мы инициализируем поверхность размером N, проверяем, просачивается ли она относительно случайно открытых ячеек, и повторяем этот процесс заданное количество раз.
if(n <= 0 || trials <= 0) throw new IllegalArgumentException();
Сначала мы проверяем, больше ли заданный размер (то есть n) и количество попыток (то есть количество повторений) 0. Если заданные параметры действительны, мы создаем 3 переменные.
- Массив для хранения результата, а именно результатов
double[] results = new double[trials];
2. Целочисленная переменная для хранения случайно сгенерированного номера строки.
int testY;
3. Целочисленная переменная для хранения случайно сгенерированного номера столбца.
int testX;
После инициализации требуемой переменной мы перебираем время следа.
for(int i = 0 ; i < trials;i ++) { ---------- }
Инициализация модели перколяции, которую мы построили ранее, размером n.
Percolation per = new Percolation(n);
Теперь самое интересное
while(!per.percolates())
{
testX = (int)((StdRandom.uniform() * n) + 1);
testY = (int)((StdRandom.uniform() * n) + 1);
if(!per.isOpen(testY,testX))
{
per.open(testX,testY);
}
}
results[i] = (double)(per.numberOfOpenSites()) / (n * n); }
Мы перебираем точку до тех пор, пока поверхность не просочится. Изначально система не просачивается, так как все ячейки закрыты. Теперь мы генерируем случайную строку и столбец равномерно наугад. После того, как у нас есть новый набор строк и столбцов, мы открываем эту конкретную ячейку, используя функцию open, которую мы ранее создали в нашей модели перколяции. После открытия новой ячейки мы снова проверяем, просачивается ли поверхность или модель. Этот процесс продолжается до тех пор, пока система не просочится. Если система просачивается, это выходит из цикла while, и количество открытых сайтов или ячеек делится на их общий размер, то есть (n * n), что дает нам долю или оценку. Затем мы сохраняем эту оценку в массиве и повторяем этот процесс несколько раз.
mean = StdStats.mean(results); sd = StdStats.stddev(results); lowConfidence = mean - (1.96 * sd)/ Math.sqrt(trials); highConfidence = mean + (1.96 * sd)/ Math.sqrt(trials);
После того, как моделирование будет выполнено, мы рассчитаем среднее значение с помощью библиотеки, предоставленной Princeton, то есть StdStats.mean ().
Точно так же мы вычисляем стандартное отклонение с помощью StdStats.stddev () для полученных нами результатов.
Чтобы вычислить верхнюю и нижнюю конечные точки 95% доверительного интервала, мы используем формулу, предоставленную в руководстве Princeton, и сохраняем их соответственно.
Теперь, чтобы запустить моделирование методом Монте-Карло, все, что нам нужно сделать, это инициализировать объект PercolationStasts, и остальные будут обрабатываться автоматически.
PercolationStats s = new PercolationStats(50,10000);
System.out.println("Mean:" + s.mean());
System.out.println("Standard Deviation:"+ s.stddev());
System.out.println("High Confidence" + s.confidenceHi());
System.out.println("Low Confidence" + s.confidenceLo());
Здесь мы проверяем поверхность размером 50 за 10000 раз. Результат выглядит примерно так
