Mensen aan gebouwen toewijzen met respect voor voorkeuren?

Een vriend stelde me vandaag een vraag over een toewijzingsprobleem. Ik vond een vrij eenvoudige oplossing, maar ik denk dat het eenvoudiger en sneller kan worden gemaakt. Uw hulp wordt op prijs gesteld.

Het probleem: Ervan uitgaande dat ik N mensen heb, moet ik ze toewijzen aan M gebouwen, elk gebouw kan K mensen bevatten. Niet alle mensen zijn bereid om met elkaar samen te leven, dus ik heb een matrix van N * N-cellen en een 1 die de mensen markeert die bereid zijn met elkaar te leven. Als een cel 1 bevat, betekent dit dat ik en J samen kunnen leven. Het is duidelijk dat de matrix symmetrisch is rond de hoofddiagonaal.

Mijn oplossing is als volgt (pseudo-code):

int[] Match(int[] people, int[][] pairs, int numBuildings, int buildingsSize)
{
    int[] freePeople = findFreePeople(people);
    if(freePeople) = 0 
    {
        return people;
    }

    foreach(int person in freePeople)
    {
        for(int buildingIndex=0 to numBuildings)
        {
            if( CheckIfPersonFitsInBuilding(...) )
            {
                int[] tempPeople = people.Copy();
                tempPeople[person] = buildingIndex;
                int[] result = Match(tempPeople,pairs,numBuildings,buildingsSize);
                if(result != null)
                {
                    return result;
                }
            }
        }
    }
    return null;
}

Ik bedek alle mogelijke arrangementen met recursie. Ik denk dat dit enorm kan worden geoptimaliseerd, en ik heb het niet over heuristiek, maar een oplossing met veel minder complexiteit.

  1. Is er een formeel bekend probleem dat hierop lijkt?
  2. Is er een beter algoritme?

Ik denk dat dit mogelijk te maken heeft met het stabiele huwelijksprobleem , hoewel ik het niet zeker weet .

 17
toegevoegd bewerkt
Bekeken: 2
de bron
ja ru fr es de
@templatetypedef kunt u mij alstublieft uitleggen wat er mis was met de naam? het is een fatsoenlijk "Something Problem" is een tekstboeknaam ...
toegevoegd de auteur AK_, de bron
Oh nou ja........
toegevoegd de auteur AK_, de bron
Ik denk niet dat het stabiele huwelijksprobleem hier van toepassing is; dat is gerelateerd aan het bipartiete afstemmingsprobleem en dit probleem is geen overeenkomst.
toegevoegd de auteur templatetypedef, de bron
Het woord "probleem" wordt vaak gebruikt in titels als "Probleem met C ++" of "Probleem met HTML" die niet beschrijven wat het probleem is. Ik ben het met je eens dat het een beetje raar is om de naam te verbieden, omdat dit kan leiden tot valse positieven zoals deze.
toegevoegd de auteur templatetypedef, de bron

3 antwoord

Dit probleem staat bekend als NP-hard door een reductie van het NP-complete probleem van het ontbinden van een grafiek in kliekjes (het probleem met kliekomslag ).

Eerst wat terminologie en discussie. Een kliek in een grafiek is een set van k verschillende knooppunten, zodanig dat elk knooppunt is verbonden met elkaar knoop in de kliek. Een onafhankelijke verzameling in de grafiek is een set van k verschillende knooppunten zodat geen twee knooppunten zijn met elkaar verbonden. Als u een grafiek G neemt en vervolgens randen invoert wanneer een rand ontbreekt en alle randen verwijdert die eerder bestonden, krijgt u de complementeer grafiek van de originele grafiek. Dit betekent dat het probleem van het vinden van een kliek in een eerste grafiek gelijk is aan het vinden van een onafhankelijke reeks in de complementgrafiek.

De reden dat dit interessant is, is dat je in het probleem dat je beschrijft een grafiek krijgt met mensen waarbij elke rand aangeeft "deze twee mensen kunnen niet samen worden gehuisvest". Bijgevolg kun je het probleem dat je beschrijft beschouwen als een manier om de grafiek te doorbreken in k subfoto's, die elk een onafhankelijke set zijn. Als je het complement van deze grafiek construeert, krijg je de grafiek van alle mensen die oké zijn om bij elkaar te worden geplaatst. In dat geval wil je de groep opbreken in k-groepen die allemaal kliekjes zijn.

Het is bekend dat het volgende probleem NP-compleet is:

Kunt u, gegeven een grafiek en een getal k, de knooppunten in de grafiek uit elkaar halen in k cliques?

We kunnen dit probleem in polynomiale tijd reduceren tot uw probleem, wat aantoont dat uw probleem NP-hard is. De constructie is eenvoudig - gegeven de eerste grafiek G en nummer k, construeer eerst het complement van G. Dit betekent dat als je het complement in k onafhankelijke sets kunt breken, de originele grafiek G uit elkaar kan worden gebroken in k cliques (omdat van de dualiteit tussen cliques en onafhankelijke sets). Neem nu deze nieuwe grafiek en converteer deze in een reeks mensen, één per knoop, waar twee mensen niet in dezelfde ruimte als elkaar kunnen worden geplaatst als hun knooppunten in de oorspronkelijke grafiek waren verbonden. Nu is er een manier om deze mensen in k huizen te verspreiden als het complement van G kan worden opgesplitst in k onafhankelijke sets als G kan worden opgesplitst in k klieken. Bijgevolg kan het bekende NP-volledige probleem van kliekbedekking worden gereduceerd tot uw probleem in polynomiale tijd, dus uw probleem is NP-hard. Om ervoor te zorgen dat elke onafhankelijke set in een huis kan passen, stelt u de maximale capaciteit van elke kamer in op n, het aantal knooppunten in de grafiek. Hierdoor kan elke onafhankelijke set in elke kamer worden ondergebracht.

Omdat je probleem NP-hard is, kan er geen polynomiale-tijdoplossing zijn tenzij P = NP. Daarom is er, zo goed als niemand weet, geen algoritme met een polynoomtijd en is de recursie van je backtrack misschien wel de optimale oplossing.

Ik hoop dat dit helpt!

25
toegevoegd
de bron

templatetypedef gaf een heel mooi bewijs waarom het probleem NP-hard is en heeft geen (bekende) polynomiale tijdoplossing.

Zoals met veel NP-harde problemen, betekent dat echter niet dat je het niet efficiënt in de praktijk kunt oplossen of dat je een brute-force-oplossing niet kunt verbeteren.

In het bijzonder moet u kijken naar problemen met constraint-tevredenheid . Ze zijn een algemenere klasse van problemen die precies beschrijven wat je probeert op te lossen. Gegeven een reeks beperkingen, wat zijn de waarden die aan alle beperkingen voldoen?

Het boek AIMA heeft een heel mooi hoofdstuk over hoe je los dit soort problemen op. Ik stel voor dat je daarover leest, want er is veel goede informatie en het is heel toegankelijk omdat het boek is ontworpen voor het niet-gegradueerde niveau. Ik zal je een paar van de grote ideeën geven hier:

De belangrijkste vragen zijn:

  • Welke student moet als volgende worden toegewezen in uw recursie?
  • In welke volgorde moeten de gebouwen voor die student worden beschouwd?

Hier zijn twee heuristieken voor:

  • Minimum remaining values (MRV) heuristic: When choosing which student to assign to a building next in your recursion, choose the student with the fewest choices left.
  • Least constraining value (LCV) heuristic: After deciding what student to look at, assign the building that rules out the fewest choices for the remaining students

Voor de MRV-heuristiek verbreek je de band door de student te kiezen die de meeste beperkingen heeft voor de andere studenten. Het idee achter deze heuristieken is dat u zoekpaden wilt kiezen die het meest waarschijnlijk zullen slagen (LCV). Maar gezien een bepaald zoekpad wilt u zo vroeg mogelijk falen om de hoeveelheid tijd die op dat pad wordt doorgebracht te verminderen (MRV).

In plaats van naïeve recursie met standaard voorwaartse controle, zou u ook een meer geavanceerd zoekalgoritme moeten gebruiken, zoals AC-3 dat verder kijkt.

Gezien problemen met constraint-tevredenheid zo vaak voorkomen in veel softwaretechnologietoepassingen, zijn er al een hoop open bibliotheken die oplossen ze op een efficiënte manier kunnen oplossen. Natuurlijk wordt dit gegeven gegeven dat het probleem dat je probeert op te lossen een echte toepassing is en geen huiswerkopdracht van soorten.

13
toegevoegd
de bron

Een leuke manier om deze problemen op te lossen, is door een beperkende oplosser te gebruiken voor eindige domeinen.

Gebruik bijvoorbeeld GNU-Prolog:

solve(Out):-
    People = [Jon, Mary, Alice, Smith, Dick, George, Betty, Lucy],
    fd_domain(People, 0, 3),    % people lives in buildings 0 to 3.
    fd_atmost(4, People, 0),    % at most, 4 people may live in building 0
    fd_atmost(3, People, 1),    % at most, 3 people may live in building 1
    fd_atmost(2, People, 2),    % etc.
    fd_atmost(1, People, 3),
    Jon   #\= Mary,             % Jon hates Mary
    Alice #\= Smith,            % etc.
    Betty #\= Lucy,
    Jon   #\= Alice,
    Dick  #\= George,
    fd_labeling(People),        % iterate until an acceptable combination is found.
    People = Out.

:- solve(O), write(O), nl.

Vanuit een complexiteitsperspectief blijft dit NP-compleet. Maar de constraint solver kan de manier waarop de toewijzingen worden uitgevoerd op de labelstap opnieuw ordenen zodat dead ends vroeg worden gevonden, wat resulteert in een kleinere zoekboom.

4
toegevoegd
de bron