15. Решение задач в пространстве состояний.

Решение задач в пространстве состояний сводится к перебору. Слепой перебор:

- Если вершины раскрываются в том же порядке, в котором они порождаются, то процесс поиска сводиться к полному перебору (Breath-firstprocess, BFP).

- Если сначала раскрывается всегда та вершина, которая была построена самой последней. то процесс поиска сводится к перебору в глубину (Depth-firstprocess, DFP), причем параметр, определяющий границу перебора (глубину), должен быть изначально задан.

Классической задачей поиска в пространстве состояний является задача коммивояжера. Суть ее заключается в поиске маршрута минимальной длины между n городами, при в точности разовом посещении каждого города и возвращении в исходный.

16. Оценочные функции и эвристические методы поиска решений.

Альтернативой слепому перебору являются процедуры, основанные на принципе неявного использования знаний о решаемой задаче с помощью эвристической информации, которая «подталкивает» поиск в сторону цели, раскрывая в первую очередь наиболее перспективные вершины. Методы, использующие знания о решаемой задаче в виде эвристических правил называют эвристическими методами поиска. По существу, в эвристических правилах представлен опыт успешного поиска решений, формализация которого позволяет количественно оценивать сложившуюся ситуацию и определить перспективное направление раскрытия вершин. Принцип использования эвристической информации может быть просто реализован, если вершины одного яруса дерева подлежащие раскрытию, будут представлены в виде упорядоченных, в соответствии с некоторой мерой , списков. Такие меры называются оценочными функциями F(S_i).

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

F(S_i)=r(S₀,S_i)+₁(S_i,S_t)+ ₂(S_i,S_t)+…+ _k(S_i,S_t)

А В

Первая компонента А должна содержать некоторую информацию о том, как осуществляется поиск от начальной вершины S₀ до текущей вершины S_i. Эта компонента - своего рода память о том, как развивалось решение до текущей вершины. Чаще всего А определяется, как расстояние между начальной и раскрываемой вершинами: r(S₀,S_i).

Вторая компонента В обязательно должна включать эвристические оценки перспективности путей от раскрываемой вершины S_i до целевой S_t, причем эта компонента может состоять из нескольких членов.

17. Критерии оценки методов перебора.

1) Целенаправленность перебора (Р) – позволяет определить в какой мере перебор идет в направлении цели, а не ведется в петельном направлении. , где L – длина пройденного пути до цели, T – общее число вершин, построенных в течении перебора. P указывает на то, насколько дерево, построенное при переборе, вытянуто, а не кустисто max P=1. С увеличением L, T растет еще более интенсивно.

2) Фактор эффективного ветвления (В) – определение основано на предположении о дереве, имеющем глубину равную длине пути и общим числом вершин равному числу вершин, построенных в процессе перебора, причем у каждой вершины этого дерева имеется в точности В дополнительных вершин. B+B²+…+B^L=T