Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 9
Случайность также можно использовать для поиска решений неслучайных задач.
У этого есть и более простые случаи. Например, использование метода Монте-Карло при интегрировании или вычислении площади
Если лобовая атака на проблему вряд ли увенчается успехом, можно попробовать зайти с фланга. К примеру, можно показать, что если бы мы рассмотрели все объекты определённого типа, и затем выбрали один из них случайным образом, то существует ненулевой шанс выбрать объект с нужным свойствам. Такой «вероятностный метод» первым применил математик Пал Эрдёш.Честно говоря, я не знаю, где конкретно применил «этот метод» Эрдёш, но выглядит как нечто, весьма косвенно относящееся к случайности. Скорее речь идёт о том, что мы вводим некую конечную меру на множестве всех рассматриваемых объектов, и доказываем, что у подмножества нужных объектов мера будет ненулевой. Мне кажется, это вообще отдельная задача, и никак не может быть проще обычного неконструктивного доказательства существования.
Если бы здесь нашлись люди, способные мне пояснить этот абзац, было бы просто восхитительно.
Ваш подход с мерой действительно прямее, но дело в том, что аппарат теорвера повсеместно освоен и им зачастую сподручней выразить мысль.
На эту тему (в том числе про Эрдёша) есть отличные лекции Райгородского, например.
На эту тему (в том числе про Эрдёша) есть отличные лекции Райгородского, например.
Это просто перебор методом «тыка», но с заумным названием. Если перебором пойти «подряд», то охватить всё пространство состояний нереально по времени, поэтому перебор сокращают до случайных «тыков» в пространство. При этом равномерно распределённые «тыки» дают хорошее покрытие всего пространства и ненулевую вероятность попасть куда надо. Пространство же сужается при помощи ограничений, под которые попадают лишь объекты заданного класса, что опять повышает вероятность правильного «тыка».
Это просто перебор методом «тыка», но с заумным названием.Никуда тыкать не надо — сам факт ненулевой вероятности и является доказательством существования «объекта с нужным свойствам».… можно показать, что если бы мы рассмотрели все объекты определённого типа, и затем выбрали один из них случайным образом, то существует ненулевой шанс выбрать объект с нужным свойствам.
Ненулевая вероятность никому не интересна с момент доказательства существования объекта с заданными свойствами, поэтому нет никакого смысла доказывать эту самую ненулевую вероятность попадания в заведомо существующий объект. А вот обнаружить экземпляр объекта для его изучения — это другая задача, которую метод тыка и решает (с ненулевой вероятностью).
Если предположить, что свойства выбраны произвольно и далее есть желание убедиться в их реальном существовании, то каким образом вероятностность подхода поможет доказать наличие свойств? Свойства либо есть, либо их нет, и вероятность здесь либо 1, либо 0. Но другое дело, когда некую формулу для доказательства легче вывести привычными данному математику средствами, только привычность средств никак не относится к привлечению к решению вопроса вероятностей. Формула через вероятность выражает то же самое, что и возможные альтернативы без вероятностей, как и в случаях с нахождением одних и тех же корней при помощи нескольких разных уравнений, описывающих один и тот же процесс. То есть задача доказательства наличия свойств к вероятности отношения не имеет, а вот нахождение объекта — очень даже имеет. Хотя, что там автор имел в виду — можно долго спорить.
Если предположить, что свойства выбраны произвольно и далее есть желание убедиться в их реальном существовании, то каким образом вероятностность подхода поможет доказать наличие свойств? Свойства либо есть, либо их нет, и вероятность здесь либо 1, либо 0. Но другое дело, когда некую формулу для доказательства легче вывести привычными данному математику средствами, только привычность средств никак не относится к привлечению к решению вопроса вероятностей. Формула через вероятность выражает то же самое, что и возможные альтернативы без вероятностей, как и в случаях с нахождением одних и тех же корней при помощи нескольких разных уравнений, описывающих один и тот же процесс. То есть задача доказательства наличия свойств к вероятности отношения не имеет, а вот нахождение объекта — очень даже имеет. Хотя, что там автор имел в виду — можно долго спорить.
Спасибо Вячеславу, что затронул интересную тему. Очень интересную.
Как-то так получилось, что за последние два года достаточно много времени было посвящено мною именно этой тематике. По собственному опыту могу сказать следующее:
1. Как правило, речь идет об очень большой группе недетерминированных задач, связанных с отбором в огромном пространстве состояния в условиях ограничений. Как вы понимаете, речь идет о задачах из множества NP в различных модификациях.
2. Решение таких задач будет крайне неэффективным, без использования метода случайного отбора при формировании ветви поиска решения.
3. Использование только случайного отбора (и больше ничего), не приведет к эффективному решению задачи. Процент правильных решений будет незначительным, и с увеличением ключевых параметров задачи, доля правильных решений быстро сведется к нулю.
4. Для решения задачи, наряду со случайным (безусловным) отбором, необходимо включить в алгоритм процедуру отбора, основанную на каком-то правиле (условный отбор).
5. Не все модели случайного отбора являются одинаковыми, между ними есть различия.
Как-то так получилось, что за последние два года достаточно много времени было посвящено мною именно этой тематике. По собственному опыту могу сказать следующее:
1. Как правило, речь идет об очень большой группе недетерминированных задач, связанных с отбором в огромном пространстве состояния в условиях ограничений. Как вы понимаете, речь идет о задачах из множества NP в различных модификациях.
2. Решение таких задач будет крайне неэффективным, без использования метода случайного отбора при формировании ветви поиска решения.
3. Использование только случайного отбора (и больше ничего), не приведет к эффективному решению задачи. Процент правильных решений будет незначительным, и с увеличением ключевых параметров задачи, доля правильных решений быстро сведется к нулю.
4. Для решения задачи, наряду со случайным (безусловным) отбором, необходимо включить в алгоритм процедуру отбора, основанную на каком-то правиле (условный отбор).
5. Не все модели случайного отбора являются одинаковыми, между ними есть различия.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как случайность может помочь математикам