Нахождение остовного дерева минимального веса
Постановка задачи: Дана плоская страна и в ней n городов. Нужно соединить все города телефонной связью так, чтобы общая длина телефонных линий была минимальной. Всякую прикладную постановку задачи нелишне уточнить. Мы негласно подразумеваем, что города сравнительно со страной малы; поэтому мы пренебрежем величиной городов и будем изображать город (точнее: телефонную станцию, размещенную в городе) точкой. Введя подходящую систему декартовых координат, мы запишем положение i-го города, парой координат ( ). Условие, что страна плоская, означает, что — расстояние от i-го города, до j-го, задается формулой В задаче речь идет о телефонной связи, т. е. подразумевается транзитивность связи: если i-й город связан с j-м, а j-й с k-м, то i-й связан с k-м. Подразумевается также, что телефонные линии могут разветвляться только на телефонной станции, а не в чистом поле. Наконец, требование минимальности (вместе с транзитивностью) означает, что в искомом решении не будет циклов. Уточненную задачу можно теперь переформулировать в терминах теории графов. В терминах теории графов задача Прима-Краскала выглядит следующим образом: Дан полный граф с n вершинами, длины ребер определяются по формуле (1), где - координаты вершин. Найти остовное дерево минимальной длины. В таком виде задача была поставлена и решена Примом (1961). Краскал, одновременно и независимо, поставил и решил задачу не для плоского случая, где расстояния определяются по формуле (1), а для произвольных положительных . При этом для некоторых пар индексов , что означает отсутствие ребра, т.е. рассматривается любой граф, а не только полный. Итак, вышеприведенный вариант есть, строго говоря, задача Прима, а задача Краскала звучит так: Дан граф с n вершинами; длины ребер заданы матрицей D [ i , j ]. Найти остовное дерево минимальной длины. Обе перечисленные задачи решаются одним алгоритмом, причем алгоритмом самой примитивной разновидности. Представим себе, что зимовщику оставлен некоторый запас продуктов, и его задачей является составление вкусного меню на всю зиму. Если зимовщик начнет с того, что сперва будет есть самую вкусную еду (например, шоколад), потом — вторую по вкусности (например, мясо), то он рискует оставить на последний месяц только соль и маргарин. Подобным образом, если оптимальный (для определенности, минимальный) объект строится как-то по шагам, то нельзя на первом шаге выбирать что-то самое малое, на втором шаге — оставшееся самое малое и т. д. За такую политику обычно приходится жестоко расплачиваться на последних шагах. Алгоритм, который мы привели, называется жадным. В задаче Прима-Краскала жадный алгоритм дает точное оптимальное решение. Как известно (это легко доказать, скажем, по индукции), дерево с n вершинами имеет n-1 ребер. Оказывается, каждое ребро надо выбирать жадно (лишь бы не возникали циклы).
Популярное: Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение... Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Почему стероиды повышают давление?: Основных причин три... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (318)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |