Полный перебор и деревья

Ветвление

Ветвление времени, возможность выбора в истории всегда занимали философов и теологов. Если весь ход истории заранее записан в Книге или спланирован Господом, то что зависит от человека? Проблема эта неоднократно обыгрывалась и в научной фантастике. В частности, «эффект бабочки» (Рей Брэдбери) состоит в том, что выбор, случившийся в далёком прошлом и выглядевший там весьма незначительно (раздавленная бабочка), приводит к достаточно радикальным изменениям в истории цивилизации, грамматические правила и политические партии становятся иными.

В математике и информатике ветвящееся время и возможные миры — один из основных способов формального задания смысла логических высказываний в различных формальных языках. Это попытка отразить в формальных языках особенности естественных языков, в частности такие понятия, как «возможно», «необходимо», «вероятно», «когда-то», «желательно», «доказуемо». В другой ветви математики рассматриваются «теория катастроф» и «теория хаоса», также изучающие то, каким образом очень маленькие изменения и незначительные ветвления приводят к глобальным эффектам.

Этим применение формальных деревьев и их графических представлений в человеческой практике не ограничивается. Очень полезными оказываются деревья при классификации. Тогда ветвление соответствует выбору того или иного значения признака классификации. Например, можно классифицировать детей в школе по параллелям, внутри параллели по буквам (3 «А» и 3 «Б»), потом по алфавиту или как-то ещё.

В современном компьютерном мире широко распространились деревья ссылок в составе так называемых гипертекстов. Однако деревья ссылок от одного слова к другому существуют и в обычных, бумажных энциклопедиях.

Языковые структуры тоже удобно представлять в виде деревьев.

Конструкция полного, исчерпывающего перебора важна в нашем курсе и вообще в жизни. (Представьте себе на секунду поиски пропавшего паспорта в квартире или ровно «той самой» кофточки. В этой ситуации бывает нужно последовательно просмотреть все места, полки, ящики и т. д. Часто вещь находится в самом неожиданном месте, там, куда вы её положили, «чтобы она не пропала». Надеемся, что в реальности вам не приходится заниматься такими поисками.)

Иногда бывает очень нужно сократить перебор, подумать, где вещи точно не может быть, и т. п. Но прежде чем изобретать разные стратегии сокращения перебора, нам следует понять, как организовать действительно полный перебор. С одной стороны, выписывание всех путей дерева является примером полного перебора, с другой стороны, во многих случаях перебор естественно представить в виде перемещения по дереву. Например, в случае поисков в квартире можно соотнести со всей квартирой корневую вершину; следующие вершины — это комнаты квартиры; за комнатами идут шкафы, полки и столы, стоящие в комнатах; в шкафах есть отделения и полки и т. д.

Дата добавления: 2015-01-03