Субоптимальное решение

Cтраница 3

Следующий раздел посвящен изложению идеи использования процедуры размывания эвристических алгоритмов поиска решений. Обычно эвристические процедуры ведут к одному из допускаемых решений, и оно не может быть улучшено этой процедурой, независимо от того сколь далеким является это решение от оптимального. Метод размытых эвристик позволяет порождать класс субоптимальных решений и дает возможность последовательно приближаться к оптимальному решению. [31]

Влияние изменения в 2 раза масштаба х на вектор-градиент. [32]

Любое решение, которое удовлетворяет этим ограничениям, называется допустимым или субоптимальным. Таким образом, оптимальное решение является лучшим допустимым решением в смысле заданного критерия. Мы интересуемся как оптимальным, так и субоптимальными решениями, так как есть много задач, для которых оптимальное решение или неизвестно, или из-за своей сложности практически неприемлемо. [33]

В этом пункте мы покажем, что стоимость субоптимального решения, полученного с помощью метода ветвей и границ, превышает оптимальное значение не более чем на заранее заданную величину. [34]

Соответствуя выбранному уровню толерантности, этот способ дает, таким образом, лишь субоптимальное решение. Но зато, вместо задачи поиска Ymin он имеет дело с задачей анализа системы при заданном значении Y, что существенно упрощает алгоритм самой процедуры, тем более что она в этом варианте целиком находится в рамках пространства состояний. Более того, обладая возможностью сколь угодно точно приближать Y к Ymin это способ позволяет получить такое субоптимальное решение, которое практически совпадает с оптимальным, поэтому, если не оговорено особо, оно будет называться оптимальным. [35]

Отдельные гипотезы Г5 могут иметь большую или меньшую эффективность в зависимости от конкретных условий решаемой задачи. Кроме того, эффективность гипотез может различаться на различных этапах поиска. Целью адаптивной процедуры является формирование эффективных композиций гипотез для различных этапов поиска решения, обеспечивающих быстрый поиск субоптимальных решений. [36]

Самые трудные задачи класса NP называют NP - полными. Это название объясняется тем, что если бы удалось доказать, что существует полиномиальное решение такой задачи, то такое решение существовало бы и для любой другой задачи класса NP, т.е. классы Р и NP совпадали бы. Поскольку, как уже говорилось, такой сценарий крайне маловероятен, именно для таких проблем наиболее важен поиск субоптимальных решений. [37]

К сожалению, эффективный алгоритм решения данной задачи пока не известен. Для сложных сетей число гамильтоновых циклов, которые необходимо просмотреть для выделения минимального, непомерно огромно. Однако существуют алгоритмы поиска субоптимального решения. Субоптимальное решение необязательно даст цикл минимального общего веса, но найденный цикл будет, как правило, значительно меньшего веса, чем большинство произвольных гамильтоновых циклов. [38]

Большая часть исследований по проблемам принятия решений выполнена в двух разных областях: нечеткой логике и поведенческой психологии. В психологии поведения ( и ее подмножестве - поведенческих финансах) мы имеем богатые эм - ПМПНТТРПШР ланныр отттогитплыю того, кяк тюди утрттттимпют решения, основываясь на правилах большого пальца, именуемых эвристиками. Однако бихевиористы не имеют математической модели, которая позволила бы нам использовать это знание. К тому же, бихевиористы утверждают, что индивиды принимают субоптимальные решения, сравнивая при этом то, что люди в действительности делают, с тем, что они должны были бы делать, основываясь на хорошем байесовском анализе. [39]

Статическое планирование процессов осуществляется до начала выполнения программы. Таким образом, порядок следования процессов уже известен к моменту компоновки объектных модулей в загрузочные, исполняемые модули. Динамический план формируется в ходе прогона программы. В случае, когда вся необходимая информация о состоянии вычислительной системы и потребностях процессов в ресурсах известна, можно говорить об оптимальном планировании, используя соответствующий критерий оптимальности. В случае, когда получение оптимального решения из-за проблем вычислительного характера невозможно, ищут близкое к нему приемлемое, субоптимальное решение. Здесь возможно построение приближенных и эвристических планов. Как правило, эвристики базируются на использовании наблюдаемых параметров, косвенно влияющих на эффективность планирования. Так, степень связности процессов по данным и распределение процессов по узлам влияет на загруженность коммуникационной среды. Однако не всегда и не только эти факторы непосредственно определяют реальную производительность вычислительной системы. [40]

Во многих практических ситуациях не обязательно получить точное решение. Приемлемыми могут считаться такие решения, о которых известно, что их стоимость отличается от оптимальной на несколько процентов. Похожий Подход заключается в нахождении решений с помощью таких эвристических алгоритмов, для которых вычислены границы характеристик для наихудшего случая [36, 49, 46] ( см. гл. Эти границы являются фиксированными. Поскольку они должны быть справедливы во всех случаях ( включая вырожденные), то часто они оказываются весьма широкими. В методах, рассматриваемых в настоящей главе, допуск, определяющий величину максимального допустимого отклонения, может быть задан произвольно. Точность, определяемая этим допуском, в принципе достижима, но это может потребовать больше вычислительных ресурсов, чем выделено. Важную роль при этом играет получаемое эвристическими методами субоптимальное решение, которое дает начальную верхнюю границу. Алгоритм ветвей и границ может либо проверить, что данное решение удовлетворяет заданному допуску, либо построить новое решение, которое бы ему удовлетворяло. [41]

Страницы: 1 2 3