VA Litvinenko I.Yu. Cernenko
1. Prevederi de bază
O clică a unui grafic este un subgraf complet maxim care nu aparține nici unui subgraf complet de ordin superior / 1 /.
Prin acuratețea rezolvării problemei determinării clicurilor unui grafic, înțelegem numărul de clicuri selectate. În acest caz, dacă sunt selectate toate clicurile din grafic, atunci precizia soluției este de 100%.
Considerăm o clasă de grafice nedirecționate fără bucle și muchii multiple.
Complexitatea combinatorică a algoritmilor exacți pentru determinarea clicurilor unui grafic duce la necesitatea utilizării metodelor aproximative pentru rezolvarea problemelor de dimensiuni mari. Astfel de probleme includ, în special, diferite probleme de proiectare a circuitelor integrate, în care algoritmii pentru determinarea clicului unui grafic sunt utilizați ca algoritmi pentru operațiile de proiectare. Algoritmi cunoscuți / 1,2 / permit să se definească numai astfel de familii de clicuri, ale căror proprietăți și putere depind de structura grafurilor rezolvate și de secvența de execuție a algoritmului însuși. Din decizia calitativă a algoritmilor operațiilor de proiectare depinde în esență calitatea soluției de algoritmi de proceduri de proiectare.
Principalii factori care afectează calitatea execuției algoritmilor pentru operațiunile proiectului sunt:
acuratețea necesară a soluției;
resursele temporare alocate pentru implementarea operațiunii proiectului;
dimensiunea unei anumite probleme.
Dintre acești factori, metodele aproximative cunoscute ne permit să luăm în considerare numai limita de timp pentru executarea algoritmului - resursa de timp prin întreruperea soluției la momentul expirării acesteia / 2 /.
Cu toate acestea, este posibil ca resursa de timp să fie suficientă pentru a obține o soluție exactă, iar precizia și dimensionalitatea necesare a problemei permit ca algoritmul să fie executat în mai puțin timp decât resursele de timp. O altă situație este posibilă atunci când dimensiunea problemei și resursele de timp nu permit obținerea preciziei necesare a soluției.
Abilitatea de a ține cont de astfel de cazuri permite algoritmul de a optimiza timpul de execuție al algoritmului de funcționare a procesului de proiectare și, prin urmare, creșterea eficienței utilizării CAD-ului matematic și software-ului.
2. Algoritmul de bază
În algoritmul dezvoltat pentru determinarea clicului graficului, care diferă de capacitatea cunoscută de adaptare la schimbarea resurselor de timp, precizia și dimensionalitatea necesare a problemei în sine, concepute pentru a investiga grafice nedirecte fără bucle și muchii multiple. Algoritmul se bazează pe metoda de adaptare parametrică, care permite utilizarea parametrilor de intrare pentru a "regla" algoritmul pentru determinarea clicurilor graficului pentru a obține soluții cu grade diferite de precizie. În acest caz, precizia soluției poate varia de la obținerea unei soluții exacte la problema determinării clicurilor unui grafic, adică determină toate clicurile graficului, înainte de a determina numărul de clicuri ale graficului care este suficient pentru a obține soluția procedurii de proiectare pentru care sarcina de determinare a graficului de clicuri este utilizată ca algoritm pentru operația de proiectare.
Astfel, algoritmul considerat permite obținerea de soluții cu grade diferite de precizie și, în același timp, permite stabilirea în principiu a tuturor clicurilor graficului. și anume pentru a obține soluția exactă. Acest algoritm este folosit ca algoritm de bază pentru algoritmul modificat considerat în această lucrare.
Baza algoritmului de bază este următoarea teoremă, dovedită în [4].
Să presupunem că în graficul G = (X, U) există un vertex
și a definit un clic
cu multe noduri
Articole similare
Trimiteți-le prietenilor: