3.12. ИСПОЛЬЗОВАНИЕ ДРУГИХ ЭВРИСТИК

Перебор этапами

До сих пор в настоящей главе мы обсуждали вопрос о том, что использование эвристической информации может существенно уменьшить объем перебора, необходимого для пбиска приемлемого пути. Следовательно, ее использование позволяет также осуществлять перебор на гораздо больших графах. И тем не менее могут возникнуть случаи, когда имеющаяся в нашем распоряжении память оказывается исчерпанной раньше, чем будет найден удовлетворительный путь. В этих случаях может быть полезным не отказываться полностью от продолжения перебора, а «отсечь» часть ветвей дерева, построенного к этому моменту в процессе перебора, освободив тем самым пространство памяти, необходимое для углубления перебора.

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

например вершины с наименьшими значениями Наилучшие пути к этим вершинам запоминаются, а остальная часть дерева отбрасывается. Затем начинается перебор снова, уже от этих «лучших» открытых вершин. Этот процесс продолжается до тех пор, пока либо будет найдена целевая вершина, либо будут исчерпаны все ресурсы. Ясно, что цаже если на каждом этапе используется алгоритм А, то хотя весь процесс заканчивается построением некоторого пути, тем не менее у нас нет теперь гарантии, что этот путь будет оптимальным.

Ограничение числа дочерних вершин

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

Один из приемов, который может позволить снизить требуемый объем перебора, состоит в том, чтобы сразу же после раскрытия вершины отбросить почти все дочерние вершины, оставив лишь небольшое их число с наименьшими значениями функции Конечно, отброшенные вершины могут оказаться расположенными на наилучших (и даже только на наилучших) путях, так что только эксперимент может определить пригодность такого метода отсечения ветвей графа для конкретных задач.

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

Поочередное построение дочерних вершин

Когда вершины, непосредственно следующие за некоторой, вычисляются с помощью операторов в пространстве состояний, то очевидно, что эти последующие вершины могут строиться по отдельности и независимо друг от друга. Кроме того, существуют случаи, когда применение всех применимых операторов было бы очень расточительно в смысле вычислительных затрат. Как указывалось выше, более информированный оператор Г

выделял бы несколько наиболее перспективных операторов и строил бы только те последующие вершины, которые возникают в результате их применения. Более гибкий подход состоит в том, чтобы сначала допускать применение самого перспективного оператора (что приведет к одной последующей вершине), оставляя в дальнейшем возможность в процессе перебора построить и другие вершины, непосредственно следующие за данной. Для того чтобы воспользоваться этой идеей вместе с оценочными функциями для упорядочения вершин, в алгоритм упорядоченного перебора следует внести соответствующие изменения.