Пятница, 01 Ноября 2024, 09:19

Приветствую Вас Гость

[ Новые сообщения · Игроделы · Правила · Поиск ]
  • Страница 1 из 1
  • 1
Наикратчайший путь по весу
DeswingДата: Пятница, 13 Декабря 2013, 02:44 | Сообщение # 1
заслуженный участник
Сейчас нет на сайте
Привет всем! По сути речь идет о алгоритме Дейкстры.
Сам я пытался решить, но только под конец понял, что решил далеко не то, что надо было, ведь я получил далеко не самую меньшую сумму весов:
Код
#include <iostream>
#include <stdio.h>
#include <time.h>
using namespace std;

const int n = 26;
const int size = n*n;
int* map = new int[size];
FILE* stream;

int pos_read(int x, int y)
{
   return map[y*n+x];
}

void pos_write(int x, int y, int c)
{
    map[y*n+x] = c;
}

class Player
{
private:
   int x, y;
public:
   int buffer,rec;
   Player()
   {
    x = 0, y = 0, buffer = pos_read(x,y), rec = 0;
    pos_write(x,y,-1);
    Logic(n-1,n-1);
   }
   void Logic(int kx, int ky)
   {
    rec++;
    if((x>=kx)&&(y>=ky))
    {
     return;
    }
    if((y!=ky)&&(x!=kx))
    {
     if((pos_read(x+1,y)>=pos_read(x,y+1)))
     {
      y++;
      buffer+=pos_read(x,y);
      pos_write(x,y,-1);
     }
     else
     {
       x++;
       buffer+=pos_read(x,y);
       pos_write(x,y,-1);
     }
    }
    else
    {
     if(x>=kx)
     {
      y++;
      buffer+=pos_read(x,y);
      pos_write(x,y,-1);
     }
     else
     {
      x++;
      buffer+=pos_read(x,y);
      pos_write(x,y,-1);
     }
    }
    Logic(kx,ky);
   }
};

int main(void)
{
   srand(time(false));
   clock_t t0 = clock();
   printf("Generating matrix...\n");
   for(int i = 0; i < size; i++)
   {
    map[i] = rand()%20+10;
   }
   printf("Generated!:\n");
   for(int i = 0; i < n; i++)
   {
    for(int u = 0; u < n; u++)
    {
     cout<<pos_read(u,i)<<" ";
    }
    printf("\n");
   }
   printf("Saving matrix...\n");
   printf("Trying to open matrix.txt\n");
   stream = fopen("matrix.txt","w");
   if(stream == NULL)
   {
    printf("ERROR: Cannot open matrix.txt\n");
    return 1;
   }
   else
   {
    printf("matrix.txt opened successfully\n");
   }
   for(int y = 0; y < n; y++)
   {
    for(int x = 0; x < n; x++)
    {
     fprintf(stream,"%d",pos_read(x,y));
     fputc(' ',stream);
    }
    fputs("\n",stream);
   }
   printf("Matrix saved!\n");
   fclose(stream);
   printf("matrix.txt closed successfully\n");
   printf("Building path...\n");
   Player *A = new Player;
   printf("Result:\n");
   for(int i = 0; i < n; i++)
   {
    for(int u = 0; u < n; u++)
    {
     cout<<pos_read(u,i)<<" ";
    }
    printf("\n");
   }
   printf("Value:%d \n",A->buffer);
   printf("Recursions:%d \n",A->rec);
   delete A;
   printf("Saving the coordinates of moves\n");
   stream = fopen("path.txt","w");
   for(int y = 0, i = 0; y < n; y++)
   {
    for(int x = 0; x < n; x++)
    {
     if(pos_read(x,y)==-1)
     {
      i++;
      fprintf(stream,"%d",i);
      fputc(':',stream);
      fprintf(stream,"%d",x);
      fputc(' ',stream);
      fprintf(stream,"%d",y);
      fputs("\n",stream);
     }
    }
   }
   fclose(stream);
   printf("ALL DONE!\n");
   clock_t t1 = clock();
   cout<<"Generation time: "<<(double)(t1-t0)/(double)CLOCKS_PER_SEC<<" sec."<<endl;
   system("PAUSE");
   return 0;
}

В связи с этим начал читать о графах, деревьях... И назрели вопросы:
Пусть дана матрица NxN (массив), тогда:
1)Сколькими способами из точки А(x1,y1) можно добраться в точку Б(x2,y2) (при условии, что x1!=x2,y1!=y2, и нельзя ходить в посещенные клеточки. Ходить можно вправо\влево\вниз\вверх и по диагоналям)?
2)Зная кол-во возможных путей можно их каким-то образом перебрать и сохранить сумму в ячейке результирующей матрицы... Как это сделать? Интересует именно обход каждый раз новых путей без повторений

Добавлено (13.12.2013, 02:44)
---------------------------------------------
P.S. в моем коде используется рекурсия, т.к. данную задачу по условию нужно решить с её использованием

Сообщение отредактировал Deswing - Пятница, 13 Декабря 2013, 02:42
GECKДата: Пятница, 13 Декабря 2013, 11:30 | Сообщение # 2
заслуженный участник
Сейчас нет на сайте
Ну во-первых это очень странный Дейкстра smile Больше напоминает жадный покоординатный спуск.
Вопрос на засыпку: что именно представляют собой числа в твоей матрице? Дейкстра на вход принимает граф со стоимостью переходов, а не со стоимостью вершин.


Всё гениальное просто. И хреново работает.
DeswingДата: Суббота, 14 Декабря 2013, 02:27 | Сообщение # 3
заслуженный участник
Сейчас нет на сайте
GECK, числа в ячейках - вес соответствующих ячеек. Задача такова: добраться из А в Б, но при этом набрав наименьший вес
  • Страница 1 из 1
  • 1
Поиск:

Все права сохранены. GcUp.ru © 2008-2024 Рейтинг