Форум программистов, компьютерный форум CyberForum.ru

Поиск остовного леса методом Соллина - C++

Восстановить пароль Регистрация
 
Vaste
1 / 1 / 0
Регистрация: 23.04.2012
Сообщений: 42
03.05.2013, 08:25     Поиск остовного леса методом Соллина #1
Доброго времени суток. Передо мной встала задача найти остовной лес минимальной стоимости методом Соллина. Интернет предложил единственный вариант реализации данного алгоритма (приведён ниже). Сразу скажу, ошибка в том, что он не делает разницы было ли рассмотрено ребро или нет (т.е. 2 раза рассмотреть одно и то же ребро, от начальной вершины к конечной и наоборот). Соответственно, к результирующей стоимости леса дважды добавляет одно и то же ребро. Кто в курсе как исправить - буду рад идеям.
C++
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
/*
Поиск остовного леса минимального веса методом Соллина
(длины ребер - расстояния между точками) вершины графа - точки плоскости.
Алгоритм Соллина построения дерева минимального веса.
1. Соединить каждую вершину с ее ближайшим соседом.
2. Удалить ребра, соединяющие вершины из одной компоненты связности полученного леса.
Рассмотреть каждую из этих компонент как отдельную вершину. Перейти к 1.
*/
#include <stdlib.h>
#include <conio.h>
#include <stdio.h>
#include <math.h>
 
#define KT 6    //число точек
 
int koord[KT][2] ={{5,5},{5,7},{8,6},{2,6},{3,3},{7,3}};    //координаты точек
 
int edges[14][2]={ //массив рёбер в формате "начальная вершина - конечная вершина"
       {0,1},
       {0,3},
 
       {1,0},
       {1,3},
 
       {2,4},
       {2,5},
 
       {3,0},
       {3,1},
       {3,4},
 
       {4,2},
       {4,3},
       {4,5},
 
       {5,2},
       {5,4}};
int kol = 0; //порядковый номер вершин графа
float resultweigth = 0;
struct Arrow;
//Структура вершин графа
struct Vertex
{
    Arrow *first; //если из вершины выходит связь
    int x, y;         //точки
    int number;     //номер точки
    Vertex *next;       //следующая вершина
} *start_Vertex = NULL;
//Структура ребра
struct Arrow
{
    Vertex *end;        //вершина, с которой связь
    double lengh;     //вес
    Arrow *next;      //если есть еще связи
};
//Создаем вершины
void add_Vertex (int i)
{
    Vertex *p = new (Vertex);
    p->first = NULL;
    p->next = NULL;
    p->x = koord[i][0];
    p->y = koord[i][1];
    p->number = kol++; //порядковый номер добавляемой вершины
    if (start_Vertex == NULL) //если добавляется первая вершина
       start_Vertex = p;
    else //если не первая
    {
        Vertex *tmp=NULL;
        tmp = start_Vertex;
        while (tmp->next) //доходим до последней вершины
              tmp = tmp->next;
        tmp->next = p; //присваиваем её указателю на следующую вершину
    }                  //адрес новосозданной вершины
}
//Связываем вершины
void add_arrow (int start, int end)
{
    int x, y;//переменные под (x-x0) и (y-y0)
    Arrow *p = new (Arrow);
    Vertex *st = start_Vertex, *ed = start_Vertex;
 
    for (x = 0; x < start; x++)
        st = st->next;          //находим узел, из кот-го выходит ребро
    for (y = 0; y < end; y++)
        ed = ed->next;          //находим узел в кот-ю входит ребро
 
    x = ed->x - st->x; //координата х вектора
    y = ed->y - st->y; //координата y вектора
 
    p->next = NULL;
    p->end = ed;
    p->lengh = sqrt(x * x + y * y); //длина между точками
 
    if (st->first == NULL)  //аналогично добавлению вершины
       st->first = p;           //добавлять для ed не надо, т.к. матрица
    else                    //симметрична
    {
      Arrow *tmp;
      tmp = st->first;
      while (tmp->next)
        tmp = tmp->next;
      tmp->next=p;
    }
}
 
void sollin(void)
{   //алгоритм Соллина
 double min=100;//эталонный вес ребра
 int startnumber,endnumber;//индексы начала и конца вершин
 Vertex *startvertex,*endvertex;
 Arrow *edge;
 startvertex=start_Vertex;
 endvertex=start_Vertex;
  //идем по вершинам
    while(startvertex)
  {
        edge=startvertex->first; min=100;
    //идём по рёбрам
    while(edge)
    {
      if(edge->lengh<min)
        {   //поиск минимального ребра
          min=edge->lengh;
          endvertex=edge->end;
                }
            startnumber=startvertex->number;
            endnumber=endvertex->number;
            edge=edge->next;
    }
        printf("\nStart: %d ",startnumber);
        printf("End: %d",endnumber);
        printf("\tMin weigth = %f",min);
    resultweigth+=min;
      startvertex=startvertex->next;
    }
} 
void print(void)
{       //вывод вершин и связей
    Vertex *tmp = start_Vertex;
    Arrow *ar = NULL;
    while (tmp)
    { //идём по вершинам
      printf ("%d vertex is connected with: \n", tmp->number);
      if (!(tmp->first))
        printf ("No connection");
      else
      {
        ar = tmp->first;
        while (ar)
        {
          printf ("\t%d (Weigth: %4.3f)\n", ar->end->number, ar->lengh);
          ar = ar->next;
        }
      }
      tmp = tmp->next;
    }
} 
 
void main()
{
  int i, j, k=0;
  system("cls");
  for (i = 0; i < KT; i++)
    add_Vertex (i);
  for (i = 0; i < KT; i++)
    for (j = 0; j < KT; j++)
      for(k = 0; k < 14; k++)
        if ((i == edges[k][0]) && (j == edges[k][1]))
          add_arrow (i, j);
  print(); //распечатка вершин и рёбер
  printf("\nAfter Sollin-ing\n");
  sollin(); //поиск остовного дерева
  printf("\n Total weigth = %.3f",resultweigth);
  getch();
}
Для администрации: не нашёл подобную тему, вот и создал новую. Если будет необходимо - перенесите куда надо, буду благодарен.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
03.05.2013, 13:30     Поиск остовного леса методом Соллина #2
есть идея написать нормальный алгоритм с меньшей вычислительной сложностью...
Vaste
1 / 1 / 0
Регистрация: 23.04.2012
Сообщений: 42
03.05.2013, 13:57  [ТС]     Поиск остовного леса методом Соллина #3
Требуется именно Соллин. нашёл тока этот. есть идеи насчёт другого - выслушаю.
iifat
2179 / 1332 / 96
Регистрация: 05.06.2011
Сообщений: 3,692
03.05.2013, 14:44     Поиск остовного леса методом Соллина #4
Странно как-то. Где остовной лес? Где вычёркивание рёбер? Могу ошибаться (О! Ещё как могу!), но, по-моему, ты кую-то фигню полную нашёл.
Vaste
1 / 1 / 0
Регистрация: 23.04.2012
Сообщений: 42
03.05.2013, 14:59  [ТС]     Поиск остовного леса методом Соллина #5
Сам лес тут как таковой не формируется. Просто ищутся минимальные рёбра для каждой из точек.

Добавлено через 5 минут
Вообще блин не понимаю чё за алгоритм соленовский такой. "Удалить рёбра одной компоненты связности..." (чё, в итоге куча свободных вершин будет?), "рассмотреть каждую компоненту связности как новую вершину..." (это как? множество вершин как одну вершину рассмотреть?? или я дурак или чё-то тут не вяжется...)
iifat
2179 / 1332 / 96
Регистрация: 05.06.2011
Сообщений: 3,692
03.05.2013, 15:09     Поиск остовного леса методом Соллина #6
А, так это промежуточный вариант? Ну, тогда осталось начать и кончить: продумать представление леса, найденные рёбра надо сразу вычёркивать, дабы не просматривать второй раз (точнее говоря, при слиянии двух кустов вычёркивать все рёбра между ними).
Я б таки посоветовал переписать полностью. Представление графа вполне, конечно, логичное, но для данной задачи весьма неудобное. Имхо, завязать рёбра в единый список (упорядоченный по возрастанию весов), в каждой вершине хранить номер минимальной вершины своего куста. Отдельный список для выбранных рёбер.

Добавлено через 4 минуты
Ну, примерно так: вот взяли ребро (с минимальным весом); две вершины, которые оно соединяет, стягиваем в одну, удаляя из графа наше ребро и все остальные, кои соединяют эти вершины; прочие рёбра, которые вели из любой из этих вершин, меняем на аналогичные, соединённые с нашей новой вершиной (при этом могут появиться многократные рёбра из одной вершины в другую). Повторяем, пока не останется всего одна вершина.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.05.2013, 02:14     Поиск остовного леса методом Соллина
Еще ссылки по теме:

Поиск методом аппроксимации C++
Поиск бинарным методом C++
Вырубка леса C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Vaste
1 / 1 / 0
Регистрация: 23.04.2012
Сообщений: 42
04.05.2013, 02:14  [ТС]     Поиск остовного леса методом Соллина #7
Ладно, будем думать....
Yandex
Объявления
04.05.2013, 02:14     Поиск остовного леса методом Соллина
Ответ Создать тему
Опции темы

Текущее время: 05:21. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru