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

Cтраница 2

Целью настоящего раздела является поиск путей сокращения вычислений и объема требуемой памяти благодаря переходу от поиска оптимального решения к поиску субоптимальных решений, последовательно приближающихся к оптимальному по мере увеличения времени поиска. [16]

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

Рассмотрим некоторые подходы к сокращению ма вычислений и требуемой памяти за счет отказа от поиска оптимального решения и перехода к порождению последовательности субоптимальных решений. [18]

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

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

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

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

Задача коммивояжера состоит в поиске гамильтонова цикла минимального общего веса в нагруженном графе. Алгоритм ближайшего соседа позволяет найти субоптимальное решение задачи коммивояжера. [24]

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

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

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

Из всех перечисленных выше алгоритмов только прямой симплекс-метод гарантирует допустимость плана задачи с самого начала вычислений. Это обстоятельство является очень важным, так как позволяет не доводить всех вычислений до конца и ограничиться получением субоптимального решения. Использование этой формулы, как показали вычислительные эксперименты Джекобсена, позволяет в значительной мере преодолеть основной недостаток метода декомпозиции Данцига - Вулфа - плохую сходимость прямого алгоритма вблизи точки оптимума. [28]

Ребра, входящие в гамильтонов цикл С. [29]

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

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