Дискретная математика: Основы теории графов и алгоритмизация задач: Учебное пособие
Рассмотрены основные определения и понятия теории графов, необходимые для решения некоторых прикладных задач дискретной математики (определение оптимальных расстояний между множеством объектов, поиск критического пути в задаче сетевого планирования и управления, выбор предпочтительных вариантов системы по множеству критериев). Обсуждаются подходы к разработке компьютерных алгоритмов задач па основе моделей теории графов.
3.1.4. Îïèñàíèå ìàøèííîãî àëãîðèòìà Ôîðäà Ïîñêîëüêó çàäà÷à ìîæåò èìåòü íåñêîëüêî âàðèàíòîâ ðåøåíèÿ, òî âîç- ìîæíûé àëãîðèòì ìîæåò âêëþ÷àòü ñëåäóþùèå îñíîâíûå øàãè. 1. Ââîä ìàòðèöû äëèí äóã ãðàôà (L) è åå ðàçìåðà (n). 2. Óñòàíîâêà íà÷àëüíûõ çíà÷åíèé: 1) âåêòîðà ìåòîê: Ì0=0; i=1(1)n1, Ìi=max; ãäå max ìàêñèìàëüíî äîïóñòèìîå ÷èñëî äàííîãî òèïà; 2) îáíóëåíèå âñïîìîãàòåëüíîãî âåêòîðà âåðøèí, âõîäÿùèõ â êðèòè÷åñêèå ïóòè, V è ìàòðèöû êðàò÷àéøèõ ïóòåé Ê. Ïðÿìîé õîä (Ðåàëèçàöèÿ ïðàâèë 3 è 4 àëãîðèòìà Ôîðäà öèêëû ïîèñêà ñìåæíûõ âåðøèí ãðàôà ïî ñòðîêàì i è ñòîëáöàì j è îáíîâëåíèå ìåòîê âåðøèí): 3. Öèêë i=0(1)n1 (ïî ñòðîêàì ìàòðèöû L) 4. Öèêë j=0(1)n1 (ïî ñòîëáöàì ìàòðèöû L) åñëè (Lij>0 è Ìj Ìi>Lij) (åñòü ìåòêà, òðåáóþùàÿ èçìåíåíèÿ, òî) { MN=Mi + Lij ; (âû÷èñëåíèå íîâîé ìåòêè (MN) âåðøèíû j) åñëè (MN < Mj) (íîâàÿ ìåòêà ìåíüøå ñòàðîé, òî) Ìj=MN; (èçìåíåíèå ìåòêè âåðøèíû j) } Îáðàòíûé õîä (Ðåàëèçàöèÿ ïðàâèëà 5 àëãîðèòìà Ôîðäà ïîèñê âåðøèí êðàò÷àé- øèõ ïóòåé): 5. Vn-1=1; (êîíå÷íàÿ âåðøèíà êðàò÷àéøåãî ïóòè) 6. Öèêë j=n1(1)0 (îáðàòíûé öèêë ïî âåðøèíàì, íà÷èíàÿ ñ ïîñëåäíåé) åñëè (Vj=1) (âåðøèíà âõîäèò â êðàò÷àéøèé ïóòü, òî) 7. Öèêë i=0(1)n1 (ïîèñê ïðåäøåñòâóþùèõ âåðøèí i, ñìåæíûõ ñ âåðøèíîé j) {åñëè (Lij>0 è Ìj Ìi=Lij) (ðàçíîñòü ìåòîê ñìåæíûõ âåðøèí ðàâíà äëèíå äóãè ìåæäó íèìè, òî) { Kij= Lij ; (çàïîëíåíèå ìàòðèöû êðàò÷àéøèõ ïóòåé) Vi=1; (âêëþ÷åíèå âåðøèíû i â âåêòîð V) } } (êîíåö öèêëîâ i è j) 8. Âûâîä ìàòðèöû ñìåæíîñòè Ê ( ïîäãðàôà êðàò÷àéøèõ ïóòåé) è âåêòîðà ìåòîê âåðøèí M (äëèí êðàò÷àéøèõ ïóòåé îò âåðøèíû V0). Ïî ìàòðèöå Ê íåîáõîäèìî ïîñòðîèòü äëÿ èñõîäíîãî ãðàôà ïîäãðàô êðàò÷àéøèõ ïóòåé îò âåðøèíû v0 ê vn. 51 à) M: Âåðøèíû 0 1 2 3 4 5 6 Ìåòêè 0 7 8 9 11 13 19 á) â) K: 0 1 E 2 3 4 5 6 v [7] 4 v" [11] 0 0 7 0 9 0 0 0 1 0 0 0 0 4 0 0 8 2 0 0 0 0 0 0 0 7 2 9 4 6 3 0 0 0 0 2 4 0 4 0 0 0 0 0 0 8 v [0] v! [9] v# [13] v$ [19] 5 0 0 0 0 0 0 6 6 0 0 0 0 0 0 0 Ðèñ. 3.4. Ðåçóëüòàòû ïîèñêà ìèíèìàëüíûõ ïóòåé â ãðàôå: à âåêòîð ìåòîê M (äëèí êðàò÷àéøèõ ïóòåé îò âåðøèíû v0 äî îñòàëüíûõ); á ïîäãðàô êðàò- ÷àéøèõ ïóòåé îò âåðøèíû v0 äî v6; â ìàòðèöà äëèí ïóòåé (Ê) ïîäãðàôà Íà ðèñ. 3.4 ïðåäñòàâëåíû ðåçóëüòàòû îáðàáîòêè ìàòðèöû äëèí äóã L (ðèñ. 3.3) èñõîäíîãî ãðàôà íà ðèñ. 3.2 â ñîîòâåòñòâèè ñ àëãîðèòìîì Ôîðäà. 3.2. Ïîèñê ìàêñèìàëüíîãî ïóòè â ãðàôå áåç êîíòóðîâ Àëãîðèòì Ôîðäà ìîæåò áûòü èñïîëüçîâàí äëÿ îòûñêàíèÿ ìàêñèìàëü- íîãî ïóòè (èëè êðèòè÷åñêîãî ïóòè â çàäà÷å ñåòåâîãî ïëàíèðîâàíèÿ è óï- ðàâëåíèÿ) â àöèêëè÷åñêîì ãðàôå. Äîñòàòî÷íî ïîëîæèòü íà÷àëüíûå ìåòêè âåðøèí λi=0, i=0, 1, 2, , n, à çàòåì çàìåíÿòü λj íà λ'j=λi+L(vi, vj), åñëè λ'j>λj, äî òåõ ïîð, ïîêà âîçìîæíî óâåëè÷èâàòü λj. 52 4. ÇÀÄÀ×À ÂÛÁÎÐÀ ÏÐÅÄÏÎ×ÒÈÒÅËÜÍÛÕ ÂÀÐÈÀÍÒΠÈÑÑËÅÄÓÅÌÎÉ ÑÈÑÒÅÌÛ 4.1. Îáùàÿ ïîñòàíîâêà çàäà÷è Ïðè ïðîåêòèðîâàíèè ñëîæíîé ñèñòåìû, êàê ïðàâèëî, èññëåäóåòñÿ íåñêîëüêî âàðèàíòîâ ñèñòåìû, ïðè ýòîì âîçíèêàþò ïðîáëåìû êàê ïðè îöåíêå ýôôåêòèâíîñòè ñèñòåìû, òàê è ïðè âûáîðå íàèáîëåå ýôôåêòèâ- íîãî, à çíà÷èò, è ïðåäïî÷òèòåëüíîãî âàðèàíòà. Ïîä ýôôåêòèâíîñòüþ ñè- ñòåìû ïîíèìàåòñÿ ìåðà ñîîòâåòñòâèÿ ñèñòåìû ñâîåìó íàçíà÷åíèþ, ò. å. ñòåïåíü ïðèñïîñîáëåííîñòè åå äëÿ ðåøåíèÿ ïîñòàâëåííûõ ïåðåä íåé çàäà÷, êîòîðàÿ îöåíèâàåòñÿ çàäàííîé öåëåâîé ôóíêöèåé f (ôóíêöèåé êðèòåðèÿ ýôôåêòèâíîñòè). Òðóäíîñòü ñîñòîèò â òîì, ÷òî ýôôåêòèâíîñòü ñëîæíîé ñèñòåìû íå ìîæåò áûòü îöåíåíà îäíèì ïîêàçàòåëåì, äàæå óíèâåðñàëüíûì, ïîñêîëü- êó îíà ÿâëÿåòñÿ ôóíêöèåé áîëüøîãî êîëè÷åñòâà ôàêòîðîâ è êðèòåðèåâ ýôôåêòèâíîñòè âñåõ ïîäñèñòåì, âõîäÿùèõ â ðàññìàòðèâàåìóþ ñèñòåìó. Ýôôåêòèâíîñòü ñëîæíîé ñèñòåìû íåîáõîäèìî îöåíèâàòü ñ ðàçëè÷íûõ òî÷åê çðåíèÿ ñ ïîìîùüþ ÷àñòíûõ ïîêàçàòåëåé êà÷åñòâà åå ôóíêöèîíè- ðîâàíèÿ, â îáùåì ñëó÷àå ïðîòèâîðå÷èâûõ, íàïðèìåð ãàáàðèòû, âåñ, ïðî- ïóñêíàÿ ñïîñîáíîñòü, íàäåæíîñòü, ñëîæíîñòü àëãîðèòìîâ ôóíêöèîíè- ðîâàíèÿ, ñòîèìîñòü ïðîèçâîäñòâà è ýêñïëóàòàöèè è ò. ï. Òàêèì îáðà- çîì, êðèòåðèé ýôôåêòèâíîñòè ñëîæíîé ñèñòåìû ÿâëÿåòñÿ âåêòîðíûì .={fn}, n = 1, N , ãäå fn ÷àñòíûå ïîêàçàòåëè êà÷åñòâà (êðèòåðèè ýôôåêòèâíîñòè) ôóíê- öèîíèðîâàíèÿ ñëîæíîé ñèñòåìû. Ïîäîáíàÿ ïðîáëåìà âîçíèêàåò è ïðè ýêñïåðòíîì àíàëèçå âûáèðàå- ìûõ îáúåêòîâ, êîãäà îáúåêòû, íàïðèìåð êâàðòèðà, îöåíèâàåòñÿ íåñêîëü- êèìè ñïåöèàëèñòàìè (ýêñïåðòàìè) ïî íåñêîëüêèì ïîêàçàòåëÿì (ìåòðàæ, óäîáñòâà, ñòîèìîñòü, óäàëåííîñòü îò òðàíñïîðòà èëè öåíòðà ãîðîäà è äð.). Ïðè ýòîì îöåíêè ýêñïåðòîâ ìîãóò îòëè÷àòüñÿ âåñüìà ñóùåñòâåííî. 53 Âîçíèêàåò îáùàÿ ïðîáëåìà îöåíêè Ì âàðèàíòîâ èññëåäóåìîé ñè- ñòåìû (îáúåêòîâ) ïî N êðèòåðèÿì è âûáîðà íàèáîëåå ïðåäïî÷òèòåëü- íûõ èç íèõ (æåëàòåëüíî âûáðàòü îäèí âàðèàíò), ñ òî÷êè çðåíèÿ âñåõ êðèòåðèåâ. Òàêèì îáðàçîì, ýòó ïðîáëåìó âûáîðà ìîæíî ðàçáèòü íà äâà ýòàïà. Íà ïåðâîì ýòàïå âàðèàíòû ñèñòåìû èññëåäóþòñÿ ïî ìíîæåñòâó êðèòåðèåâ .={fn}, n = 1, N . Ðåçóëüòàòû èññëåäîâàíèÿ (îöåíèâàíèÿ) âñåõ Ì âàðèàíòîâ ñâîäÿòñÿ â ìàòðèöó îöåíîê ||Ð||M×N, îòîáðàæàþùóþ ñòàòè÷åñêè óñòîé÷èâûå èëè äåòåðìèíèðîâàííûå îöåíêè ïîêàçàòå- ëåé êà÷åñòâà Ì âàðèàíòîâ ïî N êðèòåðèÿì.  íàøåì ïîñëåäóþùåì ðàññìîòðåíèè çàäà÷è ìû áóäåì ñ÷èòàòü ýòè äàííûå (M, N, P) êàê èñ- õîäíûå. Âòîðîé ýòàï çàêëþ÷àåòñÿ â ïîñëåäîâàòåëüíîé îáðàáîòêå ìàòðèöû îöåíîê Ð. Íåîáõîäèìî èç ñîâîêóïíîñòè èíäèâèäóàëüíûõ îöåíîê âàðè- àíòîâ ïî çàäàííîìó íàáîðó êðèòåðèåâ âûðàáîòàòü ãðóïïîâîå ðåøåíèå î ïîðÿäêå ïðåäïî÷òåíèÿ àëüòåðíàòèâíûõ âàðèàíòîâ, ò. å. äîëæíà áûòü ðåøåíà ïðîáëåìà ãðóïïîâîãî âûáîðà. Ôîðìàëèçàöèÿ è ðåøåíèå ýòîé çàäà÷è ïîêàçàíû äàëåå. 4.2. Ïîëó÷åíèå ñðàâíèìûõ îöåíîê Ïóñòü ðmn îöåíêà m-ãî âàðèàíòà ïî êðèòåðèþ fn. Îöåíêè ðmn, m = 1, M , ÿâëÿþòñÿ àáñîëþòíûìè, îíè ïîëó÷åíû â åñòåñòâåííîé äëÿ êàæäîãî êðèòåðèÿ øêàëå è ðàñïîëîæåíû â íåêîòîðîì äèàïàçîíå [pmin(n), pmax(n)]. Ïðè ýòîì äëÿ îäíèõ êðèòåðèåâ pmax ÿâëÿåòñÿ íàèëó÷øåé èç ïîëó÷åííûõ îöåíîê, äëÿ äðóãèõ íàèõóäøåé, ò. å. òàêèå îöåíêè ïî ðàçíûì êðèòåðèÿì ÿâëÿþòñÿ íåñðàâíèìûìè. Ïåðâûé øàã îáðàáîòêè ìàòðèöû îöåíîê Ð çàêëþ÷àåòñÿ â ïðåîáðàçî- âàíèè ýëåìåíòîâ ìàòðèöû ñ öåëüþ ïîëó÷åíèÿ ñðàâíèìûõ îöåíîê ïóòåì ïðèâåäåíèÿ èõ ê åäèíîìó ìàñøòàáó è íà÷àëó îòñ÷åòà. Ýòà çàäà÷à ìîæåò áûòü ðåøåíà ðàçëè÷íûìè ìåòîäàìè, íàïðèìåð ðàíæèðîâàíèåì îöåíîê. Ðàíæèðîâàíèå ïðåäñòàâëÿåòñÿ ïðîöåäóðîé âû÷èñëåíèÿ îöåíîê â ðàíãî- âîé øêàëå, êîòîðóþ ìîæíî îïèñàòü ñëåäóþùèì îáðàçîì. Îáîçíà÷èì pl (n), px (n) ñîîòâåòñòâåííî ëó÷øóþ è õóäøóþ îöåíêè ïî êðèòåðèþ fn∈., n = 1, N . Îöåíêè ïî êðèòåðèþ fn äëÿ âñåõ âàðèàíòîâ íàõîäÿòñÿ â äèàïàçîíå px (n) ≤ ðmn ≤ pl(n), m = 1, M . 54 Ïîñòðîåíèå øêàëû îöåíîê Sn çàêëþ÷àåòñÿ â çàäàíèè ÷èñëà ãðàäàöèé D (ðàíãîâ, äåëåíèé) øêàëû è îïðåäåëåíèè öåíû äåëåíèÿ øêàëû dn= ( pl (n) px (n)) / D. Áëèçêèå îöåíêè (ñ òî÷íîñòüþ äî öåíû äåëåíèÿ) ìîãóò ïîïàñòü â îäèí ðàíã øêàëû Sn, ò. å. ýòè îöåíêè ýêâèâàëåíòíû â äàííîé øêàëå Sn, çíà- ÷èò, D îïðåäåëÿåò êîëè÷åñòâî êëàññîâ ýêâèâàëåíòíîñòåé â ìàòðèöå îöå- íîê. Èç èñõîäíîé ìàòðèöû îöåíîê Ð àáñîëþòíûå îöåíêè pmn ïðåîáðàçó- þòñÿ â ðàíæèðîâàííûå îöåíêè rmn ñëåäóþùèì îáðàçîì: äëÿ pl (n) ïîëàãàåì rmn = D, äëÿ îñòàëüíûõ âû÷èñëÿåì ïî ôîðìóëå rmn = [( ðmn px(n)) / dn +1], ãäå [x] áëèæàéøåå öåëîå ÷èñëî, ìåíüøåå èëè ðàâíîå õ, ò. å. öåëàÿ ÷àñòü õ. Îöåíêè rmn ñîîòâåòñòâóþò ðàíãó, ò. å. áîëåå ïðåäïî÷òèòåëüíîìó îáúåê- òó ñîîòâåòñòâóåò áîëåå âûñîêèé ðàíã. Ïðåîáðàçîâàííàÿ òàêèì îáðàçîì ìàòðèöà ðàíæèðîâàííûõ îöåíîê ||R||M×N ñîäåðæèò ñðàâíèìûå ïî ðàçëè÷íûì êðèòåðèÿì îöåíêè, ïîñêîëü- êó ðàíæèðîâàííûå îöåíêè òåðÿþò àáñîëþòíûé âåñ è çíàê, ñïåöèôè÷- íîñòü, îïðåäåëÿåìóþ öåíîé äåëåíèÿ øêàëû äàííîãî êðèòåðèÿ, ñîõðàíÿÿ îòíîñèòåëüíûé âåñ, ò. å. ïîëîæåíèå â ðàíãîâîé øêàëå. 4.3. Ïîëó÷åíèå ãðóïïîâûõ îöåíîê Âòîðîé øàã îáðàáîòêè ìàòðèöû îöåíîê Ð ñîñòîèò â âûðàáîòêå ãðóï- ïîâîãî ïðåäïî÷òåíèÿ âàðèàíòîâ íà îñíîâå èíäèâèäóàëüíûõ ðàíæèðî- âàííûõ îöåíîê ìàòðèöû R, ïîëó÷åííîé â ðåçóëüòàòå ñîãëàñîâàíèÿ îá- ùåé øêàëû îöåíîê. Ïðîñòåéøèé ñïîñîá ïîëó÷åíèÿ ãðóïïîâîé îöåíêè ñîñòîèò â òîì, ÷òî êàæäîìó êðèòåðèþ fn ñòàâèòñÿ â ñîîòâåòñòâèå ÷èñëî ln, íàçûâàåìîå âå- ñîì êðèòåðèÿ fn. Ñîâîêóïíîñòü { ln}, n = 1, N , óïîðÿäî÷èâàåò ìíîæå- ñòâî .={fn} ïî ñòåïåíè âàæíîñòè êðèòåðèåâ. Ãðóïïîâàÿ îöåíêà îïðå- äåëÿåòñÿ êàê âåêòîð G = RM×N ×L, ãäå L={ln }, n = 1, N , à ýëåìåíòû âåêòîðà G îïðåäåëÿþòñÿ âûðàæåíèåì N gm = ∑ rmnln , n =1 îòñþäà ìîæíî ïîëó÷èòü óñðåäíåííûå çíà÷åíèÿ 55 N gm = gm / N = ( ∑ rmnln ) / N , m = 1, M , n =1 ãäå M êîëè÷åñòâî âàðèàíòîâ. Âàðèàíòû îáúåêòîâ ñðàâíåíèÿ óïîðÿäî÷èâàþòñÿ â ñîîòâåòñòâèè ñî çíà÷åíèåì âåëè÷èí gm èëè g m , ïðè ýòîì âàðèàíò ñ ìàêñèìàëüíûì çíà- ÷åíèåì gm ( g m ) ÿâëÿåòñÿ íàèáîëåå ïðåäïî÷òèòåëüíûì. Åñëè îáðàçóåòñÿ ìíîæåñòâî íåðàçëè÷èìûõ ïî gm âàðèàíòîâ, òî äàëüíåéøåå óïîðÿäî÷å- íèå îñóùåñòâëÿåòñÿ ñ ïîìîùüþ ëåêñèãðàôè÷åñêîãî ïîðÿäêà. Ïðèíèìà- åòñÿ, ÷òî âàðèàíò v1 ïðåäïî÷òèòåëüíåå âàðèàíòà v2, åñëè îöåíêà v1 ïî ñàìîìó âàæíîìó ïîêàçàòåëþ âûøå, ÷åì îöåíêà v2, ïðè ðàâåíñòâå ýòèõ îöåíîê âàðèàíòû ñðàâíèâàþòñÿ ïî ïîêàçàòåëþ, ñëåäóþùåìó ïî âàæíî- ñòè è ò. ä. Ïðèìåð Ðàññìîòðèì øàãè îáðàáîòêè ìàòðèöû îöåíîê ÐM×N äëÿ ñëåäóþùèõ èñõîäíûõ äàííûõ: êîëè÷åñòâî îáúåêòîâ ñðàâíåíèÿ (âàðèàíòîâ) Ì=4, êî- ëè÷åñòâî êðèòåðèåâ (ôóíêöèé ïðåäïî÷òåíèÿ) N=6, ìàòðèöà îöåíîê Ð4×6: 1 2 3 4 5 6 1 2,5 102 0,1 2 3,5 4 2 3 57 0,9 1 0 0 3 5,7 32 0,4 10 5 2 4 17 52 1,1 0 5 3 Ïåðâûé øàã îáðàáîòêè Ð ïîëó÷åíèå îòíîñèòåëüíûõ îöåíîê. Äèà- ïàçîíû îöåíîê ïî êðèòåðèÿì fn→[px(n), pl(n)] è öåíû äåëåíèé øêàë Sn ïðè ÷èñëå ðàíãîâ D=10: f1→[3, 17], d1 = 2, f2→[102, 32], d2 = 7, f3→[0,1; 1,1], d3 = 0,1, f4→[10, 0], d4 = 1, f5→[5, 5], d5 = 1, f6→[0, 4], d6 = 0,4. 56 Ðàíæèðîâàííàÿ ìàòðèöà îöåíîê R4×6: 1 2 3 4 5 6 1 3 1 1 9 20 10 2 1 7 9 10 6 1 3 5 10 4 1 1 6 4 10 7 10 10 10 8 Âòîðîé øàã ïîëó÷åíèå ãðóïïîâûõ îöåíîê. fn 1 2 3 4 5 6 Âåñà êðèòåðèåâ: ln 3 2 2 3 1 1 Ãðóïïîâûå îöåíêè âàðèàíòîâ: g1 = 3⋅3+2⋅1+2⋅1+3⋅9+1⋅2+1⋅10 = 52, g1 =8,7, g2 = 3⋅1+2⋅7+2⋅9+3⋅10+1⋅6+1⋅1 = 72, g2 = 12, g3 = 3⋅5+2⋅10+2⋅4+3⋅1+1⋅1+1⋅6 = 53, g3 = 8,7, g4 = 3⋅10+2⋅7+2⋅10+3⋅10+1⋅10+1⋅8 = 112, g4 = 18,67. Èñõîäÿ èç óñðåäíåííûõ ãðóïïîâûõ îöåíîê âàðèàíò 4 ìîæíî ñ÷èòàòü ïðåäïî÷òèòåëüíûì èç ðàññìàòðèâàåìûõ âàðèàíòîâ ñðàâíåíèÿ. Îäíàêî ïî ïîâîäó óñðåäíåííûõ ãðóïïîâûõ îöåíîê ìîæíî ñêàçàòü òî æå, ÷òî è î ñðåäíåé òåìïåðàòóðå áîëüíûõ â áîëüíèöå èëè îòíîñèòåëüíî ñðåäíèõ îöåíîê ýêñïåðòîâ. Ýòè îöåíêè íèâåëèðóþò ðàçëè÷èÿ â ôóíêöèÿõ ïðåä- ïî÷òåíèÿ, îíè îòðàæàþò òî îáùåå, ÷òî åñòü â èíäèâèäóàëüíûõ îöåíêàõ, è ñãëàæèâàþò áîëåå òîíêèå îòíîøåíèÿ ìåæäó ðàçëè÷íûìè êðèòåðèÿìè. Çàäà÷ó âûáîðà ïðåäïî÷òèòåëüíûõ âàðèàíòîâ ìîæíî ðåøèòü äðóãèì ñïîñîáîì ïðîèçâîäÿ àíàëèç ïðåäïî÷òåíèé ñðåäè àëüòåðíàòèâíûõ âà- ðèàíòîâ ïóòåì èõ ïîïàðíîãî ñðàâíåíèÿ. Ñôîðìóëèðóåì ýòó çàäà÷ó âû- áîðà êàê çàäà÷ó òåîðèè ãðàôîâ. 4.4. Ôîðìàëèçàöèÿ çàäà÷è âûáîðà ïðåäïî÷òèòåëüíûõ îáúåêòîâ Ïóñòü V ìíîæåñòâî îáúåêòîâ (âàðèàíòîâ) ñðàâíåíèÿ, ïðè÷åì V =Ì (êîëè÷åñòâî îáúåêòîâ), à . ìíîæåñòâî êðèòåðèåâ (ôóíêöèé ïðåäïî÷òåíèÿ), ïî êîòîðûì ìîæíî îöåíèâàòü ýòè îáúåêòû, è .=N (êîëè÷åñòâî ôóíêöèé). Âåëè÷èíû pn, íàçûâàåìûå îöåíêàìè, îòðàæà- þò ðàçëè÷èå ìåæäó ýëåìåíòàìè V ïî êðèòåðèþ fn∈., n = 1, N , ò. å. ïðåäñòàâëÿþò ñîáîé îòîáðàæåíèå pn : 57 V→fn, êîòîðîå ïîçâîëÿåò âûïîëíèòü ñðàâíåíèå ïî êðèòåðèþ fn. Îáîçíà÷èì ÷åðåç .n ìíîæåñòâî îöåíîê, êîòîðûå ìîæíî ïîëó÷èòü, èññëåäóÿ ýëåìåíòû V ñ òî÷êè çðåíèÿ êðèòåðèÿ fn. Ïðè àíàëèçå ïî âñåì êðèòåðèÿì êàæäîìó ýëåìåíòó v∈V ñòàâèòñÿ â ñîîòâåòñòâèå ïîñëåäîâàòåëüíîñòü èç N îöåíîê, âçÿòûõ èç ìíîæåñòâ .1, , .N, ò. å. ñ êàæäûì ýëåìåíòîì ìíîæåñòâà V ñîïîñòàâëÿåòñÿ ýëåìåíò äåêàðòîâà ïðîèçâåäåíèÿ . '= .1× .2× × .N.. Ñòàâèòñÿ çàäà÷à âûïîëíèòü ñðàâíåíèå îáúåêòîâ ìíîæåñòâà V ñ ïî- ìîùüþ ìíîãîìåðíîãî ñîñòîÿíèÿ .' = .1× .2× × .N. ñ öåëüþ âûáîðà îäíîãî èëè íåñêîëüêèõ îáúåêòîâ, ÿâëÿþùèõñÿ íàèëó÷øèìè ñ òî÷êè çðå- íèÿ ìíîæåñòâà êðèòåðèåâ .. Ïðåäñòàâèì ðåøåíèå çàäà÷è ïîïàðíîãî ñðàâ- íåíèÿ îáúåêòîâ íà ÿçûêå òåîðèè ãðàôîâ. Ìíîæåñòâî âñåõ óïîðÿäî÷åííûõ ïàð v, v'∈V îáîçíà÷àåòñÿ V×V. Ïîä- ìíîæåñòâî B⊆V×V íàçûâàåòñÿ áèíàðíûì îòíîøåíèåì, ò. å. (v,v') ∈B. Âûøå ìû ðàññìîòðåëè ñîîòâåòñòâèå ìåæäó áèíàðíûì îòíîøåíèåì è îðãðàôîì, ïðè ýòîì âåðøèíû ãðàôà ñîîòâåòñòâóþò îáúåêòàì ñðàâíåíèÿ vi∈V, à äóãè îòðàæàþò áèíàðíîå îòíîøåíèå ìåæäó îáúåêòàìè. Íàïîìíèì, ÷òî åñëè (v,v') ∈B, òî â ãðàôå ïðîâîäèòñÿ äóãà èç v â v', ïðè ýòîì v íà÷àëî, à v' êîíåö äóãè, ò. å. äóãà îïðåäåëÿåòñÿ ïàðîé (v,v'). Ïîñëåäîâàòåëüíîñòü äóã (vi, vi+1), i=1,2, , k1, íàçûâàåòñÿ ïó- òåì. Êîíå÷íûé ïóòü, ó êîòîðîãî v1=vk, îáðàçóåò êîíòóð. Äóãà (v, v) íà- çûâàåòñÿ ïåòëåé. Êàê èçâåñòíî, áèíàðíîå îòíîøåíèå íàçûâàåòñÿ ðåôëåêñèâíûì, åñëè (v,v) ∈B (ò. å. ãðàô ñ ïåòëÿìè); àíòèðåôëåêñèâíûì, åñëè (v,v) ∉B (ò. å. ãðàô áåç ïåòåëü); ñèììåòðè÷íûì, åñëè (v,v') ∈B ↔ (v',v) ∈B (ò. å. äëÿ êàæäîé ïàðû ñìåæíûõ âåðøèí åñòü âñòðå÷íûå äóãè); àíòèñèììåò- ðè÷íûì, åñëè (v,v') ∈B è (v',v) ∈B → v=v' (ò. å. âåðøèíû ñî âñòðå÷íû- ìè äóãàìè ðàññìàòðèâàþòñÿ êàê îäíà âåðøèíà); àñèììåòðè÷íûì, åñëè (v,v') ∈B → (v',v) ∉B (ò. å. ãðàô áåç âñòðå÷íûõ äóã ìåæäó ïàðàìè âåð- øèí); òðàíçèòèâíûì, åñëè (v,v') ∈B è (v',v'') ∈B → (v,v'') ∈B (ò. å. åñëè ëþáûå òðè ïîñëåäîâàòåëüíûå âåðøèíû ñâÿçàíû äâóìÿ ïîñëåäîâàòåëü- íûìè äóãàìè, òî ñóùåñòâóåò äóãà ìåæäó ïåðâîé è òðåòüåé âåðøèíàìè); ëèíåéíûì, åñëè (v,v') ∈B èëè (v',v) ∈B (ò. å. ëþáûå äâå âåðøèíû ñâÿçà- íû õîòÿ áû îäíîé äóãîé). Ðàññìîòðèì òåïåðü ìíîæåñòâî êðèòåðèåâ .. Êàæäûé ÷àñòíûé êðèòå- ðèé fn∈. çàäàåò íàïðàâëåíèå âîçðàñòàíèÿ ïðåäïî÷òåíèÿ îáúåêòîâ, â ñî- îòâåòñòâèè ñ óâåëè÷åíèåì èõ îöåíîê, îïðåäåëÿåìûõ â êîëè÷åñòâåííîé èëè ðàíãîâîé øêàëå, ò. å. ìîæíî çàäàòü áèíàðíîå îòíîøåíèå ïðåäïî÷- 58 òåíèÿ (ïðåâîñõîäñòâà) Pf , êîòîðîå ñâÿçûâàåò ïàðó îáúåêòîâ ìíîæåñòâà V: (v,v') ∈ Pf , åñëè îöåíêà p(v) ≤ p(v'). Äëÿ êàæäîãî ÷àñòíîãî êðèòåðèÿ fn ìîæíî ïîñòðîèòü ãðàô Gn=(V,Un) (çäåñü Un ìíîæåñòâî âñåõ äóã ãðàôà Gn), â êîòîðîì ïðîâîäèòñÿ äóãà (v,v')∈Un, åñëè îöåíêà pn(v)<pn(v'), ò. å. ñòðåëêà äóãè ïîêàçûâàåò íà ïðåä- ïî÷òèòåëüíûé îáúåêò è ïðîâîäÿòñÿ âñòðå÷íûå äóãè (v,v'), (v',v) ∈ Un, åñëè pn(v)=pn(v'). Ãðàô Gn =(V,Un) áóäåò òðàíçèòèâíûì è ðåôëåêñèâ- íûì, íî íå áóäåò àñèììåòðè÷íûì, òàê êàê ìåæäó äâóìÿ âåðøèíàìè ìî- ãóò áûòü âñòðå÷íûå äóãè. Òðàíçèòèâíîå è ðåôëåêñèâíîå îòíîøåíèå Pf íàçûâàåòñÿ êâàçèïîðÿä- êîì, à ïðè óñëîâèè, ÷òî ëþáûå äâà îáúåêòà ñðàâíèìû ïî Pf : (v,v') ∈ Pf èëè (v',v) ∈ Pf , îíî íàçûâàåòñÿ ëèíåéíûì, èëè ïîëíûì êâàçèïîðÿäêîì. Ââåäåì îòíîøåíèå íåðàçëè÷èìîñòè Nf äëÿ îáúåêòîâ ñ p(v)=p(v'): (v,v') ∈Nf. Ýòî òðàíçèòèâíîå, ðåôëåêñèâíîå è ñèììåòðè÷íîå îòíîøå- íèå, íàçûâàåìîå ýêâèâàëåíòíîñòüþ, îòðàæàåòñÿ íà ãðàôå Gn êîíòó- ðàìè è ïîðîæäàåò êëàññû (ïîäìíîæåñòâà) ýêâèâàëåíòíûõ îáúåêòîâ K i⊆V. Ìåæäó êëàññàìè ýêâèâàëåíòíîñòåé ñóùåñòâóåò îòíîøåíèå ñòðîãîãî ïðåäïî÷òåíèÿ: (v(K),v(K')) ⊆ P, åñëè p(v(K)) < p(v(K')). Ýòè îòíîøåíèÿ, íàçûâàåìûå êâàçèñåðèÿìè, ðåôëåêñèâíû è òðàíçèòèâ- íû. Êâàçèñåðèþ P, äëÿ êîòîðîé Nf ÿâëÿåòñÿ îòíîøåíèåì ðàâåíñòâà, ò. å. (v,v')∈Nf →v=v' íàçûâàþò ñåðèåé. Ñåðèè ñîîòâåòñòâóþò ñòðîãîìó óïîðÿäî÷åíèþ îáúåêòîâ. Ïîëíûé êâàçèïîðÿäîê ÿâëÿåòñÿ ïîëíûì ïîðÿäêîì, èëè ñåðèåé, òîãäà è òîëüêî òîãäà, êîãäà îí àíòèñèììåòðè÷åí, ò. å. êîãäà êëàññû ýêâèâàëåí- òíîñòåé ñâåäåíû ê îäíîìó îáúåêòó: (v,v')∈Nf è (v',v)∈Nf → v=v'. Òàêèì îáðàçîì, ãðàô Gn âîñïðîèçâîäèò îòíîøåíèå ïîëíîãî êâàçè- ïîðÿäêà íà ìíîæåñòâå îáúåêòîâ V íà îñíîâàíèè êðèòåðèÿ fn. Óêàçàâ ðÿäîì ñ âåðøèíàìè ãðàôà çíà÷åíèÿ îöåíîê îáúåêòîâ, ïîëó- ÷åííûõ â êîëè÷åñòâåííîé èëè ðàíãîâîé øêàëå, ìîæíî îòðàçèòü íà ãðà- ôå âñþ èíôîðìàöèþ ïî ñðàâíåíèþ îáúåêòîâ. Ñîâìåñòèâ îäíîèìåííûå âåðøèíû ãðàôîâ Gn, n = 1, N , ïîëó÷èì ìóëü- òèãðàô GV, îòðàæàþùèé èíôîðìàöèþ äëÿ ñðàâíåíèÿ ìíîæåñòâà îáúåê- òîâ V ïî ìíîæåñòâó êðèòåðèåâ .. Ïðèìåð Íà îñíîâå ðàíæèðîâàííîé ìàòðèöû îöåíîê R4×6, ïîëó÷åííîé â ïðåäû- äóùåì ïðèìåðå äëÿ ÷åòûðåõ îáúåêòîâ ñðàâíåíèÿ, íà ðèñ. 4.1 ïîñòðîåíû 59 ÷àñòíûå ãðàôû G n äëÿ êðèòåðèåâ fn (n= 1,6 ) ïî ÷åòûðåì âåðøèíàì (îáúåêòàì v1,v2,v3,v4), ãäå ÷èñëà ïðè âåðøèíàõ ýòî çíà÷åíèÿ ðàí- æèðîâàííûõ îöåíîê îáúåêòîâ ñðàâíåíèÿ. Ïîñëå ñîâìåùåíèÿ âåðøèí è íàëîæåíèÿ äóã ïîëó÷èì ìóëüòèãðàô GV (ðèñ. 4.2,à), ãäå ÷èñëà ïðè äóãàõ ïîêàçûâàþò êîëè÷åñòâî ïàðàëëåëüíûõ äóã äàííîãî íàïðàâëå- íèÿ. v v! v v! v v! 1 5 7 10 9 4 3 10 1 7 1 10 v v" v v" v v" v→G v →G v!→G! v v! v v! v v! 10 1 6 1 1 6 9 10 2 10 10 8 v v" v v" v v" v"→G" v#→G# v$→G$ Ðèñ.4.1. ×àñòíûå ãðàôû Gn  ìóëüòèãðàôå GV íàðóøàåòñÿ òðàíçèòèâíîñòü îòíîøåíèÿ íåðàçëè- ÷èìîñòè, âñëåäñòâèå íåîáõîäèìîñòè ñðàâíèâàòü ïî íåñêîëüêèì êðèòå- ðèÿì. Íåîáõîäèìî ââåñòè íîâîå îòíîøåíèå, êîòîðîå òðàíñôîðìèðîâàëî áû ìóëüòèãðàô GV â ãðàô G=(V,U), âîñïðîèçâîäÿùèé êâàçèïîðÿäîê íà ìíîæåñòâå V ñ ó÷åòîì îöåíîê ïî âñåì êðèòåðèÿì. Ïðåîáðàçîâàíèå GV → G=(V,U) ñâîäèòñÿ ê óñòàíîâëåíèþ ïðàâèëà, êîòîðîå ïîçâîëÿåò çàìåíèòü ìíîæåñòâî äóã ìåæäó âåðøèíàìè v è v' â GV ê äóãå (v,v')∈U èëè (v',v)∈U â ãðàôå G. Ñàìîå ïðîñòîå ïðàâèëî ïðåîáðàçîâàíèÿ GV→G ñâîäèòñÿ ê ïðèí- öèïó ãîëîñîâàíèÿ (áîëüøèíñòâà), ïî êîòîðîìó â ãðàôå G ïðîâîäèòñÿ äóãà (v,v'), åñëè â ãðàôå GV êîëè÷åñòâî äóã (v,v') ïðåâûøàåò ÷èñëî äóã (v',v), à â ñëó÷àå ðàâåíñòâà ïðîâîäÿòñÿ âñòðå÷íûå äóãè (v,v') è (v',v), ïðè ýòîì âåñà äóã ïîëàãàþòñÿ îäèíàêîâûìè, ò. å. èãíîðèðóåòñÿ 60