Algorytm na droge najmniejszej redukcji macierzy

0

Witam.
Muszę napisać algorytm na odnalezienie najmniejszej drogi w macierzy kwadratowej gdzie:

  1. M[i,j]=całkowita dodatnie albo 0, dla i będącego liczbą parzystą oraz j będącego liczbą nieparzystą, albo i będącego liczbą nieparzystą oraz j będącego liczbą parzystą,
  2. M[i,j]=X, dla i oraz j będących liczbami parzystymi,
  3. M[i,j]=Y, dla i oraz j będących liczbami nieparzystymi.
    Przykładowa macierz:
    X 0 X 3 X
    9 Y 0 Y 0
    X 6 X 6 X
    9 Y 8 Y 3
    X 0 X 2 X

Naszym zadaniem jest stworzenie drogi która daje dostęp każdemu X do każdego innego X, gdzie droga może powstać tylko i wyłącznie miedzy X 0 X. Możemy wykonywć operacje redukcji liczby na 0 i suma redukcji liczb jest naszym wynikiem.

Powstała macierz:
X 0 X 0 X < redukcja 3
9 Y 0 Y 0
X 0 X 6 X < redukcja 6
9 Y 8 Y 0 < redukcja 3
X 0 X 0 X < redukcja 2

Teraz każdy X ma dotep do każdego innego X a wynkiem algorytmu jest
14 4
14 = suma kosztu rekucji
4 = ile operacji redukcji

Mam już stworzoną strukturę danych macierzy ale nie mam pomysłu jak zabrać się za algorytm wyszukujący taką drogę najmniejszej redukcji.
Może ma ktoś jakąś wskazówkę jak to zrobić.

0

Jest to jedno z zadań konkursowych na pewnej uczelni... bądźmy fair. Wskazówka to zamodelować problem jako graf.

1 użytkowników online, w tym zalogowanych: 0, gości: 1