Ես քեզ պարտական ​​եմ, դու ինձ պարտք ես, մենք նրան ենք պարտական

Օղակի վերացում ուղղորդված, կշռված գրաֆիկում

Օղակի վերացման ալգորիթմները սովորաբար օգտագործվում են օպտիմիզացման և գրաֆիկական ալգորիթմներում՝ կատարելագործելու աշխատանքը՝ հեռացնելով ավելորդ կամ ավելորդ օղակները հաշվարկներում: Թեև հատուկ օգտագործման դեպքերը կարող են տարբեր լինել, հայտնի օրինակները, որտեղ պահանջվում են օղակների վերացման ալգորիթմներ, են էջերի դասակարգման ալգորիթմները, մատրիցային բազմապատկումը, կոմպիլյատորների օպտիմալացումը և այլն:

Իմ օգտագործման դեպքը բավականին տարբեր է:

Այս տարի ես հնարավորություն ունեցա մեկնել հարավային Իսպանիա և վայելել իմ սիրելի զբաղմունքը՝ ճանապարհային հեծանվավարություն:

Մի քանի ընկերների հետ գնացի այնտեղ և հենց սկզբից պայմանավորվեցինք, որ բոլոր ծախսերը ձայնագրելու և կիսելու ենք։

Բջջային բազմաթիվ հավելվածներ ունեն նման ֆունկցիոնալություն: Մենք ընտրեցինք Tricount-ը: Դա հեշտ օգտագործման ծրագիր է, որը հետևում է ծախսերին, ցույց է տալիս մնացորդները և ճանապարհորդության վերջում առաջարկում է փողի բաշխման եղանակ:

Ես նախկինում ներդրել էի նմանատիպ ծրագրակազմ, այնպես որ ես բացատրեցի, թե ինչպես է ծրագրաշարի այս մասը աշխատում իմ ընկերներին լեռներում երկար զբոսանքներից մեկի ժամանակ:

Քանի որ դա հետաքրքիր թեմա է, ես կփորձեմ նույնը անել ձեզ համար, սիրելի ընթերցող…

Ես կօգտագործեմ մի խումբ երևակայական ընկերներ, ովքեր գնացել են ճանապարհորդության և որոշել են կիսել ծախսերը։ Ցանկացած մարդ կարող է վճարել ամեն ինչի համար, բայց նրանք համաձայնեցին, որ գրանցեն յուրաքանչյուր ծախս, իսկ հետո ծախսերը հավասարապես բաժանեն, ինչպես մենք արեցինք:

Ինչպես և շատ այլ բաներ, այս խնդիրը կարող է ներկայացվել գրաֆիկով.

Նման գրաֆիկը պետք է գագաթ ունենա խմբի յուրաքանչյուր ընկերոջ համար: Ուղղորդված եզրը ներկայացնում է վճարման պարտավորություն:

Եթե ​​գագաթից արտաքին եզր կա, ապա սկզբնական գագաթի ընկերը պարտական ​​է վերջավոր գագաթի ընկերոջը:

Արժեքը ներկայացված է եզրի կշռով:

Ահա այսպիսի գրաֆիկի օրինակ.

Եկեք ամփոփենք յուրաքանչյուր ընկերոջ մնացորդները (առաջին թիվն այն է, թե յուրաքանչյուր մարդ որքան է պարտք, իսկ երկրորդը, թե որքան է նա պարտք).

Ալիս՝ (-80+40) = -40

Բոբ՝ (-30+30) = 0

Չարլզ՝ (-60+40) = -20

Դիլան՝ (-20+80) = 60

Եթե ​​հաշվեկշիռը բացասական է, ապա տվյալ անձը պետք է վճարի մյուսներին (ուղևորության ընթացքում նա վճարել է ավելի քիչ, քան մյուսները): Եթե ​​մնացորդը դրական է, ապա կոնկրետ անձը ճանապարհորդության ընթացքում վճարել է ավելի շատ, քան մյուսները։

Քանի որ ընկերները համաձայնել են ծախսերը հավասարապես բաժանել, ընդհանուր մնացորդը միշտ պետք է լինի 0:

Մեր նպատակն է նվազագույնի հասցնել վճարումների քանակը և դրանց գումարները, որոնք մասնակիցները պետք է կատարեն ճանապարհորդության ավարտին:

Հենց այստեղ է հայտնվում հանգույցի վերացումը:

Մեր օրինակի գրաֆիկում մենք ինքներս հեշտությամբ կարող ենք նույնականացնել մի քանի հանգույց:

Սկսենք պարզից. Ալիսը պարտք է Չարլզին 20, մինչդեռ Չարլզը Ալիսին 40:

Այս օղակը կարող է վերացվել, եթե մենք հանենք Ալիսի պարտքը Չարլզին (20) այն գումարից, որը Չարլզը պետք է վճարի Ալիսին (40):

Կատարելով այս քայլը՝ մենք արդյունավետորեն վերացնում ենք մեկ օղակ, ինչի արդյունքում Էլիսը ոչինչ չի պարտք Չարլզին, և Չարլզը ստիպված է լինում միայն 40-ի փոխարեն Ալիսին վճարել 20:

Այժմ, երբ մենք հասկանում ենք, թե ինչպես է աշխատում հանգույցի վերացումը, մենք կավտոմատացնենք այս գործընթացը՝ ստեղծելով ալգորիթմ, որը կարող է անել վերը նշված քայլերը նույնիսկ շատ ավելի մեծ գրաֆիկներում:

Մենք կներկայացնենք մեր գրաֆիկը՝ օգտագործելով հիմնական զանգվածը: Մեկնարկային գագաթը կպահվի առաջին ինդեքսում, վերջի գագաթը երկրորդ ինդեքսում, իսկ համապատասխան արժեքը ցույց կտա առաջին անձից մյուսին պարտքի գումարը:

Այսպիսով, մեր օրինակում մեր գրաֆիկի համապատասխան մասը կունենա հետևյալ տեսքը.

$graph['alice']['charles'] = 20;
$graph['charles']['alice'] = 40;

Եկեք տեսնենք մեր կոդի առանցքը.

public function reducePayments(): self 
{

        // Get the first vertex in the graph
        $vertices = array_keys($this->graph);
        $firstVertex = reset($vertices);

        // Loop until there are no more cycles in the graph
        while ($cycle = $this->findCycle($firstVertex)) {
            // Cancel the cycle
            $this->cancelCycle($cycle);
        }

        return $this;

}

Ի՞նչ ենք մենք այստեղ անում։

Մենք փորձում ենք գտնել բոլոր ցիկլերը մեր գրաֆիկում և վերացնել դրանք մեկ առ մեկ:

Մեր findCycle մեթոդը հիմնականում իրականացնում է Depth First Search մեր գրաֆիկում: Ես չեմ պատրաստվում մանրամասնել, թե ինչպես է աշխատում DFS-ը, բայց եթե ձեզ հետաքրքրում է, ապա այս հոդվածի վերջում կարող եք գտնել հղում դեպի ամբողջական աղբյուրի կոդը:

Ցիկլը բացահայտելուց հետո մենք պետք է չեղյալ հայտարարենք այն՝ նվազեցնելով եզրերի քաշը օղակի մեջ ամենացածր քաշով, հետևելով նախորդ օրինակում ցուցադրված նույն մոտեցմանը:

protected function cancelCycle($cycle) 
{
        
     // Find the minimum weight of the cycle
     $min_weight = $this->minWeight($cycle);
        
     // Loop through the edges in the cycle
     foreach ($cycle as list($v, $u)) {
         // Subtract the minimum weight from the edge weight
         $this->graph[$u][$v] -= $min_weight;
     }
        
 }

Այս մեթոդը գտնում է ցիկլի մեջ ամենացածր քաշ ունեցող եզրը և դուրս է բերում այն ​​այդ ցիկլի բոլոր եզրերից:

Եթե ​​որևէ եզրի կշիռը դառնում է 0, ապա մենք այլևս այն չենք համարում եզր (և այն կրկին ՉԻ օգտագործվի մեր DFS որոնման մեջ).

protected function getAdjacentEdges($v) {
    return array_keys(
        // Do not return those edges which are already reduced to 0 weight ...
        array_filter($this->graph[$v], fn($w) => $w !== 0)
    );
}

Եթե ​​մենք գործադրենք մեր reducePayments մեթոդը, ապա մենք կստանանք հետևյալ նոր գրաֆիկը.

Դուք հեշտությամբ կարող եք ասել, որ այս գրաֆիկը իր մեջ որևէ օղակ չունի:

Եկեք արագ հաշվարկենք մնացորդները կրկին.

Ալիս՝ (-40+0) = -40

Բոբ: (-10+10) = 0

Չարլզ՝ (-20+0) = -20

Դիլան՝ (0+60) = 60

Ինչպես տեսնում եք, մնացորդները չեն փոխվել, սակայն վճարային գործարքների թիվը զգալիորեն նվազել է (8-ից 4):

Սա այն է, ինչ մենք ակնկալում էինք։

Հուսով եմ, որ այժմ դուք կարող եք բացատրել հանգույցի վերացումը ձեր ընկերներին, ինչպես նաև ճանապարհի վրա երկար ճանապարհորդությունների ժամանակ:

Ամբողջական սկզբնական կոդը կարելի է ներբեռնել այստեղից՝ https://gist.github.com/dihjital/e4353725a27dbbe12da402d771467883