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

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

Цитата(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