Род Стивенс

Книги → Delphi. Готовые алгоритмы → Глава 8. Деревья решений

Подобно задачам о выполнимости, разбиении и поиске Гамильтонова пути, в этом примере нужно дать положительный или отрицательный ответ на вопрос. Это означает, что нельзя применять частные или приближенные решения при ис­следовании дерева решений.

Можно использовать определенный тип методики ветвей и границ, если зара­нее известно, какие места размещения контор не приведут к хорошим решениям. Например, вы ничего не получите, помещая новое пожарное депо между двумя другими, расположенными близко друг от друга. Если все узлы в пределах рас­стояния D от нового депо находятся также в пределах расстояния D от другого депо, значит, новое депо нужно поместить в какое-то иное место. Однако подоб­ные вычисления потребуют большого количества времени, и задача все еще оста­ется очень сложной.

Так же, как и для задачи разбиения и поиска Гамильтонова пути, для задачи о пожарных депо существует обобщенный случай. В обобщенном случае вопрос звучит следующим образом: если задана сеть и некоторое число F, в каких узлах сети нужно разместить Рдепо, чтобы наибольшее расстояние между любым узлом и пожарным депо было минимальным?

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

Краткая характеристика сложных задач

Читая предыдущие разделы, вы, наверное, заметили, что для многих задач есть парные варианты. Первый вариант задачи задает вопрос: «Есть ли решение задачи, удовлетворяющее определенным условиям?» Второй уточняет: «Каково лучшее решение этой проблемы?» v

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

При решении более обобщенной задачи можно использовать частные решения, чтобы применить метод ветвей и границ. Это не облегчает поиск наилучшего ре­шения, поэтому не поможет получить точное решение для частной задачи. Напри­мер, самый короткий Гамильтонов путь через сеть найти сложнее, чем любой Га­мильтонов путь через ту же сеть.

С другой стороны, эти вопросы обычно относятся к различным входным дан­ным. Если сеть сильно разрежена, то вообще трудно сказать, существует ли такой путь. Вопрос о кратчайшем Гамильтоновом пути актуален в случае, когда сеть плотная и имеется много таких путей. При таких условиях частные решения най­ти легко и метод ветвей и границ сильно упростит решение задачи.

Резюме

← предыдущая следующая →

Страницы раздела: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Публикация компанией Dropbox кода Zulip – средства общения для IT-разработчиков

20.11.2015
Одной из одобрительно встреченных программистами инициатив, реализующихся в рамках акции Hack Week, стала публикация исходного кода приложения Zulip – веб-приложения для общения между собой разработчиков в сфере IT-технологий.

Объединение ОС Android и Chrome

17.11.2015
Слухи об объединении двух крупнейших ОС компании Google, Android и Chrome, гуляют по Интернету уже более 5 лет, но до сих пор этого не случилось, хотя очевидно, что с течением времени эти ОС становятся всё более похожими: так, в последнее время появилось немало Android-устройств, к которым прилагаются клавиатуры, а Chrome OS «научилась» работать с сенсорными экранами.

Конференция Linux Piter 2015

15.11.2015
Уже почти через неделю в Санкт-Петербурге впервые в истории пройдёт конференция, посвящённая проблемам свободного программного обеспечения – Linux Piter 2015.