Zachłanne szukanie drogi w tablicy

[Roundstic 0]

Zaimplementuj zachłanny algorytm poszukiwania drogi w podanej tablicy. Użytkownik podaje liczbę N, i tablicę liczb o wymiarach N x N. Program, z użyciem metody zachłannej, znajduje drogę z lewego dolnego rogu tablicy do prawego górnego rogu i jej koszt. Program wypisuje współrzędne kolejnych pól na drodze w tablicy. Po tablicy możemy poruszać się tylko do góry lub w prawo.

 

Przykład

 

Wejście

 

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

Przykładowe wyjście (może się różnić, w zależności od implementacji)

 

Koszt: 22

4 0

3 0

2 0

2 1

1 1

1 2

1 3

0 3

0 4

 

Sam napisałem jedynie, początek i nie wiem co dalej myślałem nad utworzeniem nowej tablicy

 

#include <iostream>

using namespace std;


int main()
{
   int n;
   int T[100][100];

   cout<<"Podaj liczbe: ";
   cin>>n;

   cout<<"Podaj tablice liczb: "<<endl;
   for(int i=0; i<n; i++)
   {
       for(int j=0; j<n; j++)
       {
           cin>>T[i][j];
       }
   }

   int A[100][100];

[Bono[UG] 1618]

Przede wszystkim czy wiesz jak ma wyglądać algorytm? Czy potrafisz znaleźć drogę mając wyrysowaną tabelę i chodząc palcem po niej?

Czy po poprzednich zadaniach z algorytmów zachłannych rozumiesz na czym polega idea takiej grupy algorytmów, czym jest ta zachłanność?

 

Z tego co na razie masz, to do czego ma służyć ta nowa tablica? W jakim celu ją tworzysz? Co dzięki niej osiągniesz?

[Roundstic 0]

Algorytm powinien wybierać najbardziej optymalną wartość, jednak czasami nie najbardziej opłacalną.

Droga w tablicy powinna wyglądać tak, że pierw idzie od dołu do samej góry i prawego rogu, a potem kolejne komórki powinien wybierać, albo z boku, albo z dołu w zależności od najmniejszej wartości.

Nową tablicę chciałem utworzyć na drogę

[januzi 24]

Nie ma potrzeby tworzenia drugiej tablicy, wszystko możesz pokazać "na żywca".

[Bono[UG] 1618]

Algorytm powinien wybierać najbardziej optymalną wartość, jednak czasami nie najbardziej opłacalną.

Droga w tablicy powinna wyglądać tak, że pierw idzie od dołu do samej góry i prawego rogu, a potem kolejne komórki powinien wybierać, albo z boku, albo z dołu w zależności od najmniejszej wartości.

Nową tablicę chciałem utworzyć na drogę

Algorytmy zachłanne najprościej opisać: bierz najlepsze rozwiązanie w danym momencie i idź dalej.

Tak, wybiera się optymalną wartość ale tylko w danym kroku. Ogólny wynik może być daleki od najlepszego.

 

 

Coś chyba nie do końca zrozumiałeś zadanie lub zbyt skrótowo to teraz opisujesz.

Startujesz z lewego dołu, masz dojść do prawej góry.

Możesz iść w górę lub w prawo.

Trudnością tutaj może być orientacja góra - dół, lewo - prawo względem indeksów tablicy.

 

 

Ok, chcesz zapisać przebytą drogę w tablicy. Po co ci zatem o takich samych rozmiarach, co plansza?

Zapis drogi to kolejne pary liczb, współrzędne położenia. Czyli tablica jeden z wymiarów powinna mieć 2, np. tab[10][2] pozwoli na zapamiętanie 10 kroków.

Gdybyś poruszał się po tablicy trójwymiarowej, to przykładowa tablica byłaby: tab[10][3]. tab[10][10] z kolei umożliwia zapamiętanie 10 kroków w 10 wymiarowej przestrzeni.

 

Deklarując tablicę 100x100 marnujesz pełno pamięci lub dokładasz sobie roboty z wyszukaniem w niej jaką drogę przeszedłeś.

[Kitu 266]

A*?

 

 

To jeszcze nie ten poziom - z tego, co zdążyliśmy się zorientować, Roundstic dopiero zaczyna swoją przygodę w programowaniem (w ogóle wygląda to na pierwszy semestr studiów) - nie dawaliby mu zadania z A* bez wcześniejszego wspomnienia o nim. Przy tym poziomie w zupełności wystaczy porównanie kosztu przejścia w górę i w prawo (o ile sa możliwe) oraz wybranie mniejszego kosztu jako kolejny krok. To nic ponad zadanie na zrozumienie indeksów w tablicy dwuwymiarowej