Искусственный интеллект

Оценим время и память, затрачиваемые в процессе поиска в ширину. Будем полагать, что число последователей каждой вершины равно /. Тогда в начале поиска в ширину мы имеем одну начальную вершину, затем / последователей, потом Р последователей и т.д. В общем случае при глубине дерева поиска, равной к, число вершин, изучаемых в процессе поиска, равно 1 + /+ /2+ /3+ ...+ /*. При конкретных значениях / и к по этой формуле можно вычислить максимальное число вершин дерева поиска, которое может быть получено в процессе поиска в ширину. Естественно, решение можно найти раньше, чем будут найдены все последователи. Однако для некоторых задач эта величина может быть достигнута. Обычно вместо этой формулы употребляют ее обозначение в виде О(1к), которое называют экспоненциальной оценкой сложности. Если полагать, что получение каждого последователя требует одной единицы времени, то O(lk) является оценкой сложности по времени. В процессе поиска в ширину каждая вершина дерева должна сохраняться до получения требуемого решения. Если полагать, что для этого сохранения требуется единица памяти, то та же формула является одновременно и оценкой сложности по памяти для поиска в ширину.