Применение - эвристика
Cтраница 2
На этом мы заканчиваем обзор попыток запрограммировать игру в шахматы для вычислительной машины. В изложенных работах отчетливо видно стремление к созданию все более сложных программ и применению эвристик, обладающих большей избирательностью. Развитие идет также в направлении использования принципов игры, подобных тем, которыми пользуются шахматисты. Отчасти эта тенденция объясняется, по крайней мере в нашем случае, желанием моделировать мыслительный процесс. Однако еще в большей степени она отражает ограничения, накладываемые самой задачей на любую систему обработки информации, которая призвана ее реализовать. Мы убеждены, что любая система переработки информации ( человек, вычислительная машина или любая другая), которая успешно играет в шахматы, будет пользоваться эвристиками того же типа, что и человек. [16]
В целом ее развитие было направлено на обеспечение все более адекватных соотношений между сложностью и интенсивностью применения различных эвристик, с одной стороны, и соответствия стратегий управления задаваемым пользователями значениям настроечных параметров - с другой. Имеются достаточные основания полагать, что разработчикам удалось поднять эвристическое программирование на очень высокий уровень. Последняя версия рассматриваемой программы отличается от всех предыдущих чрезвычайной гибкостью управления, которой удалось достичь в результате более глубокого анализа ситуаций и отказа от принятия поспешных решений, а также менее активным вмешательством в работу других системных компонентов. [17]
 |
Граф решения задачи, иллюстрирующий структуру С и операторов преобразования. [18] |
Эвристики применяются при составлении графа решения за дачи в процессе эвристической обработки. Существуют два типа эвристик - синтаксические и семантические, названные так в соответствии с типом объекта, проверяемого в процессе применения эвристики. Сначала поясним понятие синтаксической эвристики в геометрии. [19]
Главы б и 7 посвящены в основном эвристическим алгоритмам решения задач дискретного программирования. Как уже отмечалось ранее, под эвристическими понимаются алгоритмы, основанные на правдоподобных, но не обоснованных строго предположениях о свойствах оптимального решения задач. Рассматривается применение различных эвристик для задач о ранце, о коммивояжере, о покрытии графов и ряда других. Показано, что эти эвристики могут приводить к решениям, сколь угодно далеким от оптимальных. Высказывается естественное предположение, что комбинация эвристик позволяет существенно улучшить качество приближенных решений. Описан комбинированный алгоритм для задачи коммивояжера, в котором сочетаются различные эвристики, и проведено его экспериментальное исследование. [20]
Основное назначение SRM как механизма промежуточного планирования состоит в обеспечении установленной администрацией дисциплины обслуживания, максимизации ( при учете всех прочих производственных потребностей) эффективности использования оборудования и стабилизации работы системы в условиях активной конкуренции выполняющих программ. Для достижения всех этих целей планировщику SRM приходится постоянно контролировать состав мультипрограммной смеси. Сделанные ранее замечания о высоком уровне применения эвристик в рамках SRM, а также об отказе от некоторых из них в его последних версиях относятся и к интенсивности управления составом диспетчерской очереди, и к глубине анализа конкретных ситуаций. [21]
Необходимо отметить, что среди них имеются как стратегии, ориентированные на расширение ( expansion) множества дизъюнктов, получаемого путем резолюции, так и на сокращение ( contraction) этого множества путем поглощения. Упорядочение здесь понимается как наличие обоснованного порядка среди дизъюнктов, подлежащих процедуре поиска вывода. Стратегии, основанные на упорядочении, используют поиск только наилучшего ( с применением эвристик) и, как правило, не очень восприимчивы к разрешению целей. Однако использование в них семантических ( например, семантической резолюции) или поддерживающих ( резолюция множества поддержки) требований настраивает поиск на разрешение целей. [22]
Для конкретного случая задачи, предлагавшейся на выпускном экзамене по геометрии в Бруклинском техническом училище, решение с использованием расширенной системы эвристик было найдено менее чем за 5 мин. Когда же использовалась только основная эвристика, машина за полчаса исчерпала свои возможности, так и не решив задачи. В то же время существуют и такие задачи, для которых машина не получает выигрыша от применения дополнительных эвристик. Теорема: Диагонали параллелограмма пересекаются была доказана в обоих случаях приблизительно за 3 мин. [23]
Это еще одна очень интересная парадигма, она исследовалась, и результаты были неоднородны. Для некоторых задач трудности действительно были устранены - можно получить решение, сколь угодно близкое к оптимуму. Результаты эти были очень изящны, но, по-моему, не характеризовали то, что происходит при применении практических эвристик. Практические эвристики очень хороши почти всегда, но не в худшем случае. [24]
Появилась мысль попытаться научить догадкам-эвристикам и машины. При постановке этого вопроса учитывается следующее. Как было показано на примере персептро-на, используя догадку о том, как распознает образы человек, оказалось возможным на основании этой догадки построить машину, способную в оговоренных ранее простейших случаях тоже распознавать образы мгновенно, без длительной, трудоемкой обработки исходных данных. То, что так может получаться, является преимуществом эвристического подхода. Но в рассмотренном примере, а это относится и к любым другим возможным применениям эвристик, поставленная-цель достигается не наверняка, не со стопроцентной гарантией. В отличие от того, что дает алгоритмическое решение различных задач, в том числе и задач распознавания образов, при использовании эвристик нет уверенности в том, что задача обязательно во всех случаях будет решена. Обученный персептрон правильно распознавал простейшие образы почти всегда, но иногда он и ошибался; он распознавал образы правильно лишь с какой-то, пусть даже высокой, степенью вероятности, но не наверняка. При эвристическом подходе к решению пробуют применить сделанное предположение, и затем проверяют, не привелр ли это к ошибочному результату. По существу эвристический метод сводится к так называемому методу проб и ошибок. Применение эвристик оказывается нужным там, где у нас нет твердых знаний; по мере их появления, когда мы знаем, как нужно сделать то или иное, эвристики заменяются точными алгоритмами. Во многих случаях оказывается эффективным совместное применение алгоритмов и эвристик. Как могут вводиться эвристики в машину и использоваться ею, покажем в ходе этой нашей бесеДы на конкретном примере немного позднее. [25]
Страницы: 1 2