Mám súbor S={a,c,d,e,f,j,m,q,s,t} s obmedzením C={am,cm,de,df,dm,ds,ef,em,eq,es,et,fj,fm,fs,jm,js}, xy v C znamená, že x a y nemôžu byť v tej istej podskupine. Chcel by som, aby algoritmus rozdelil súbor S na podsúbory Sj tak, že:
1. Počet Sj je minimalizovaný
2. Rozdiel medzi veľkosťou každej podskupiny je čo najväčší
Napríklad v tomto prípade oboje {{q,a,c,d,j,t},{m,s},{f},{e}} a {{a,c,e,j},{m,s,q,t},{d},{f}} vyhovujú 1, ale prvý je optimálny.
Prišiel som z pozície počítačovej vedy a som zvedavý, či matematici vytvorili algoritmus pre tento problém.
odpovede:
1 pre odpoveď č. 1Ako som pochopil, vaša úloha môže byť prepísaná ako: nájsť najväčšiu nezávislú podmnožinu vrcholov S "grafu G = (S, C), opakovať krok pre graf G" = GS ".
Je to dobre známe (tiež označené @tobias_k vo svojom komentári), že najväčší nezávislý súbor grafu je NP-ťažký problém (pretože je to ekvivalent slávneho problému s klikou).
0 pre odpoveď č. 2
Myslím, že je to veľmi ťažký problém, a to jeprečo. Pri hľadaní minimálneho počtu podmnožín musíte vyriešiť problém s minimálnym chromatickým číslom grafu. Tento problém je vo všeobecnosti riešený hrubou silou.