Главная Случайная страница


Полезное:

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


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Задача о кубиках





При всей своей простоте эта задача является модельной для решения одной из центральных задач робототехники — задачи о составлении упорядоченного плана операций.

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

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

Проблемная ситуация — положение и состав всех трех столбиков. Разрешенные ходы — перемещения верхнего кубика. Будем задавать состояния как список столбиков, столбики — как список символов, голова списка — верхний кубик.

Начальное состояние: [[‘c’,’a’,’b’]],[],[]].

Целевое состояние:

end(Prob):-

member([’a’,’b’,’c’],Prob).

Теперь можно определить правила возможных переходов из состояния в состояние.

Ранее мы всегда предполагали, что граф задан явным образом. Но в задачах ИИ граф пространства состояний нам не известен, так как пространство состояний имеет астрономические размеры или даже бесконечно. Поэтому для каждого текущего состояния состояния-преемники будут вычисляться с помощью правила go(Prob1,Prob2).

В Prob1 имеются два столбика Stolb1 и Stolb2 такие, что верхний кубик из Stolb1 можно поставить на Stolb2 (рис. 1):

Рисунок 1. Правило перекладывания верхнего кубика

Удалить из Prob1 непустой столбик Stolb1. Оставшиеся обозначить Tprob1.

Удалить из Tprob1 столбик Stolb2. Оставшиеся обозначить TTProb1.

Голову списка Stolb1 сделать головой списка Stolb2.

go(Prob1,[Stolb1,[H|Stolb2]|TTProb1]):-

del([H|Stolb1],Prob1,TProb1),

del(Stolb2,TProb1,TTProb1).

del(X,[X|L],L).

del(X,[Y|L],[Y|L1]):-

del(X,L,L1).

Теперь пространство состояний задано полностью. Осталось найти путь. Путь на графе можно найти поиском в глубину или ширину. Откажемся пока от однократного просмотра каждой вершины.

Рекурсивная процедура поиска в глубину depth

depth(Way,Sol), где Way — текущий путь;

Sol — окончательное решение;

Z — целевая вершина.

depth([Z|Was],[Z|Was]):-

end(Z).

% рекурсивное правило продолжения пути

depth([X|Was],Sol):-

go(X,Y),

not(member(Y,Was),

depth([Y,X|Was],Sol).

% Запуск глубины с начальной путем из одной вершины

solve:-

A=[[c,a,b],[],[]],

depth([A],Sol), write(Sol), nl.

Sol — список состояний, соответствующий сделанным ходам.

Задание. Написать программу, реализующую составление упорядоченного плана перестановок кубиков поиском в глубину в пространстве состояний.

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

Date: 2015-08-07; view: 615; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию