Search
Write a publication
Pull to refresh

Comments 9

Случайность также можно использовать для поиска решений неслучайных задач.

У этого есть и более простые случаи. Например, использование метода Монте-Карло при интегрировании или вычислении площади
Если лобовая атака на проблему вряд ли увенчается успехом, можно попробовать зайти с фланга. К примеру, можно показать, что если бы мы рассмотрели все объекты определённого типа, и затем выбрали один из них случайным образом, то существует ненулевой шанс выбрать объект с нужным свойствам. Такой «вероятностный метод» первым применил математик Пал Эрдёш.
Честно говоря, я не знаю, где конкретно применил «этот метод» Эрдёш, но выглядит как нечто, весьма косвенно относящееся к случайности. Скорее речь идёт о том, что мы вводим некую конечную меру на множестве всех рассматриваемых объектов, и доказываем, что у подмножества нужных объектов мера будет ненулевой. Мне кажется, это вообще отдельная задача, и никак не может быть проще обычного неконструктивного доказательства существования.

Если бы здесь нашлись люди, способные мне пояснить этот абзац, было бы просто восхитительно.
Ваш подход с мерой действительно прямее, но дело в том, что аппарат теорвера повсеместно освоен и им зачастую сподручней выразить мысль.
На эту тему (в том числе про Эрдёша) есть отличные лекции Райгородского, например.
Это просто перебор методом «тыка», но с заумным названием. Если перебором пойти «подряд», то охватить всё пространство состояний нереально по времени, поэтому перебор сокращают до случайных «тыков» в пространство. При этом равномерно распределённые «тыки» дают хорошее покрытие всего пространства и ненулевую вероятность попасть куда надо. Пространство же сужается при помощи ограничений, под которые попадают лишь объекты заданного класса, что опять повышает вероятность правильного «тыка».
Это просто перебор методом «тыка», но с заумным названием.
… можно показать, что если бы мы рассмотрели все объекты определённого типа, и затем выбрали один из них случайным образом, то существует ненулевой шанс выбрать объект с нужным свойствам.
Никуда тыкать не надо — сам факт ненулевой вероятности и является доказательством существования «объекта с нужным свойствам».
Ненулевая вероятность никому не интересна с момент доказательства существования объекта с заданными свойствами, поэтому нет никакого смысла доказывать эту самую ненулевую вероятность попадания в заведомо существующий объект. А вот обнаружить экземпляр объекта для его изучения — это другая задача, которую метод тыка и решает (с ненулевой вероятностью).

Если предположить, что свойства выбраны произвольно и далее есть желание убедиться в их реальном существовании, то каким образом вероятностность подхода поможет доказать наличие свойств? Свойства либо есть, либо их нет, и вероятность здесь либо 1, либо 0. Но другое дело, когда некую формулу для доказательства легче вывести привычными данному математику средствами, только привычность средств никак не относится к привлечению к решению вопроса вероятностей. Формула через вероятность выражает то же самое, что и возможные альтернативы без вероятностей, как и в случаях с нахождением одних и тех же корней при помощи нескольких разных уравнений, описывающих один и тот же процесс. То есть задача доказательства наличия свойств к вероятности отношения не имеет, а вот нахождение объекта — очень даже имеет. Хотя, что там автор имел в виду — можно долго спорить.
UFO landed and left these words here
UFO landed and left these words here
Спасибо Вячеславу, что затронул интересную тему. Очень интересную.

Как-то так получилось, что за последние два года достаточно много времени было посвящено мною именно этой тематике. По собственному опыту могу сказать следующее:

1. Как правило, речь идет об очень большой группе недетерминированных задач, связанных с отбором в огромном пространстве состояния в условиях ограничений. Как вы понимаете, речь идет о задачах из множества NP в различных модификациях.

2. Решение таких задач будет крайне неэффективным, без использования метода случайного отбора при формировании ветви поиска решения.

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

4. Для решения задачи, наряду со случайным (безусловным) отбором, необходимо включить в алгоритм процедуру отбора, основанную на каком-то правиле (условный отбор).

5. Не все модели случайного отбора являются одинаковыми, между ними есть различия.
Sign up to leave a comment.

Articles