но, и в этом случае могут помочьалгоритмы эвристического поиска, которые обладают высокой вероятностью правильного выбора решения. Рассмотрим некоторые из этих алгоритмов.
Алгоритм наискорейшего спуска по дереву решений
Пример построения более узкого дерева рассмотрим на примере задачи о коммивояжере. Торговец должен побывать в каждом из 5 городов, обозначенных на карте ( рис. 3. 3).
Рис. 3. 3.
Задача состоит в том, чтобы, начиная с города А, найти минимальный путь, проходящий через все остальные города только один раз и приводящий обратно в А. Идея метода исключительно проста - из каждого города идем в ближайший, где мы еще не были. Решение задачи показано на рис. 3. 4.
Рис. 3. 4.
Такой алгоритм поиска решения получил название алгоритма наискорейшего спуска (в некоторых случаях - наискорейшего подъема).
Алгоритм оценочных (штрафных) функций
Умело подобранные оценочные функции (в некоторых источниках - штрафные функции) могут значительно сократить полный перебор и привести к решению достаточно быстро в сложных задачах. В нашей задаче о людоедах и миссионерах в качестве самой простой целевой функции при выборе очередного состояния можно взять число людоедов и миссионеров, находящихся "не на месте" по сравнению с их расположением в описании целевого состояния. Например, значение этой функции fxy для исходного состояния f06, а значение для целевого состояния f10.
Эвристические процедуры поиска на графе стремятся к тому, чтобы минимизировать некоторую комбинацию стоимости пути к цели и стоимости поиска. Для задачи о людоедах введем оценочную функцию:
f(n) d(n) w(n)
где d(n) - глубина вершины n на дереве поиска и w(n) - число находящихся не на нужном месте миссионеров и людоедов. Эвристиказакл
Страницы: << < 1 | 2 | 3 | 4 | 5 > >>