Понятия теории графов. Представление задачи в виде теоремы. Поиск решений в пространстве состояний и при сведении задач к подзадачам. Процедура построения графа состояний на примере выбора маршрута транспортным роботом. Свойства эвристических алгоритмов.
Аннотация к работе
Общие способы решения задачДеревом называется ориентированный граф, в каждую вершину которого входит только одна дуга, за исключением одной вершины, называемой корнем дерева. При этом вершинам будут соответствовать задачи, а дугам - операторы редукции задач. Связанные вершины называют И-вершинами, несвязанные - ИЛИ-вершинами, а граф называется графом типа И-ИЛИ. Каждая из вершин, порожденных корнем, порождает по две вершины, и каждая из вершин 2 и 3 уровней - по одной. Поиск решения имеет итеративный характер, причем число итераций и вершин, раскрытых до нахождения целевой вершины, существенно зависит от порядка (последовательности), в котором раскрывались вершины.