Обход бесконечных деревьев
Бывают ситуации, когда необходимо обработать бесконечное дерево. Дерево может генерироваться, когда мы обращаемся к нему (например, мы обходим сайт, страницы которого генерируются сервером во время обращения), либо его размер просто не известен (и возможно велик).
Если дерево растёт бесконечно в глубину, то его можно обрабатывать, используя проход в ширину. То есть, известно, что если спускаться вниз по ветви, то до конца мы не дойдём, но на данном уровне дерево имеет конечный размер.
Если дерево растёт бесконечно в ширину, но при этом имеет конечную глубину (то есть, у узла не два наследника, а из бесконечно много), то можно использовать поиск в глубину.
Обработку бесконечного дерева можно заканчивать например, когда обработано достаточно большое количество узлов или их значения достигли какой-то величины.
Пусть робот "шмугл" индексирует страницы на сайте. Количество ссылок на странице конечно. (т.к. страница конечна). То есть можно рассматривать страницы как узел, ссылки с которой ведут к другим узлам. Конечно, есть ссылки, которые ведут на предыдущие страницы, есть кросс-ссылки между страницами на одном уровне вложенности и т.д., сейчас всех тонкостей рассматривать не будем. То есть, есть дерево, у каждого узла которого конечное число наследников. В лучшем случае количество ссылок конечно и охватывает весь сайт. Однако, может попасться страница, на которой есть календарь, ссылки с которого генерируются автоматически. Программист забыл, что ссылки в будущее надо запретить, поэтому в глубину мы получаем бесконечно дерево, каждый новый узел которого генерируется автоматически. Обход этого дерева закончится, например, когда будет забит канал или превышен лимит по ссылкам.
Бывают ситуации, когда необходимо обработать бесконечное дерево. Дерево может генерироваться, когда мы обращаемся к нему (например, мы обходим сайт, страницы которого генерируются сервером во время обращения), либо его размер просто не известен (и возможно велик).
Если дерево растёт бесконечно в глубину, то его можно обрабатывать, используя проход в ширину. То есть, известно, что если спускаться вниз по ветви, то до конца мы не дойдём, но на данном уровне дерево имеет конечный размер.
Если дерево растёт бесконечно в ширину, но при этом имеет конечную глубину (то есть, у узла не два наследника, а из бесконечно много), то можно использовать поиск в глубину.
Обработку бесконечного дерева можно заканчивать например, когда обработано достаточно большое количество узлов или их значения достигли какой-то величины.
Пусть робот "шмугл" индексирует страницы на сайте. Количество ссылок на странице конечно. (т.к. страница конечна). То есть можно рассматривать страницы как узел, ссылки с которой ведут к другим узлам. Конечно, есть ссылки, которые ведут на предыдущие страницы, есть кросс-ссылки между страницами на одном уровне вложенности и т.д., сейчас всех тонкостей рассматривать не будем. То есть, есть дерево, у каждого узла которого конечное число наследников. В лучшем случае количество ссылок конечно и охватывает весь сайт. Однако, может попасться страница, на которой есть календарь, ссылки с которого генерируются автоматически. Программист забыл, что ссылки в будущее надо запретить, поэтому в глубину мы получаем бесконечно дерево, каждый новый узел которого генерируется автоматически. Обход этого дерева закончится, например, когда будет забит канал или превышен лимит по ссылкам.
Traversing endless trees
There are situations when it is necessary to process an endless tree. The tree can be generated when we access it (for example, we go around a site whose pages are generated by the server during access), or its size is simply not known (and possibly large).
If the tree grows infinitely in depth, then it can be processed using a width pass. That is, it is known that if we go down the branch, then we will not reach the end, but at this level the tree has a finite size.
If the tree grows infinitely in width, but at the same time has a finite depth (that is, the node has not two heirs, but from infinitely many), then depth-first search can be used.
Processing of an infinite tree can be finished, for example, when a sufficiently large number of nodes have been processed or their values have reached a certain value.
Let the "shmugl" robot index pages on the site. The number of links on the page is finite. (since the page is finite). That is, you can think of pages as a node, links from which lead to other nodes. Of course, there are links that lead to previous pages, there are cross-links between pages at the same nesting level, etc., now we will not consider all the subtleties. That is, there is a tree, each node of which has a finite number of descendants. At best, the number of links is finite and covers the entire site. However, you may come across a page on which there is a calendar, links from which are generated automatically. The programmer forgot that references to the future must be prohibited, so in depth we get an infinite tree, each new node of which is generated automatically. The traversal of this tree will end, for example, when the channel is clogged or the link limit is exceeded.
There are situations when it is necessary to process an endless tree. The tree can be generated when we access it (for example, we go around a site whose pages are generated by the server during access), or its size is simply not known (and possibly large).
If the tree grows infinitely in depth, then it can be processed using a width pass. That is, it is known that if we go down the branch, then we will not reach the end, but at this level the tree has a finite size.
If the tree grows infinitely in width, but at the same time has a finite depth (that is, the node has not two heirs, but from infinitely many), then depth-first search can be used.
Processing of an infinite tree can be finished, for example, when a sufficiently large number of nodes have been processed or their values have reached a certain value.
Let the "shmugl" robot index pages on the site. The number of links on the page is finite. (since the page is finite). That is, you can think of pages as a node, links from which lead to other nodes. Of course, there are links that lead to previous pages, there are cross-links between pages at the same nesting level, etc., now we will not consider all the subtleties. That is, there is a tree, each node of which has a finite number of descendants. At best, the number of links is finite and covers the entire site. However, you may come across a page on which there is a calendar, links from which are generated automatically. The programmer forgot that references to the future must be prohibited, so in depth we get an infinite tree, each new node of which is generated automatically. The traversal of this tree will end, for example, when the channel is clogged or the link limit is exceeded.
У записи 2 лайков,
0 репостов,
317 просмотров.
0 репостов,
317 просмотров.
Эту запись оставил(а) на своей стене Николай Носов
