algorytm zachłanny poszukiwania drogi

mając taką macierz NxN gdzie N = 5

5
2 3 4 2 5
5 2 1 2 2
2 4 2 2 3
1 2 2 4 3
3 2 1 2 3

muszę z lewego dolnego rogu dojść do prawego górnego rogu normalnie bym to zrobił

for(int i = 0; i < N; i++)
        {
            cout <<  i << " " << N-1-i << '\n';
        }

i droga by wyglądała

3 2 2 2 5

ale ze jest to algorytm zachłanny muszę poruszać się drogą po mniejszych wartościach np.

3 1 2 4 2 1 2 2 5

mając taki przepis proszę o pomoc w napisanu go w c++

1. ustawiasz start na [N - 1][0] => lewy, dolny róg.
2. sprawdzasz, który z kierunków zawiera miejszą wartość - czy w górę, czyli [N - 1 - 1][0], czy w prawo, czyli [N -1][1]
   2a) może nastąpić przypadek, że po drodze dojdziesz do wiersza 0, albo kolumny N - 1. Od takiego momentu możliwy jest tylko ruch w prawo (dla wiersza 0), albo w górę (dla ostatniej kolumny), musisz to uwzględnić w algorytmie.
3. przestawiasz start na znaleziony w punkcie 2 indeks, i powtarzasz krok 2 póki nie dojdzie do [0][N - 1] => prawy, górny róg

No dobra, wiesz jak to rozwiązać - to dlaczego tego nie zapiszesz w kodzie?

Właśnie nie wiem jak to przełożyć na kod w c++, to prawda MasterBLB pomysł zaczerpnąłem od Ciebie, a że uczę się o algorytmie zachłannym bardzo pomógł mi post w którym brałeś udzial, prosiłbym o pomoc jeszcze raz nie za bardzo rozumiem te zapisy [N - 1][0] itp.. w sensie rozumiem ale nie wiem jak przełożyć je na kod

Pytanie pomocnicze, czym może być N w zaproponowanym rozwiązaniu?

było, pewnie koleżanka z grupy: https://4programmers.net/Forum/C_i_C++/321600-zachlanny_algorytm_poszukiwania_drogi_w_podanej_tablicy_pomoze_ktos_w_rozwiazaniu?p=1561091#id1561091

tylko ze problem jest zupełnie inny niż koleżanki bo ona miała problem z otwarciem pliku mi natomiast zależy tylko na algorytmie a dokładniej pomocy w przelozeniu go na kod..
przemyslowiec N jest to wielkosc macierzy kwadratowej

rozumiem to zacząc w ten sposób:

int tab[100];
        for(int i=0;i<N;i++)
        {
            tab[0]=tablica[N-1][0];
            if(tablica[N-1-1][0]<tablica[N-1][1])
                cout<<tablica[N-1-1][0];
                else cout<<tablica[N-1][1];
        }
}

i wlasnie uwazam ze to co pisze jest bez sensu, a nie potrafie go lepiej przelozyc na poprawny kod dlatego proszę o pomoc...

Zauważ, że w tym kodzie:

        for(int i=0;i<N;i++)
        {
            tab[0]=tablica[N-1][0];
            if(tablica[N-1-1][0]<tablica[N-1][1])
                cout<<tablica[N-1-1][0];
                else cout<<tablica[N-1][1];
        }

N razy odwołujesz się do dokładnie tych samych pól tablicy. N się nie zmienia przecież.

Przez N oznaczyłem wielkość kwadratowej tablicy 2-wymiarowej NxN, od tego zacznijmy. W takim układzie indeksy wierszy oraz kolumn zawierają się w <0, N - 1> => stąd wspomniane w przepisie [N - 1][0] => lewy, dolny róg a to dlatego, że [N - 1][0] oznacza maksymalny możliwy wiersz oraz pierwszą kolumnę.

Zatem nalezało by zacząc od

for(int i=N-1;i>=0;i--)

i nie wiem czy druga pętla teraz jest potrzebna zaczynajaca od 0 czy może od razu warunek sprawdzający ?

Potrzebne jest coś w rodzaju wskaźnika na początkowy element oraz możliwe, iż dodatkowych zmiennych, tak abyś dla tablicy 5x5 mógł zrobić porównanie:
pointer[4 - 1][0] < pointer[4][1]? Jeśli tak to pointer nastaw na [4 - 1][0], jeśli nie to na [4][1]. I powtarzasz to aż pointer będzie wskazywał na [0][4]

Z tego co napisałeś udało mi się napisać to

int *pT;
        for(int i=N-1;i>=0;i--)
        {

            pT=&tablica[N-1][0];
        for (int i=0; i<N; i++)
        if (pT[N-1][0] < pT[N-1][i])
           * pT = pT[N-1][i];
   

        }

Ale wyswietlil mi się bląd i nie potrafie go naprawić proszę o pomoc

Nie jesteśmy jasnowidzami, ino programistami - jak nie pokażesz komunikatu błędu, oraz pełnego kodu programu to nie podpowiemy, co jest nie tak.

Kod jeszcze do poprawy w tym kodzie wyswietlaja się tylko indeksy przejścia po przekątnej i koszt ich pod dodaniu wartości, problem jest z tymi porównywaniami

#include <iostream>
#include<fstream>
#include<cstdlib>

using namespace std;

int main()
{

    fstream plik;
    int N;
    plik.open("dane.txt",ios::in);
    if(plik.is_open())
    {
        plik >> N;
        cout << "wczytana wielkosc tablicy: " << N<<endl;
        int ** tablica = new int * [N];
        for(int i=0; i<N; i++)
        {
            tablica[i]=new int [N];
            for(int j=0; j<N; j++)
            {
                plik >> tablica[i][j];
                cout<<tablica[i][j]<<" ";

            }
            cout<<endl;
        }
        int koszt=0;
        for (int i = N - 1, j = 0; j < N; i--, j++)
        {
            koszt+=tablica[i][j];
        }
        cout<<"Koszt: "<<koszt<<endl;

        fstream plik2;
        plik2.open("wynik.txt", ios::out);
        plik2<<"Koszt: "<<koszt<<endl;
        for(int i = 0; i < N; i++)
        {
            plik2  << i << " " << N-1-i  << endl;
            cout <<  i << " " << N-1-i << '\n';
        }

        cout<<endl;
        int *pT;
        for(int i=N-1;i>=0;i--)
        {

            pT=&tablica[N-1][0];
        for (int i=0; i<N; i++)
        if (pT[N-1][0] < pT[N-1][i])
           * pT = pT[N-1][i];


        }



        plik2.close();
    }
    else
    {
        cout << "Blad otwarcia pliku dane.txt!";
    }

    return 0;
}

Hmmm, skoro wyświetlają się indeksy to oznacza, że program się kompiluje i działa - gdzie błąd zatem? Chyba, że masz na myśli iż wykłada SEG FAULT jak dojdzie to wyszukiwania drogi.
Ok, to co tego przeszukiwania.

1. użyta zła pętla. Przede wszystkiem, nie jest prawdą że zakończy się to w N - wyobraź sobie tablicę 5x5 gdzie ścieżka będzie cały czas w prawo, a potem cały czas do góry. Ile wtedy przejść będzie?4x w lewo + 4x do góry, no jak dla mnie to więcej jak 5. Dlatego jako warunek zakończenia pętli należy dać aż pT == &tablica[0][N - 1]; A skoro nie wiemy z góry, ile przebiegów będzie wymagane to stosowniejsze jest użycie pętli while albo do/while

2. Zamiast posługiwać się ciągle N - 1, 0 itd wygodniej będzie utworzyć pomocnicze zmienne indeksujące row i column, a następnie je zainicjować:

int row = N - 1;
int column = 0;

i potem ich używać razem ze wskaźnikiem pT

1. Porównanie masz w miarę ok pomijając źle użyte i z pętli for, ale nie obsługujesz przypadku kiedy to wartość będąca na prawo od bieżącej pozycji jest mniejsza. Więc if powinien wyglądać jakoś tak:

if (pT [wiersz o 1 wyżej niż ma pT][bieżąca kolumna] < pT [bieżący wierz][kolumna o 1 na prawo])
{
    nastaw pT na indeks o 1 w górę;
}
else
{
   nastaw pT na indeks o 1 w prawo
}

3a) uważaj na pułapkę bo może się zdarzyć, że bieżąca kolumna albo zrówna się z N - 1, albo wiersz zmaleje do 0 - w takiej sytuacji odpowiednio dalszy ruch możliwy jest tylko do góry albo w prawo

dziękuję po tablicy możemy się poruszać tylko do góry i prawo a błąd który wciąż się wyswietla to : invalid types'int[int]' for array subript nie mogę sobie z nim poradzic

I znów - w tym kodzie dostępnym nam tutaj nie ma czegoś takiego jak subript - czyli ten kod nie jest już aktualny. Komunikat błędu też niepełny, tutaj nie wiadomo, jakiej linii i komendy dotyczy. Zaktualizuj go zatem Bracie, a komunikat błędu przekopiuj cały tak, jak pokazuje to IDE.

pomyłka napisałem subript zamiast subscript
error: invalid types 'int[int]' for array subscript , a kod wrzuciłem cały

No to znajdź w tym co wkleiłeś jako cały kod identyfikator subscript, bo ja jakoś nie widzę.

błąd wyswietla się w tej linii

if (pT[N-1][0] < pT[N-1][i])

Aaa, bo źle pT zdefiniowany. No dobra, tutaj za dużo by zeszło na klarowaniu czemu tak, oto testowy programik jaki zrobiłem na szybko:

int main()
{
    const int N = 5;
    int **tablica = new int * [N];
    for(int i=0; i<N; i++)
    {
        tablica[i] = new int [N];
    }

    int **pT = tablica + N - 1;

    **pT = 10;

    std::cout << tablica[N - 1][0] << std::endl;//i wypisał mi 10, czyli istotnie wskaźnik jest ustawiony na lewy, dolny róg


    return 0;
}

ehh próbuję cos napisac, ale jest ciężko

int **pT = tablica + N - 1;
        for(int i=N-1; i>=0; i--)
        {

          while()
            {
                if (pT[N-1][0] < pT[N-1][1])
                {
                    pT[i+1]=tablica[i];
                }
                else
                {
                    pT[i+1]=tablica[i];
                }

            }
        }

mam problem z warunkiem i ze zwiększeniem indeksow bo nie wiem czy musze je przypisac do tablicy czy po prostu zwiekszyc je o 1

A co to niby jest według ciebie?

while()

Przecież ten kod się wcale nie kompiluje...

wiem, ze się nie kompiluje bo nie mam pomysłu jaki warunek wstawić i czy w ogole jakiś wstawiac bo nie mam pojęcia ile tu przebiegow petli będzie.. i poprawiłem zmienne ..

int row = N - 1;
 int column = 0;
 int **pT = tablica + N - 1;
        for(int i=N-1; i>=0; i--)
        {

          while()
            {
                if (pT[N-1][0] < pT[N-1][1])
                {
                    pT[row+1][column];
                }
                else
                {
                    pT[row][column+1];
                }

            }
        }

Jeszcze mam pytanie pojawiło się tu sporo niezrozumiałego dla mnie kodu i mam problem z wyświetleniem zawartości, prosiłbym o pomoc,chciałbym zobaczyć co mi wyświetli ten fragment kodu

int row = N - 1;
       int column = 0;
        int **pT = tablica + N - 1;
        for(int i=N-1; i>=0; i--)
        {

                if (pT[N-1][0] < pT[N-1][1])
                {
                    pT[row+1][column];
                }
                else
                {
                    pT[row][column+1];
                }

        }

W sumie, skoro wprowadzamy dodatkowe zmienne row = N - 1 i column = 0 to wskaźnika **pT już nie potrzebujemy, można operować bezpośrednio na tablicy - przestawianie bieżącego indeksu załatwi się zmniejszaniem row i zwiększaniem column.
Mówiłem, że pętla for jest do zastąpienia przez while albo do/while z innym warunkiem, to idziesz w zaparte.
EDIT:
Nudziło mi się, to sobie implementację stworzyłem. Łapta Bracie @dcielak i Siostro @Nency Black: coś na podrażnienie apetytu :]

A poniżej test dla przypadku kiedy ścieżka prowadzi po krawędziach tabeli:

udało mi się tyle napisać, ale warunek w pętli mam beznadziejny bo nie wiem co mam wpisac

 while(table[N-1][0]=table[column][row])
   {
        if(table[row-1][column]<table[row][column+1])
        {
            cout<<"do gory: ["<<row-1<<"]"<<"["<<column<<"]"<<"="<<table[row-1][column]<<" "<<endl;
             table[row-1][column]=table[N-1][0];

        }
        else
        {
            cout<<"w prawo: ["<<row<<"]"<<"["<<column+1<<"]"<<"="<<table[column+1][row]<<" ";
            table[column+1][row]=table[N-1][0];
        }

   }

udało mi się tyle napisać, ale warunek w pętli mam beznadziejny bo nie wiem co mam wpisac

Odpowiedz sobie na pytanie Bracie @dcielak - kiedy chcesz aby ta pętla się zakończyła?

gdy indeksy w tablicy będą się znajdować w punktach [0][N-1], tylko nie wiem jak to ujać w kodzie

dcielak napisał(a):

gdy indeksy w tablicy będą się znajdować w punktach [0][N-1], tylko nie wiem jak to ujać w kodzie

Prawidłowa odpowiedź! Przy czym chodzi o bieżący indeks drogi.
Czyli chcesz, żeby z [N - 1][0] wylądował na [0][N - 1]...hmmm, a czy jakieś pomocnicze zmienne indeksujące były może ustawiane na tą początkową wartość?

i wlasnie tu mam problem chodzi np. o to ?

int start=table[N-1][0];