Лекция
Привет, сегодня поговорим про веревочный телеграф, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое веревочный телеграф , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.
Гомельская городская олимпиада, 1999
Тимур и его друзья, приехав летом на свои старые дачи, решили устроить на время своего отдыха игру. Они организовали команду, чтобы тайно помогать жителям дачного городка в их повседневных делах. Дачный поселок довольно большой, и дома, в которых живут друзья Тимура, расположены далеко друг от друга. Как быстро передавать друг другу сообщения? Как собирать ребят на совет?
Тимур решил проложить веревочный телеграф , который связал бы все домики, в которых живут ребята из его команды. Всего домиков N. По карте ребята вычислили координаты каждого домика (Xi, Yi) в целых числах и выписали их на бумаге. За единицу измерения координат они взяли один метр. Однако возник вопрос: какие домики нужно соединять веревочным телеграфом, чтобы связь была между всеми домиками (возможно, через другие домики), а общая длина всех веревок была как можно меньше?
Требуется написать программу, которая по координатам домиков определяла бы, какова минимальная общая длина всех веревок, соединяющих все домики между собой (возможно, через другие домики).
Порядок ввода Порядок вывода N X.xx X1 Y1 X2 Y2 .. .. XnYn
где X.xx — минимальная общая длина веревки с точностью до двух знаков в дробной части.
Пример ввода Пример вывода 5 623.61 100 200 200 200 300 400 400 200 400 100
Ограничения:
0 < N < 100
-32 000 <= Xi,Yi <= 32 000
Рассмотрим домики тимуровцев как вершины графа, веревки между ними — как ребра графа, а длины веревок — как веса ребер. Теперь перед нами задача о минимальном остовном дереве.
В данном случае исходный граф — полный, то есть существует ребро между любыми его двумя вершинами, поскольку по условиям задачи веревки можно протянуть между любыми двумя домиками. В данной задаче удобно представлять граф в виде матрицы весов ребер: D[i,j] — расстояние между вершинами i и j.
Результат работы алгоритма построения остовного дерева методом Прима будет представлен в виде массива Prev [0..N-1]: Prev [i] = j, то есть предком вершины i в остовном графе будет вершина j, или, другими словами, минимальное остовное дерево будет содержать ребро (i,j). У вершины 0 предка не будет (Pred[0] = -1).
Telegraph()
1. Считать координаты домов из файла.
2. Найти расстояния между всеми парами домов и занести результаты в
матрицу смежности.
3. Использовать алгоритм Прима для нахождения наименьшего остового дерева
(выполнять пп 3.1-3.4):
3.1. Добавить все вершины в очередь и инициализировать значение ключа
бесконечностью.
3.2. Присвоить стартовой вершине значение ключа 0.
3.3. Пока в очереди присутствуют вершины, повторять пп. 3.3.1-3.3 :
3.3.1. Найти вершину с минимальным ключом.
3.3.2. Удалить найденную вершину из очереди.
3.3.3. Обновить ключ для всех инцидентных вершин, которые
находятся в очереди.
3.4. Найти сумму ключей всех вершин.
4. Вывести сумму ключей.
Ограничения:
0 -32 000
Решим зададчу на языке паскаль и си.
Рассмотрим домики тимуровцев как вершины графа, веревки между ними — как ребра графа, а длины веревок — как веса ребер. Теперь перед нами задача о миниминимальном остовном дереве. Тело программы, решающей эту задачу, может выглядеть следующим образом:
begin
InputData; {Ввод исходных данных}
MinTree: {Построение минимального остовного дерева}
OutputData: {Вывод результата}
end.
В данном случае исходный граф — полный, то есть существует ребро между люлюбыми его двумя вершинами, поскольку по условиям задачи веревки можно пропротянуть между любыми двумя домиками.
В данной задаче удобно представлять граф в виде матрицы весов ребер:
D[i,j] — расстояние между вершинами i vij. Об этом говорит сайт https://intellect.icu . Ввод данных, обеспечивающий вычисление D[i,j] по исходным данным задачи, представлен ниже и не требует комментариев.
Результат работы алгоритма построения остовного дерева методом Прима будет представлен в виде массива Pred [l..N]: Pred [i] -7, то есть предком вершины i в остовном графе будет вершина; или, другими словами, минимальное остовное дерево будет содержать ребро (iJ).
У вершины 1 предка не будет (Pred[l] - 0).
Ответ задачи по построенному остовному дереву получается следующим образом:
Рассмотрим теперь собственно алгоритм Прима для построения минимального остовного дерева. Идея алгоритма Прима заключается в следующем: пусть А —
это множество ребер части остова, растущей от пустого множества ребер к миниминимальному остовному дереву. Формирование множестваЛ может начинаться с пропроизвольной вершины, называемой корневой. Для определенности в реализации в какачестве корневой выбирается вершина 1.
На каждом шаге в множество (дерево) А добавляется ребро наименьшего веса среди
ребер, соединяющих вершины из дерева А с вершинами не из дерева А. После вывыполнения N - 1 раз таких добавлений мы получаем минимальное остовное дерево.
Для эффективной организации выбора нужного для добавления ребра используиспользуется очередь с приоритетами, в которой хранятся все вершины, еще не попавшие
в деревоЛ. При этом каждая вершина i снабжена также приоритетом — специальспециальной характеристикой Key[i], которая равна минимальному весу ребер, соединяюсоединяющих вершину i с вершинами из А.
Более формально алгоритм Прима может быть записан следующим образом:
Ставим в очередь Q все вершины исходного графа
Устанавливаем для всех вершин Key[i] - бесконечность (MaxD)
Заносим в дерево А вершину 1:
key[l] -0 - расстояние от нее до вершин дерева А
Pred[l]-0 - у корневой вершины нет предка
Пока очередь Q не пуста
Выбираем из очереди вершину U такую, для которой расстояние
от нее до вершин из множества А минимально
Для каждой вершины V. соседней с U
(то есть в графе имеется ребро (U.V)).
если V находится в очереди и D[U.V] то Pred[V]-U
key[V]=D[U.V]
Ниже приведена реализация алгоритма Прима:
Далее приводится полное решение задачи «Веревочный телеграф» алгоритмом
Прима.
#include <iostream>
#include <conio.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
#define MAXVERTEXES 101 //maximal amount of vertaxes
int infinity=2000000; //infinity
float a[MAXVERTEXES][MAXVERTEXES]; //adjacency matrix (distances between houses)
int amount; //amount of houses
struct houses { //structure with coordinates o house
int x;
int y;
};
houses house[100]; //array of houses
void input(); //read coordinates of houses
void createMatrix();//find distances between houses
float prim(int); //find the minimal tree
//===================================== Main program ===============================
void main(){
input(); //read coordinates of houses
createMatrix();//find distances between houses
float length=prim(0); //length of all edges of the MST
printf("\n%0.2f\n\n",length);
//cout<<"\nThe total length of MST is "<<length<<".\n\n"; //print length of MST
system ("pause");
}
//================================== Prim's algorithm ====================================
float prim(int start) { //start vertex
float key[MAXVERTEXES]; //key for the queue
char Q[MAXVERTEXES]; //queue
int amountInQ=amount; //indicator that queue is not empty
for (int u=0; u<amount; u++) {
key[u]=infinity; // initialization
Q[u]=1;
}
int u,v; //vertexes
key[start]=0; //begin from start vertex
while (amountInQ) { //while queue isn't empty
float min=infinity; //find minimal element in the queue
for (int i=0; i<amount; i++) if (Q[i] && key[i]<min) {
u=i; //get it from queue
min=key[i];
}
Q[u]=0; //delete current vertex u from the queue
amountInQ--;
for (int v=0; v<amount; v++)
// for all vertexes v which are incident to u, are still in queue and willn't make cycle
if (a[u][v]!=0 && Q[v] && a[u][v]<key[v]) {
key[v]=a[u][v]; //refresh key
}
}
float sum=0; //length of all edges of MST
for (int i=0; i<amount; i++) sum+=key[i]; //find sum
return sum;
}
// ========================= find distances between houses =========================
void createMatrix(){
for (int i=0; i<amount; i++) //for every pair of houses
for (int j=i; j<amount; j++)
if (i==j) a[i][j]=0; //distance is 0 between house and the same house
else {
a[i][j]=sqrt((float) (house[i].x-house[j].x)*(house[i].x-house[j].x)+
(house[i].y-house[j].y)*(house[i].y-house[j].y));//find distance between houses
a[j][i]=a[i][j];
//create symetric matrix
}
}
//============== Creating array with coordinates of houses ================
void input() {
FILE *file=0; //pointer on input file
char retry='y';
while (file==0 && retry=='y') {
if (retry=='y') {
system("cls");
cout<<"Enter name of the file: ";
char fileName[50]; //name of the file
gets(fileName); //reading name
file=fopen(fileName,"rt"); //open file for reading
}
if (file==0) { //if file doesn't exist offer repeaet entering name
cout<<"File not found. Do you want to retry? (y/n) ";
retry=getch();
}
else {
fscanf(file,"%d",&amount); //read amount of houses
for (int i=0; i<amount; i++) //for every house
fscanf(file,"%d %d",&house[i].x, &house[i].y); //read coordinates of house
fclose(file);
}//end if file found
}//end enter file name
if (retry!='y') exit(0);
}
1.До с соединением ниткой двух полостей додумался еще в 1667 году английский математик Роберт Хук. Правда, вместо пластиковых стаканчиков он использовал две железные банки. Хук обнаружил, что если говорить в одну из банок, то звуки голоса будут вызывать в ней колебания, которые передадутся проводу, а затем и второй банке.
2. В 1888 году в США вдоль одной из дорог была проложена.«веревочная» телефоннаялиния длиной 4,8 километра
3. Понятие так называемого «веревочного телеграфа» используется заключенными они его еще называют заключенные - «дорога».
«Дорога» представляет собой систему тонких веревочек, которые как паутина опутывают часть здания тюрьмы, выходящую во двор. Веревки протягиваются от окна одной тюремной камеры к другой и далее так, что все камеры находятся как бы в одной связке.
По этим веревкам постоянно гонят коней - передают мешочки, где спрятаны «малявы», сигареты или деньги.
Такой, на первый взгляд примитивный способ связи, существующий уже несколько веков, позволяет заключенным обмениваться личными посланиями
и грузами, согласовывать поведение изолированных друг от друга подельников.
На этом все! Теперь вы знаете все про веревочный телеграф, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое веревочный телеграф и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов
Комментарии
Оставить комментарий
Алгоритмы и теория алгоритмов
Термины: Алгоритмы и теория алгоритмов