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


Полезное:

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


Категории:

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






Множества начальных вершин, прямой и обратный поиск





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

solve([H|T]):-

depth(H,Sol).

solve([_|T]):-

solve(T).

При поиске в ширину образуем из начальных вершин начальные пути и соберем их в список: L0 — список начальных вершин, W0 — список начальных путей.

solve(L0):-

findall(Was,make_way(X,L0,Way),W0),

width(W0,Sol).

make_way(X,L0,[X]):-

member(X,L0).

Если начальных состояний довольно много, а конечное одно, удобно производить поиск обратный поиск — от конечного к начальному. Если ходы в пространстве не обратимы, то вместо процедуры go может потребоваться обратная процедура go1. Кроме того, поиск в ширину можно сделать двунаправленным — для просмотра меньшей области пространства.

Рисунок 3. Обратный и двунаправленный поиск в ширину

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

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



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