Дали сегодня вот такую задачку см. ниже
Вот решил поделится условием и послушать что люди скажут по этому поводу

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Цитата(chaos @ 10.12.2004, 13:33) а по поводу "дважды в одной вершине нельзя быть?" по моему можно раз в условии не сказано ну тогда я кроме перебора с возвратами пока не могу придумать решение.

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

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

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

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

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

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

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

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

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

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

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

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

Код

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]);      }   } }

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

Это сообщение отредактировал(а) podval - 17.12.2004, 17:50

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

Код

#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 - 17.12.2004, 18:34

все написал, и даже работает
кому интересно вот исходник на срр

Код

#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;  //конец }