Метода - слепой поиск
Cтраница 1
Методы слепого поиска могут направляться целью, направляться данными или носить двунаправленный характер. В случае игры в восемь направляемый целью поиск производится в обратном направлении от желаемого конечного состояния к начальным условиям путем применения обратных операторов. Направляемый данными поиск, который начинается от данных начальных условий, называют также прямым поиском. Двунаправленный поиск состоит в поиске, ведущемся с обоих концов пространства, пока не произойдет встреча где-то посередине. [1]
К методам слепого поиска относятся сканирование и чисто случайный поиск. [2]
Таким образом, в методе слепого поиска число требуемых вычислений значений целевой функции весьма резко увеличивается с возрастанием размерности решаемой задачи. Аналогичные проблемы уже встречались при рассмотрении поиска оптимума методом сканирования, где для устранения трудностей с размерностью иногда может использоваться поиск с переменным шагом сканирования. Точно такой же прием можно применить и в методе слепого поиска, если после выполнения определенной серии проб дальнейший поиск ( уточнение) производить в некоторой суженной области, охватывающей найденную в предыдущей серии точку наименьшего ( наибольшего) значения функции цели. При этом вероятность попадания в заданную Д - окрестность оптимума возрастает, за счет чего можно существенно сократить общий объем вычислений. [3]
F ( x)) в случае использования ПЛП-поиска при конечном числе N экспериментов незначительно отличаются от наилучших результатов в методе слепого поиска, а в ряде случаев и сопоставимы между собой. [4]
 |
Представление игры в восемь в пространстве состояний. Каждая конфигурация фишек является здесь состоянием, а операторы, применяемые к состояниям в этом пространстве, обеспечивают движение к цели. [5] |
В методе слепого поиска систематически обследуются все дуги графа. [6]
Всегда присутствуют практические ограничения для времени и памяти, отпущенных для осуществления поиска. Хотя в принципе методы слепого поиска находят решение поисковых задач, на практике для больших задач они неприемлемы, поскольку слишком много вершин будет пройдено, прежде чем обнаружится решение. Здесь проявляется феномен комбинаторного взрыва, который возникает, когда у системы решения задачи отсутствует необходимая информация, направляющая сам процесс вывода. [7]
 |
Процесс поиска экстремума функции в безынерционном объекте. [8] |
С этой точки зрения метод слепого поиска требует значительной затраты времени, и поэтому применение его сравнительно ограничено. [9]
Методы поиска в глубину и ширину назьь вают слепым поиском, поскольку в этих методах порядок раскрытия вершин предопределен и никак - не зависит от расположения цели. При увеличении пространства поиска методы слепого поиска требуют чрезмерных затрат времени и ( или) памяти. Стремление сократить время поиска привело к созданию эвристических методов поиска, т.е. методов, использующих некоторую информацию о проблемной области для рассмотрения не всего пространства поиска, а таких путей в нем, которые с наибольшей вероятностью приводят к цели. Один способ сокращения перебора состоит в выборе более информированного оператора, который не строит так много вершин, не относящихся к делу. Другой способ состоит в использовании эвристической информации для определения на каждом шаге дальнейшего направления перебора. Для этого необходимо ввести меру перспективности вершины в виде некоторой оценочной функции. В некоторых случаях удается ввести такую оценочную функцию, что она, сокращая перебор, не теряет свойства полноты. Чаще же используемые эвристики, сильно сокращая перебор, влекут за собой потерю свойства полноты. Как правило, оценочные функции пытаются количественно оценить расстояние от текущей вершины до конечной. Из двух вершин при одинаковой глубине перспективней та, от которой меньше расстояние до цели. Для многих приложений, в частости для экспертных систем, применение количественных оценок не позволяет эффективно направлять процесс поиска. [10]
Такая задача оптимизации решается с помощью методов нелинейного математического программирования. Очень часто методы определения экстремума нелинейной функции при наличии ограничений на оптимизируемые параметры делят по признаку организации процесса поиска на методы слепого поиска и методы направленного поиска. К методам направленного поиска относятся градиентный метод, метод наискорейшего спуска, метод покоординатного спуска и другие. [11]
Таким образом, в методе слепого поиска число требуемых вычислений значений целевой функции весьма резко увеличивается с возрастанием размерности решаемой задачи. Аналогичные проблемы уже встречались при рассмотрении поиска оптимума методом сканирования, где для устранения трудностей с размерностью иногда может использоваться поиск с переменным шагом сканирования. Точно такой же прием можно применить и в методе слепого поиска, если после выполнения определенной серии проб дальнейший поиск ( уточнение) производить в некоторой суженной области, охватывающей найденную в предыдущей серии точку наименьшего ( наибольшего) значения функции цели. При этом вероятность попадания в заданную Д - окрестность оптимума возрастает, за счет чего можно существенно сократить общий объем вычислений. [12]
С принципиальной точки зрения на этот вопрос существует однозначный положительный ответ. Однако, учитывая конечное значение числа проводимых машинных экспериментов на ЭВМ ( хотя и достаточно большое), нужно было выяснить, не потребуется ли в задачах с функциональными ограничениями на параметры при использовании метода ПЛП-поиска столь большого числа N экспериментов, что это окажется неэффективным по сравнению с методами прямого перебора, например методами слепого поиска. [13]
В машинах будущего решение задач может прпзводпться не только по заданному методу. Они могут сами вырабатывать, изобретать методы решения задач. Поиск методов решения задач является важным примером сложного вида поиска. Пробуя различные методы решения, машина не должна обязательно действовать по методу слепого поиска. [14]
Страницы: 1