Skip to content

Determinarea drumul optim într-un graf / drum hamiltonian, folosind matricea de atingere. (Chan)

O rezolvare pentru problema:

Să se întocmească un program care determină drumul optim într-un graf, folosind matricea de atingere.

consta in determinarea unui drum hamiltonian într-un graf orientat (fără circuite).
Se poate executa un algoritm cu 2 pasi (Chan)

  • Pasul 1. Se construieşte matricea conexă terminală T pornind de lamatricea tranziţiilor M.
    Se determină câte elemente din T sunt nenule; dacă numărul acestora este n(n-1)/2, atunci graful conţine un drum hamiltonian.
  • Pasul 2. Din matricea T se construieşte T_prim.
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    
    package Namir;
    /*
     * Determinarea drumul optim într-un graf / drum hamiltonian, folosind matricea de atingere. Chan
     */
     
    public class Chan {
    	public static void main(String[] args) {
    		int[][] matrice; // retinem o matrice
    		int nr_noduri = 5;
    		matrice = new int[nr_noduri][nr_noduri]; // matricea retinuta este atat
     
    		matrice[0][1] = 1;
    		matrice[0][2] = 1;
    		matrice[0][3] = 1;
    		matrice[0][4] = 1;
    		matrice[1][2] = 1;
    		matrice[1][3] = 1;
    		matrice[1][4] = 1;
    		matrice[2][4] = 1;
    		matrice[4][3] = 1;
     
    		// afisarea matricii
    		System.out.printf("\nmatricea citita este:\n");
    		for (int i = 0; i < nr_noduri; i++) {
    			for (int j = 0; j < nr_noduri; j++) {
    				System.out.printf("%d ", matrice[i][j]);
    			}
    			System.out.printf("\n");
    		}
     
    		// Pentru determinarea unui drum hamiltonian într-un graf orientat şi fără circuite
    		// se parcurge un algoritm cu 2 pasi (Chan?!)
     
    		// Pasul 1. Se construieşte matricea conexă terminală T pornind de la matricea tranziţiilor M.
    		// Se determină câte elemente din T sunt nenule; dacă numărul acestora
    		// este n(n-1)/2, atunci graful conţine un drum hamiltonian.
    		int[][] t = new int[nr_noduri][nr_noduri];
    		for (int i = 0; i < nr_noduri; i++)
    			for (int j = 0; j < nr_noduri; j++)
    				t[i][j] = matrice[i][j];
     
    		for (int i = 0; i < nr_noduri; i++) {
    			for (int j = 0; j < nr_noduri; j++)
    				if (matrice[i][j] != 0) {	//daca avem drum intre nodul i si nodul j
    					t[i][j] = matrice[i][j];
    					for (int k = 0; k < nr_noduri; k++) {
    						t[i][k] = matrice[i][k] + t[j][k];	// 0+0=0; 0+1=1; 1+0=1; 1+1=1
    						if (t[i][k] > 1) // 1+1 = 2, deci vom folosi 1 in loc de 2
    							t[i][k] = 1;
    					}
    				}
    		}
    		// numaram numarul de elemente diferite de zero
    		int nrElementeNenule = 0;
    		for (int i = 0; i < nr_noduri; i++)
    			for (int j = 0; j < nr_noduri; j++)
    				if (t[i][j] != 0)
    					++nrElementeNenule;
    		int nrNoduriHamilton = nr_noduri * (nr_noduri - 1) / 2;
    		if (nrNoduriHamilton != nrElementeNenule)
    			System.out.printf("s-au gasit %d elemente nenule si nu avem drum hamiltonian (n(n-1)/2=%d)\n", nrElementeNenule, nrNoduriHamilton);
     
    		// Pasul 2. Din matricea T se construieşte T_prim.
    		// punem suma liniei din matricea t
    		int[][] tPrim = new int[nr_noduri][2];
    		for (int i = 0; i < nr_noduri; i++)
    			for (int j = 0; j < nr_noduri; j++) {
    				tPrim[i][0] = i;
    				tPrim[i][1] = tPrim[i][1] + t[i][j];
    			}
     
    		// sortam matricea rezultat ca pe un vector de obiecte cu 2 proprietati
    		// [0] este indexul original
    		// [1] este suma calculata anterior
    		// sortam dupa suma, deci dupa [1]
    		for (int i = 0; i < nr_noduri - 1; i++) {
    			for (int j = i + 1; j < nr_noduri; j++)
    				if (tPrim[i][1] < tPrim[j][1]) {
    					int vTemp = tPrim[i][1];
    					int iTemp = tPrim[i][0];
    					tPrim[i][1] = tPrim[j][1];
    					tPrim[i][0] = tPrim[j][0];
    					tPrim[j][1] = vTemp;
    					tPrim[j][0] = iTemp;
    				}
    		}
     
    		// afisam rezultatul
    		System.out.printf("Drumul optim folosind matricea de atingere este:\n");
    		for (int i = 0; i < nr_noduri; i++)
    			System.out.printf("%d->", tPrim[i][0] + 1);
    	}
     
    }