Az algoritmus módosítása egy gráf klikkek meghatározásához paraméteres adaptációval
VA Litvinenko I.Yu. Csernyenkónak
1. Alapvető rendelkezések
A grafikon klikkje egy maximális teljes subgraph, amely nem tartozik a magasabb rendű teljes részgrafikához (1 /).
A grafikon klikkek meghatározásának problémájával a kiválasztott klikkek számát értjük. Ebben az esetben, ha a grafikon összes kattintása ki van választva, akkor a megoldás pontossága 100%.
A nem irányított grafikonok csoportját tekintjük hurok és több széle nélkül.
A gráf klikkjeinek meghatározására szolgáló pontos algoritmusok kombinatorikus komplexitása ahhoz vezet, hogy közelítő módszereket kell alkalmazni a nagy dimenziójú problémák megoldására. Az ilyen problémák közé tartoznak különösen az integrált áramkörök tervezésének különböző problémái, amelyekben a gráf kattintásának meghatározására szolgáló algoritmusokat a tervezési műveletek algoritmusaként használják. Ismert algoritmusok / 1,2 / lehetővé teszik, hogy csak a klikkek olyan családjait határozzák meg, amelyek tulajdonságai és ereje a megoldott grafikonok szerkezetétől és az algoritmus végrehajtási sorrendjétől függ. A tervezési műveletek algoritmusainak minőségi döntése alapján a tervezési eljárások algoritmusainak megoldásának minősége lényegében függ.
Az algoritmusok kivitelezésének minőségét befolyásoló fő tényezők:
a megoldás szükséges pontossága;
a projekt mûködésének végrehajtására elkülönített idõforrás;
egy adott probléma dimenziója.
Ezek közül a tényezők közül az ismert megközelítő módszerek lehetővé teszik számunkra, hogy csak az időbeli korlátozást vesszük figyelembe az algoritmus végrehajtásához - az időforrás a megoldás megszakításával a lejáratkor / 2 /.
Azonban lehetséges, hogy az időforrás elegendő ahhoz, hogy pontos megoldást érjen el, és a probléma szükséges pontossága és dimenziója lehetővé teszi, hogy az algoritmust kevesebb idő alatt hajtsák végre, mint az időforrás. Egy másik helyzet akkor lehetséges, amikor a probléma dimenziója és az időforrás nem teszi lehetővé a megoldás szükséges pontosságának megszerzését.
Az ilyen esetek figyelembevételének lehetősége algoritmikusan lehetővé teszi a tervezési eljárás tervezési művelete algoritmusának végrehajtási idejének optimalizálását és ezáltal a matematikai és szoftver CAD használatának növelését.
2. Az alapvető algoritmus
A / 3 / kifejlesztett algoritmust a grafikon kattintásának meghatározására, amely különbözik az ismert időbeli erőforrásváltozáshoz való alkalmazkodás képességétől, a probléma pontosságától és méreteitől függetlenül, amelyet nem orientált gráfok hurok és több széle nélkül tanulmányoznak. Az algoritmus a parametrikus adaptáció módszerén alapul, amely lehetővé teszi a bemeneti paraméterek használatát arra, hogy "az algoritmust" állítsuk be a grafikon klikkjeinek meghatározásához, hogy különböző mértékű pontosságú megoldásokat kapjunk. Ebben az esetben a megoldás pontossága eltérhet a grafikon klikkek meghatározásának problémájához tartozó pontos megoldás megszerzésétől, azaz. határozza meg a grafikon összes klikkjét, mielőtt meghatározza a grafikon kattintásainak számát, amely elegendő ahhoz, hogy meg lehessen szerezni a tervezési eljárás megoldását, amelyre a klaszter grafikon meghatározásának feladatát algoritmussá kell használni a tervezési művelethez.
Így a figyelembe vett algoritmus lehetővé teszi, hogy különböző fokú pontosságú megoldásokat kapjunk, és ugyanakkor lehetővé tegyük a gráf összes klikkének elválasztását. azaz hogy megtalálja a pontos megoldást. Ezt az algoritmust algoritmusként használjuk a módosított algoritmusban.
Az alapalgoritmus alapja a következő tétel, melyet [4] bizonyítottak.
Tegyük fel, hogy a G = (X, U) gráfban van egy csúcs
és egy kattintást határozott meg
sok csúcsponttal