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