Соединить все города телефонной связью так, чтобы общая длина телефонных линий была минимальной

@Shadu · Регистрация: 16.12.2019

Студворк — интернет-сервис помощи студентам

Дана плоская страна и в ней n городов. Нужно соединить все города телефонной
связью так, чтобы общая длина телефонных линий была минимальной. Уточнение задачи. В декартовой системе координат положение i-го города, i = 1,...,n, задано парой координат (x[i],y[i]). d[i,j] - декартово расстояние между i-ым городом и j-ым
городом , j=1,...,n. В задаче речь идет о телефонной связи, т. е. подразумевается
транзитивность связи: если i-й город связан с j-ым, а j-ый с k-ым, то i-й связан с k-ым. Подразумевается также, что телефонные линии могут разветвляться только на телефонной станции, а не в чистом поле. Наконец, требование минимальности (вместе с транзитивностью) означает, что в искомом решении не будет циклов. В терминах теории графов задача Прима-Краскала выглядит следующим образом:
Дан граф с n вершинами; длины ребер заданы матрицей (d[i,j]), i,j = 1,...,n. Найти остовное дерево минимальной длины. Как известно, дерево с n вершинами имеет n-1 ребер. Оказывается, каждое ребро надо выбирать жадно (лишь бы ни возникали циклы).
Алгоритм Прима-Краскала
(краткое описание)
В цикле n-1 раз делай:
выбрать самое короткое еще не выбранное ребро при условии, что оно не образует цикл с уже выбранными.
Выбранные таким образом ребра образуют искомое остовное дерево.
Напишите программу для решения задачи Прима-Краскала.

Prolog
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
%ищет оптимальную конфигурацию
launch:-
write_ln('Города:'), read(X),
write_ln('Расстояния между городами:'), read(Y),
city(X,Y,Z),
write_ln('Оптимальная конфигурация телефонной связи:'),
write(Z).
 
launch:-
write_ln('Невозможно связать города телефонной связью').
 
%ищет соединение минимальной длины
%
%Z1 - выбранные ребра,
%Y- список ребер
%Z2 - результат
minimum([],Z,Z):- !.
 
minimum([[X1,X2,_]|Y],Z1,Z2):-
not(search(X1,X2,Z1,[X1])),!,
minimum(Y,[[X1,X2]|Z1],Z2).
 
minimum([_|Y],Z1,Z2):- minimum(Y,Z1,Z2). %пропустить ребро
 
%реализует поиск пути от вершины Х1 к вершине Х2
%алгоритм поиска - поиск в глубин7у.
%где, Y - список ребер, Z - список вершин (которые пройдены).
search(X1,X2,Y,_):- member([X1,X2],Y).
 
search(X1,X2,Y,_):- member([X2,X1],Y).
 
search(X1,X2,Y,Z):- member([X1,X3],Y),
not(member(X3,Z)), search(X3,X2,Y,[X3|Z]).
 
search(X1,X2,Y,Z):- member([X3,X1],Y),
not(member(X3,Z)), search(X3,X2,Y,[X3|Z]).
 
% реализует вставку в список (с сортировкой)
%
% L1 - список, X - элемент, а L2 - результат
ins(X,[],[X]).
 
ins([X1,X2,R1],[[Y1,Y2,R2]|L],[[X1,X2,R1]|[[Y1,Y2,R2]|L]]):- R1<R2,!.
ins(X,[Y|L1],[Y|L2]):- ins(X,L1,L2).
 
%реализует сортировку вставкой
%
%L - список,Y1 - отсортированный список, а Y3 - результат.
sortrast([],Y,Y). sortrast([X|L],Y1,Y3):- ins(X,Y1,Y2), sortrast(L,Y2,Y3).
 
%соединяет города телефонной связью.
%
%Z - результат X - города, Y - рассояния,
city([X|L],Y,Z):- sortrast(Y,[],Y1), minimum(Y1,[],Z), all(X,L,Z).
 
%проверяет зону охвата всех
%городов телефонной связью
% x -город, Z - список ребер L - список городов
all(_,[],_).
all(X,[Y|L],Z):- search(X,Y,Z,[X]),!,all(X,L,Z).

вроде как надумала:

Python
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
matr = [
         [0, -1, 15, 20, 15], 
         [-1, 0, 60, 50, 80], 
         [15, 60, 0, 50, 10], 
         [20, 50, 50, 0, 30], 
         [15, 80, 10, 30, 0]
       ]
def search_min(tr, vizited):
    min=max(tr)
    for ind in vizited:
        for index, elem in enumerate(tr[ind]):
            if elem>0 and elem<min and index not in vizited:
                min=elem#веса путей
                index2=index# индекс города
    return [min, index2]
 
def prim(matr):
    toVisit=[i for i in range(1,len(matr))]# города кроме начального(0)
    vizited=[0]
    result=[0]# 
    for index in toVisit:
        weight, ind=search_min(matr, vizited)
        result.append(weight)#в результат будут заноситься веса
        vizited.append(ind)# содержит карту пути
    return result

Новые блоги и статьи Все статьи Все блоги /
Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .
Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .