Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > обход 'графа'

Автор: chaos 9.12.2004, 13:47

Дали сегодня вот такую задачку см. ниже
Вот решил поделится условием и послушать что люди скажут по этому поводу
http://wlpr.fatal.ru/1.gif

Автор: Akina 9.12.2004, 14:13

ну и что? убери числа из узлов и проставь их произведения на ребрах - в результате заменишь поиск суммы произведений на поиск суммы. А дальше задача совершенно тривиальнаЯ.

Автор: chaos 9.12.2004, 14:37

Цитата(Akina @ 9.12.2004, 14:13)

спасибо за совет

Автор: chaos 9.12.2004, 15:11

Цитата(Akina @ 9.12.2004, 14:13)

чето не доходит smile

Автор: Fedor 9.12.2004, 19:02

ИМХО, поиск в ширину. Идешь из старта волной. Просматриваешь все смежные вершины с текущей. Если произведение текущей вершины на смежную плюс найденная максимальная сумма в этой вершине больше чем уже найденная (либо еще не найденная нулевая) то записываем в новую матрицу и продолжаем обход.

З.Ы. Могу алгоритм написать если нужно. Только завтра уже.

З.З.Ы. Насколько я понял, дважды в одной вершине нельзя быть?

Автор: Akina 9.12.2004, 19:33

Цитата(chaos @ 9.12.2004, 16:11)

чето не доходит

Чего не доходит? число на ребре = стоимости маршрута. Задача коммивояжера, тоько поиск не опимума, а заданного значения.

Автор: chaos 10.12.2004, 14:33

Цитата(Morpheus @ 9.12.2004, 19:02)

поделись алгоритмом есл не жалко,
а по поводу "дважды в одной вершине нельзя быть?" по моему можно раз в условии не сказано smile

Автор: Fedor 10.12.2004, 18:06

Цитата(chaos @ 10.12.2004, 13:33)

а по поводу "дважды в одной вершине нельзя быть?" по моему можно раз в условии не сказано

ну тогда я кроме перебора с возвратами пока не могу придумать решение.

Автор: chaos 13.12.2004, 12:30

Цитата(Morpheus @ 10.12.2004, 18:06)

Цитата(chaos @ 10.12.2004, 13:33)

а по поводу "дважды в одной вершине нельзя быть?" по моему можно раз в условии не сказано

ну тогда я кроме перебора с возвратами пока не могу придумать решение.

а если дв каждой вершине можно быть только раз у тя есть какоенибудь решение??
А то что то у меня не получается smile

Автор: chaos 15.12.2004, 09:38

помогите люди!!!

Автор: chaos 15.12.2004, 12:30

Цитата(Morpheus @ 9.12.2004, 19:02)

Выяснил. В каждой вершине можно быть по разу
Добавлено @ 12:31
smile

Люди ну помогит хоть ктонить

Автор: Akina 15.12.2004, 13:29

Цитата(chaos @ 15.12.2004, 13:30)

Люди ну помогит хоть ктонить

Начинай делать и задавай КОНКРЕТНЫЕ вопросы. За тебя делать - влом.

Или шагай в раздел "Работа" и заказывай.

Автор: chaos 16.12.2004, 16:07

подскажите хоть с чего начать то

Автор: Vladimir13 17.12.2004, 03:52

сначала как уже сказали - замена узловых значений реберными ( подсчет произведения каждого ребра ). потом смотришь куда ты можешь пойти с данной точки - запоминаешь все значения. Далее смотришь куда можешь пойти из тех точек, если сначала пошел в первую выбранную... и т.д. в результате запоминаешь суммы. Перед "шагом" надо проверять вершину на четность ( т.к. если с ней грничит <2 ребер, то мы с нее уже не выйдем. Там еще нолики есть -это тоже упрощает дело. Надеюсь, я понятно объяснил.

Автор: chaos 17.12.2004, 10:30

Код


void beatVertex(int a)
{
   int b;
   printf("%d\n",a);
   if (a == (vEND-1)) {printf("return\n"); return;}


   for (int m=0; m<vertex[a].node; m++)
      if (vertex[a].vicinal_from_beat[m]) printf("1 "); else printf("0 ");

   printf("\n");

   for (int n=0; n<vertex[a].node; n++)
   {
      //printf(" %d\n", vertex[a].vicinal_from[n]);
      if (!vertex[a].vicinal_from_beat[n])
      {	
          //printf("  %d\n", a);
          vertex[a].vicinal_from_beat[n] = true;
  	
           b = vertex[vertex[a].vicinal_from[n]].isVretex(a);
           //printf("    %d\n", b);
           vertex[vertex[a].vicinal_from[n]].vicinal_from_beat[b] = true;

           beatVertex(vertex[a].vicinal_from[n]);
      }
   }
}

вот я лгоритмик набросал, но он глючный smile

Автор: chaos 17.12.2004, 18:15

Вот еще переписал вроде для малого кол-ва точек работает, а решил для 30, все писец загнулось smile

(

Код


#include <stdio.h>
#include <conio.h>

#define MAX 30

int cMatrix[MAX][MAX];
int pMatrix[MAX*MAX];
int Weight[MAX];
int hod[MAX*MAX];
int ss = 0, N=0, vS, vE;
char *FILENAME = "c:\\graphp.txt";


void init()
{
	int q;
	FILE *f = fopen(FILENAME, "r");
	fscanf(f,"%d\n",&N);
	fscanf(f,"%d %d\n", &vS, &vE);
	for (int i=0; i<N; i++)
  for (int j=0; j<N; j++)
  {
  	fscanf(f,"%d", &q);
  	cMatrix[i][j] = q;
  	pMatrix[i*N+j] = 0;
  	hod[i*N+j] = 0;
  }
	for (i=0; i<N; i++)
	{
  fscanf(f,"%d", &q);
  Weight[i] = q;
	}
	fclose(f);
}


int rez()
{
	int s=0;
	for (int n=0; n<ss-1; n++)
  s += Weight[hod[n]]*Weight[hod[n+1]];
	return s;
}


void beanGraph(int s, int e, int *m)
{
	int mm[MAX][MAX], mmm[MAX], a, b, c;
	hod[ss] = s;	

	ss++;	
	printf("stack = %d\n",ss);
	
	printf("%d\n", s);

	for (a=0; a<N; a++)
	{
  for (b=0; b<N; b++) 
  {
  	mm[a][b] = *(m+a*N+b); 
  	printf("%d ", mm[a][b]); 
  }
  printf("\n");
	}

	for (a=0; a<N; a++) if (mm[e][a]) mm[s][a] = mm[e][a];

	if (s == vE) 
	{
  printf("return\n");
  //if (ss == N)
  //{
  	printf("%d  hod-- ", ss); 
  	for (a=0; a<ss; a++) printf("%d ", hod[a]);
  	printf("    %d", rez());
  //}
  printf("\n");
  //ss -= 1;
  return;
	}

	for (c=0; c<N; c++)
	{

  //printf("---%d\n",s); 
  if (cMatrix[s][c] && mm[s][c]==0)
  {
  	//mm[s][c] = 1;
  	mm[c][s] = 1;
  	for (a=0; a<N; a++)	for (b=0; b<N; b++) mmm[a*N+b] = mm[a][b]; 
  	beanGraph(c,s,mmm);
  	ss -= 1;
  }
  //mm[s][c] = 1;
	}
}



void main()
{
	init();
	beanGraph(vS,vS,pMatrix);
	
}

вормат данных:

кол-во вершин
начальная вершина конечная
матрица смежности
вес каждой вершины

Пример:
4
1 4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
1
2
3
4

Автор: chaos 24.12.2004, 16:12

все написал, и даже работает smile

кому интересно вот исходник на срр

Код


#include <stdio.h>  //подключаем библиотеки
#include <conio.h>  
#include <string.h>  	
#include <process.h>


char **cMatrix;    //описываем указатель
char *pMatrix, *Weight;  //описываем указатели
int N=0, vS, vE, pog, kolvo, skol=0, price, fexit=0;  //описываем переменные
char *FILENAME;        	//описываем указатель на строку


void init()  	//функция инициализации - читает файл с даннывми
{
	int i,j,q;  //описание переменных
	FILE *f = fopen(FILENAME, "r");  //описываем файловую переменную и открываем файл
	fscanf(f,"%d\n",&N);    //читаем из файла кол-во вершин
	fscanf(f,"%d %d\n", &vS, &vE);  //читаем стартовую и финишную вершину
	fscanf(f,"%d %d %d", &price, &pog, &kolvo);	//читаем необходимую цену для поиска пути,
            //погрешность, кол-во путей для поиска 
        	

	Weight  = new char[N];  	//выделяем память для N вершин - матрица весов
	pMatrix = new char[N];  	//выделяем память для N вершин - матрица переходов
	
	cMatrix = new char*[N];  	//выделяем память для 2-х мерного массива

	for (i=0; i<N; i++)    
	{
  cMatrix[i] = new char[N];	//выделяем память для каждой строки матрицы
  for (j=0; j<N; j++)
  {
  	fscanf(f,"%d", &q);  //читаем матрицу смежности
  	cMatrix[i][j] = q;  //записываем в массив
  }
	}

	for (i=0; i<N; i++)
	{
  fscanf(f,"%d", &q);  	//читаем вес вершины
  Weight[i] = q;    //записываем в массив
  pMatrix[i] = 0;    //инициализируем матрицу переходов нулями
	}

	fclose(f);      //закрываем файл
}


int price_tour(char *p)  //функция подсчитывает результат по правилу ab+bc+cd...
{
	int sum=0;    //для суммы
	for (int n=1; n<N; n++) sum += Weight[p[n-1]]*Weight[p[n]];	//считаем
	return sum;    //возвращаем результат
}

void beanGraph(int s, int e, char *m)	//функция обхода графа
{
	if (fexit) return;
	int c,a;      	//описываем переменные
	m[s] = e;      	//записываем в массив переходов очередную вершину

	if (s == vE)      //проверка на достижимость конца пути
	{	
  int f=0;      //описываем переменную
  char *hod = new char[N];  //выделяем память для массива
  for (int x=0; x<N; x++)	if (m[x] == 0) f = 1;//проверка: всели вершины обошли
  if (!f)  	//если все то ...
  {
  	f=0; 
  	for (c=0; c<N; c++)
    for (a=0; a<N; a++) 
    	if (m[a]==c+1)
    	{
//      printf("%d ", a);  
      hod[f++] = a;	//записываем ходы для передачи в ф. price_tour
    	}
  	f = price_tour(hod);	//функция возвращает посчитанный результат
  	if (price <= f+pog && price >= f-pog)	//проверяем на условие
  	{
    if (skol >= kolvo) {fexit=1; return;};	//если необходимые пути найдены то закрываем программу
    skol++;  	
    for (a=0; a<N; a++) printf("%d ", hod[a]);//вывод пути
    printf("price tour = %d\n", f);//вывод цены пути
  	}
  	delete[] hod;	//освобождаем память
  }
  return;	//выход из функции
	}

	char *mmm = new char[N];  //выделяем память

	for (c=0; c<N; c++)  //цикл по смежным вершинам
	{	
  if (cMatrix[s][c] && m[c]==0)  //если не обходили то ...
  {
  	memcpy(mmm, m, N);    //копируем содержимое одного массива в другой
  	beanGraph(c,e+1,mmm);  	//вызываем функцию
  }
	}
	delete[] mmm;  	//освобождаем память
}    

int main(int argc, char *argv[])  //главная функция получает название файла с данными
{
	if (argc == 2)      //проверка на один аргумент
	{
  FILENAME = argv[1];    //имя файла
  init();      	//вызываем функцию	
  beanGraph(vS,1,pMatrix);  //вызываем функцию	
  for(vS=0; vS<N; vS++) delete cMatrix[vS];	//освобождаем память(двумерный массив)
  delete[] cMatrix; //освобождаем память
  delete[] Weight;//освобождаем память
  delete[] pMatrix;//освобождаем память
	}
	else printf("Usage: kgraph.exe file_data.txt\n");//выводим подсказку
	getch();  //ждем нажатия клавиши
	return 0;  //конец
}