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

0(/*) =1 12 +....+ /" + /*-' + /*. Например, для / = 10, к = 5 будем иметь 0(/*) = 111111. При итеративном поиске на глубину к вершины глубины к просматриваются один раз, глубины к-\ — два раза, глубины к-2 — три и т.д. Корневая вершина просматривается к + 1 раз. Таким образом, оценка сложности по времени при итеративном поиске в глубину вычисляется по формуле 0(/*) = {к + 1) /° + {к) /' + {к-\) 1г+ .... + 3 /*"2 + 2 /*-' + 1 /*. Для / = 10, к = 5 будем иметь 0(/*) = 123456. По сравнению с оценкой сложности по времени для ограниченного поиска в глубину сложность по времени для итеративного поиска в глубину возросла только на 11%. Из формулы, приведенной выше, видно, что чем выше степень ветвления, тем ниже доля сложности, получающейся за счет повторного просмотра вершин. Но даже для случая, когда / = 2, сложность по времени итеративного поиска в глубину только в два раза превосходит сложность по времени простого поиска в глубину. Это означает, что оценка сложности по времени