Что означает размер границы и исследуемый список в дереве поиска?
У меня есть дерево поиска, использующее поиск в ширину, и вопрос задает наибольший размер границы (полосы) и исследуемого списка.
Я не совсем понимаю, о чем он просит. Я использую поиск по графику, поэтому исследуемый узел будет пропущен. Я просмотрел свои слайды и даже книги, но я все еще не понимаю, о чем он просит. Благодарю.
1 ответ
Прогресс БФС легко визуализировать как наводнение. Посмотрите на нижнее левое изображение в этом ответе, где серые точки представляют "наводнение".
Граница - это "фронт" этого "потока", который на самом деле является узлами, которые должны оцениваться следующим.
"Узлы, которые в данный момент оцениваются", на самом деле хранятся в очереди. Таким образом, наибольший размер границы эквивалентен наибольшему размеру очереди.
Если вы соберете все исследованные узлы в списке, размер этого списка ("исследуемый список") будет иметь список, который будет расти до тех пор, пока поиск не будет остановлен.