Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 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. Обратный и двунаправленный поиск в ширину Задание. Написать программу составления упорядоченного плана перестановок кубиков за минимальное число шагов с помощью поиска в ширину в пространстве состояний. Определить ее вычислительную сложность, то есть, как быстро будет расти число шагов, производимых алгоритмом, при неограниченном увеличении размерности пространства состояний.
|