Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Поиск в пространстве состояний




Поиск решения в одном пространстве.

Вопрос 4. Комплексные затраты труда для работников животноводства

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

Карта затрат труда разрабатывается для различных сельскохозяйственных животных и половозрастных групп скота с учетом направления использования продуктивности и технологии выполнения работ.

Нормативно-технологические карты разработаны на более распространенные варианты применяемой механизации и технологии выполнения работ.

В сборнике комплексных нормативов труда для работников животноводства кроме затрат времени на выполнение отдельных технологических операций рассчитаны:

1. норм обслуживания, численности работников (обслуживающего персонала)

2. затрат труда на центнер продукции;

3. комплексных затрат времени на обслуживание 1 головы;

4. суточной трудоемкости работ.

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

 

 

Задача поиска в пространстве состояний может быть сформулирован так.

Пусть задана тройка (S0, F, ST), где S0 – множество начальных состояний (условия задачи), F – множество операторов задачи, отображающих одни состояния в другие, ST – множество конечных (целевых) состояний (решений задачи).

В этой постановке решить задачу – значит определить такую последовательность операторов, которая преобразует начальные состояния в конечные. Процесс решения можно представить в виде графа G = (X,Y),

X = {x0, x1,…} – множество, в общем случае бесконечное, вершин графа, каждая из которых отождествляется с одним из состояний, а Y – множество, содержащее пары вершин (xi, xj), где (xi, xj) Î X.

Если каждая пара (xi, xj) неупорядочена, то ее называют ребром, а граф называют неориентированным. Если для каждой пары (xi, xj) задан порядок, то пару (xi, xj) называют дугой (ориентированным ребром), а граф называют ориентированным (направленным). Вершины пары (xi, xj) называют концевыми точками ребра (дуги).

Поиск в пространстве состояний более естетсвенно представлять в виде ориентированного графа. Наличие пары (xi, xj) свидетельствует о существовании некоторого оператора f (f Î F), преобразующего состояние, соответствующее вершине xi в состояние xj. С точки зрения поиска в пространстве состояний для некоторой вершины xi уместно выделить множество всех направленных пар (xi, xj), (xi, xj) Î Y, т.е. множество дуг, исходящих из вершины xi (родительской вершины), и множество вершин (называемых дочерними вершинами), в которые эти дуги приводят. Множество дуг, исходящих из вершины xi, соответствует множеству операторов, которые могут быть применены к состоянию, соответствующему вершине xi. В множестве вершин X выделяют подмножество вершин X0 подмножество X, соответствующее множеству начальных состояний (S0), и подмножество вершин XT подмножество (знак) X, соответствующее множеству конечных (целевых) состояний (ST). Множество XT может быть задано как явно, так и неявно, т.е. через свойства, которыми должны обладать целевые состояния.

Определим на графе G маршрут L как такую последовательность ребер, что каждые два соседних ребра имеют общую концевую точку. Будем обозначать путь L как последовательность (xi1, xi2, …, xi(k+1)), где пара (xi(j-1), xij) Î Y, j = 2, …, k+1. Будем говорить, что маршрут L имеет длину k и соединяет вершины (состояния) xi1 и xi(k+1).

В случае ориентированного графа маршрут называется путем. Очевидно, что решение задачи методом поиска в пространстве состояний (т.е. нахождение последовательности операторов, преобразующей начальное состояние в конечное) сводится к задаче поиска пути L на графе G. Путь из x0 принадлежащего (знак) X0 в xT принадлежит (знак) XT называют решающим (целевым). Часто удобно приписывать дугам графа веса, отражающие стоимость применения стоимость соответствующих операторов.

Для обозначения стоимости дуги, направленной из xi в xj, используют запись c(xi,xj). Стоимость пути между двумя вершимнами определяется как сумма стоимостей всех дуг, образующих этот путь. В ряде приложений возникает задача нахождения пути (путей), имеющих минимальную стоимость, между любыми элементами из множества Х0 и любыми элементами множества ХТ. Отметим, что граф G может быть задан как в явном виде, так и неявно. Неявное задание графа G состоит в определении множества операторов, которые будучи применимы к некоторой вершине графа, дают все ее дочерние вершины.

Итак, граф G задает пространство состояний, т.е. пространство, в котором осуществляется поиск решения.

Построение пространства осуществляется с помощью следующего процесса. Берется некая вершина из x0 (знак принадледжит) X0, к ней применяются все возможные операторы, порождающие все дочерние вершины. Порождение всех дочерних вершин для некоторой вершины xi называют процессом РАСКРЫТИЯ ВЕРШИН.

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

Надежным способом обеспечения полноты является ПОЛНЫЙ ПЕРЕБОР всех вершин.

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

При поиске в глубину сначала раскрывается та вершина, которая была построена самой последней. Глубина вершины в графе определяется так:

1) глубина начальной вершины равна нулю;

2) глубина неначальной вершины равна единице плюс глубина наиболее близкой родительской вершины.

При практической реализации поиск в глубину в некотором направлении завершается в следующих случаях: 1) при достижении целевой вершины; 2) при достижении терминальной вершины; 3) при построении в ходе поиска вершины, глубина которой превышает некоторую граничную глубину. При поиске в ширину вершины раскрываются в том же порядке, в котором они порождаются. Если в пространстве состояний ввести операторы, переводящие состояние Si в предшествующее состояние Si-1, то поиск может осуществляться не только в направлении от начального состояния к целевому, но и в обратном направлении. Поиск первого типа называют поиском от данных (или прямым поиском), а поиск второго – поиском от цели (или обратным поиском).

Более того, можно организовать поиск в обоих направлениях одновременно. Такой поиск называют двунаправленным (или бинаправленным).

При переборе всего пространства оба метода будут анализировать одинаковое количество вершин, однако метод поиска в ширину будет требовать существенно больше памяти, так как он запоминает все пути поиска (а не один как при поиске в глубину).

 

 




Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 588; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.01 сек.