Cтраница 1
Процедура эвристического ветвления состоит в следующем. [1]
Хотя процедура эвристического ветвления является асимптотически оптимальной, однако ее эффективность существенно зависит от правильности гипотез, выдвигаемых экспертом. Если они правильны, то процедура дает возможность намного сократить время поиска по сравнению с полным перебором или случайным равновероятным выбором. При отсутствии правильных гипотез это улучшение достигнуто быть не может. [2]
Основной смысл метода эвристического ветвления [1, 2] состоит в следующем. Тогда задача эксперта, осуществляющего поиск решения, состоит в том, чтобы указать наиболее перспективное, по его мнению, направление или упорядочить все возможные направления по эвристической оценке их перспективности. После этого с помощью ЭВМ порождаются допустимые решения, принадлежащие всем возможным направлениям, однако основное внимание сосредоточивается на тех направлениях, которые эксперт считает наиболее перспективными. Результаты работы машины выдаются эксперту, он их анализирует, уточняет свои предположения и процедура переходит к следующему шагу, аналогичному предыдущему. При этом предполагается существование реализуемых алгоритмов для порождения допустимых решений, принадлежащих заданным направлениям поиска. [3]
Для дискретных задач процедура эвристического ветвления является асимптотически оптимальной. [4]
В первой части статьи излагается человеко-машинная процедура поиска решений, названная эвристическим ветвлением, на базе которой эксперт, ведущий решение задачи, может осу ществлять проверку и последовательное уточнение выдвигаемых гипотез. Вторая часть посвящается вопросам использования процедур адаптивного случайного поиска для оценки выбранных гипотез и формирования наборов, необходимых для решения конкретных задач. [5]
Рассматриваются методы поиска субоптимальных решений для задач, не имеющих практически реализуемых способов нахождения оптимальных решений. В числе возможных подходов рассматриваются диалоговые алгоритмы, использующие метод эвристического ветвления, метод размытых эвристик, адаптивные процедуры i о иска, а также субоптимальные алгоритмы, базирующиеся на идеях динамического программирования. [6]