Большой Воронежский Форум Mobile

Здравствуйте!!!
Помогите пожалуйста!
Тут такая проблемма!
Нужно решить задачу о покрытие графа!А именно НАЙТИ НАИМЕНЬШЕЕ ПОКРЫТИЕ ГРАФА(НЕОРЕНТИРОВАННЫЙ,БЕЗ ПЕТЛЕЙ)
То есть необходимо найти минимум ребер с минимальными весами которые покрывают все точки графа!
Ребят может кто сталкивался!
Мне даже программа не нужна а нужен алгоритм по которому ищеться данное покрытие!

Тут на форуме вроде как данная тема была,но там только листинг программы есть...

СПАСИБО! [Ответ]

Ребер не обязательно должен быть минимум))) Девять ребер по 1 - меньше чем одно с 10. Это раз.
Задача эта решается перебором. Алгоритм состоит из следующих частей
1. Найти первое решение, любое.
2. Оценить его.
3. Начать перебор всех остальных вариантов.
4. Оценивать каждый вариант, если он лучше предыдущего лучшего, запоминать оценку и путь.

Основная и единственная сложность - грамотно построить перебор, чтобы он
а) рассмотрел все варианты
б) не зациклился

Задача эта на самом деле не про графы))) А про циклы с вложенностью N, где N на этапе разработки неизвестно. Решается она следующим образом - вводится МАССИВ ИНДЕКСОВ, и переменная, которая отвечает за уровень, на котором мы находимся.
Проще будет объяснить на примере:
[0-3]
0 0
0 1
0 2
0 3
1 0
1 1
1 2
1 3
...
Здесь N = 2, соответственно для индексов нужен массив из двух элементов. [Ответ]

Спасибо но чесно говоря мне не совсем понятно все что тут написано..
Вот например есть какой то граф...для него строим матрицу инцидентности...Затем как я представляю я должен работать с этой матрицей,ну и соответственно программа которая будет написана!В матрице единицы и нули и с ними должна соотвестсвенно работать программа!
Или не так?Я наверно вообще не то говорю... [Ответ]

Сообщение от Puzen:
Спасибо но чесно говоря мне не совсем понятно все что тут написано..
Вот например есть какой то граф...для него строим матрицу инцидентности...Затем как я представляю я должен работать с этой матрицей,ну и соответственно программа которая будет написана!В матрице единицы и нули и с ними должна соответственно работать программа!
Или не так?Я наверно вообще не то говорю...

Для простоты объявляем матрицу N x N, где N - количество вершин.
Граф неориентированный, значит заполняем нулями всю матрицу, потом выставляем единички в парах I-J, J-I, где каждые I, J - пара соединенных узлов.
С этой матрицей мы будем работать дальше. Каким образом?
Проще всего - рекурсивно. Соединяем любой узел с любым узлом, спускаемся на уровень ниже, там соединяем любой уровень с любым узлом, спускаемся ниже и т.д. На каждом этапе проверяем
а) Достигли мы цели
б) Есть ли куда двигаться дальше

Если достигли цели - путь найден. Если двигаться дальше некуда - нужно просто вернуть FALSE (облом) и алгоритм пойдет дальше искать решение. Сложность только в том чтобы неудачные обходы можно было откатить назад. Но это уже сами, иначе надо будет алгоритм расписывать вплоть до деталей. Это уже только за денежку.

Ой, Вам не путь надо найти, а покрыть весь граф. Тогда задача усложняется - перебор надо делать еще и по всем стартовым точкам. Но это не страшно, на самом деле. Просто приведенный выше алгоритм надо будет повторить в цикле для всех точек графа. [Ответ]

Так уже яснее...
Благодарю...
Вопос вот еще какой а если нам дана не матрица смежности а матрица инцидентности?
Есть какие варианты?
Просто мне необходимо оперировать именно матрицей инцидентности... [Ответ]

Чесно говоря ситуация вот какая у меня есть программа а вот алгоритм ее работы не могу понять вот поэтому и пришел сюда-узнать какие методы решения данной задачи существуют... [Ответ]

Сообщение от Puzen:
Так уже яснее...
Благодарю...
Вопос вот еще какой а если нам дана не матрица смежности а матрица инцидентности?
Есть какие варианты?
Просто мне необходимо оперировать именно матрицей инцидентности...

Будем разбираться, тэк.
Инцидентность — понятие, используемое только в отношении ребра и вершины: если v1,v2 — вершины, а e = (v1,v2) — соединяющее их ребро, тогда вершина v1 и ребро e инцидентны, вершина v2 и ребро e тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Для обозначения ближайших вершин (рёбер) используется понятие смежности.

Таким образом, инцидентность - это просто информация о том что вершина связана с ребром.
На основе этой информации мы и
Граф неориентированный, значит заполняем нулями всю матрицу, потом выставляем единички в парах I-J, J-I, где каждые I, J - пара соединенных узлов.
Каким образом? На основании ребер и таблицы инцидентности нужно построить вышеупомянутую матрицу.
Перебираем все вершины вложенным ТРИ раза циклом и смотрим - есть ли связь между Iтой и Jтой вершиной в Ктой записи (этой самой инцедентности), если она есть, значит выставляем в матрице единичку. Или две штуки - туда и назад, если связь ненаправленная. [Ответ]

Ладно... СПАСИБО большое...
Все таки попытаюсь сначала придумать как находить с помошю матрицы инциндентности..если не выйдет то как вы сказали попробую сделать.... [Ответ]

Сообщение от Puzen:
Ладно... СПАСИБО большое...
Все таки попытаюсь сначала придумать как находить с помошю матрицы инциндентности..если не выйдет то как вы сказали попробую сделать....

Не за что)))
Да там алгоритм не сильно меняется. Просто немного другая структура данных. Совместите мой алгоритм и данные в формате матрицы инцедентности, да и все. [Ответ]

Ладно попробую...
Спасибо... [Ответ]

Так....короче сам не смог ничего придумать...стал анализировать программу которая у меня имеется и все может расчитывать...но есть кое что непонятное-поясните пожалуйста что могут означать данные строки:

//Формирование блоков таблицы
i:=0;j:=0;
repeat
k:=0;
repeat
if datatab[i,j]=1 then
begin
jj:=0;
setlength(C[j],k+1);
c[j][k]:=ves[i];
setlength(P[j],k+1,n);
repeat
p[j][k,jj]:=datatab[i,jj];
jj:=jj+1;
until jj>n-1;
k:=k+1;
end;
i:=i+1;
until i>m-1;
j:=j+1;
i:=0;
until j>n-1;

KDataTab:=DataTab;
KVes:=Ves;

//Поиск
setlength(E,n);kp:=1;
for i:=0 to n-1 do E[i]:=0;
k:=0;z:=0;zz:=1.7*power(10,38);B:=nil;
i:=0;
while i<=n-1 do
begin
if E[i]=0 then
begin
j:=-1;
l2:repeat
j:=j+1;
if j>high(P[i]) then goto l1;
until z+c[i,j]<=zz;
K:=k+1;setlength(B,k);
z:=z+c[i,j];B[k-1,0]:=i;
B[k-1,1]:=j;
for r:=i to n-1 do
if p[i][j,r]=1 then E[r]:=1;
end;
i:=i+1;
end;
//Удалить в листинге
if zz=z then kp:=kp+1;
zz:=z;BB:=B;
l1: if B=nil then begin

...
Хотя бы приблизительно...Спасибо... [Ответ]

Puzen, i:=0;j:=0; это алгоритм Кнута - Морриса -Пратта
В интеренете посмотрите там есть подробное описание

borlpasc.narod.ru/docym/shay/practice/2_6/2_6_4.htm
Там можно поискать,просто долго рассказывать по каждой строчке. [Ответ]

Сообщение от SKYnet_Main boss:
Puzen, i:=0;j:=0; это алгоритм Кнута - Морриса -Пратта
В интеренете посмотрите там есть подробное описание

borlpasc.narod.ru/docym/shay/practice/2_6/2_6_4.htm
Там можно поискать,просто долго рассказывать по каждой строчке.

ТАк спасибо щас посмотрюю...
Отпишусь... [Ответ]