[C] For-loop over deelverzameling A \ B

[Knakker]

Voor mijn afstudeerscriptie ben ik o.a. bezig met performance-analyse van enkele algoritmes die betrekking hebben op het asymmetrische handelsreizigers-probleem. Die analyse gebeurt deels theoretisch maar ook deels experimenteel. Daartoe ben ik bezig implementaties te schrijven in de taal die als OR-industrie-standaard gehanteerd wordt, namelijk C. Het probleem is dat ik met C specifiek niet veel ervaring heb (wel Pascal, Delphi, Matlab, PHP, ASP en Perl).

Ten behoeve van de efficientie van de implementatie wil ik graag het volgende weten (ik kan niets vinden op google; wellicht gebruik ik de verkeerde zoektermen):

Stel, ik heb een initiële verzameling A = {1,2,3,4,5,6,7,8,9,0} en een verzameling B die in willekeurige volgorde elementen uit A bevat. Hoe creëer ik een for-loop over alle items A \ B?

Idee daarachter is dat ik bij elke iteratie een item uit A aan B toevoeg, die bij de volgende iteratie dus overgeslagen kan worden. Dit wil ik - indien mogelijk natuurlijk - doen zónder gebruik te maken van een If-statement aan het begin van de loop die kijkt of het huidige getal bevat is in B (wat vanwege de willekeurige volgorde van de elementen in B een complexiteit n heeft en bij grote netwerken dus énorm veel tijd gaat kosten).

Is dit eenvoudig? Alvast bedankt!

[ Voor 4% gewijzigd door Knakker op 12-09-2005 14:30 ]

[Janoz]

Is A enkel oplopend en ga je de elementen 1 voor 1 af?

Als je enkel het huidige element aan B toevoegd hoef je nooit te controleren omdat je het huidige element dan al afgehandeld hebt en er dus nooit meer langs komt. Haal je toekomstige elementen uit A dan kun je ze gewoon uit die lijst halen en worden ze niet meer behandeld.

Wat je ook zou kunnen doen is zorgen dat B gesorteerd blijft (door een gegarandeerd gebalanceerde BST te gebruiken wordt het toevoegen en het zoeken van een item een orde log N operatie). eventueel kun je een priority queue gebruiken waarbij je items lager dan het huidige item niet toevoegd en tijdens de start van je loop enkel naar de top kijkt. Deze heeft dezelfde complexiteit als het eerdere voorbeeld, maar is heel simpel al gebalanceerd.

[MSalters]

C heeft dit soort functionaliteit niet standaard. In C++ is het niet al te ingewikkeld, maar ja.

Jouw probleem is bovendien dat A unsorted is. Je zult een verzameling B' moeten maken wat de gesorteerde versie is van B. Vervolgens kun je in O(logN) tijd bepalen of een element in A ook in B' zit (bsearch( ) functie) en zoniet, dan zit dat element in A\B

[Knakker]

De volgorde waarin de elementen in B geplaatst worden is belangrijk; ze geven namelijk de route langs het netwerk aan.

We hebben een netwerk met N steden en een kostenmatrix C(i,j) die de onderlinge afstand tussen stad i en j definieert. We zijn op zoek naar de kortste route langs alle steden die begint in stad 1 en daar ook weer uitkomt. Dit probleem, bekend als het handelsreizigersprobleem, is NP-hard en derhalve niet op te lossen. Wel bestaan er een aantal heuristieken die een oplossing genereren; daar houd ik mij mee bezig, en dan specifiek het geval waarin c(i,j) ongelijk is aan c(j,i) - asymmetrisch dus.

Ik zal de simpelste heuristiek ter illustratie gebruiken (de heuristieken waar ik voor mijn scriptie mee werk zijn een stukje ingewikkelder ); deze heet heet 'Nearest Neighbour' (NN): de NN-heuristiek gaat steeds naar de stad die het dichtste bij ligt mits deze nog niet bezocht is, om uiteindelijk naar de beginstad terug te keren.

Mijn verzameling A bestaat uit alle steden en verzameling B de tot nu toe afgelegde route. Op het moment dat de heuristiek besluit dat we van stad i naar stad j moeten gaan, moet voorkomen worden dat vanuit elke andere willekeurige stad terug in i terecht gekomen kan worden - immers, we zijn er reeds geweest. De eenvoudigste manier is simpelweg alle kostenelementen in de i^e kolom van de matrix op oneindig te zetten; op die manier zal de heuristiek niet terugkeren naar stad i (kosten zijn oneindig en er zal dus een goedkoper alternatief zijn).

De oplettende persoon ziet dat de elementen in de i^e kolom van steden die de heuristiek reeds bezocht heeft niet op oneindig gesteld hoeven te worden; de heuristiek zal daar niet meer terugkomen en deze rijen kunnen dus ongemoeid blijven.

In dit voorbeeld is het ws. efficienter gewoon de betreffende kolom van alle rijen op oneindig te zetten; ik heb echter te maken met heuristieken die een stuk complexer zijn en daar valt (volgens mij) wel een voordeel te behalen indien er een dergelijke efficientere manier bestaat om over deelverzamelingen te loopen.

Suggesties worden met open armen in ontvangst genomen

[igmar]

Knakker schreef op maandag 12 september 2005 @ 14:29:
Stel, ik heb een initiële verzameling A = {1,2,3,4,5,6,7,8,9,0} en een verzameling B die in willekeurige volgorde elementen uit A bevat. Hoe creëer ik een for-loop over alle items A \ B?

Misschien handig om van A \ B een uitleg te geven voor degenen waarvan de wiskunde wat erg roestig is (waaronder ik dus).

Idee daarachter is dat ik bij elke iteratie een item uit A aan B toevoeg, die bij de volgende iteratie dus overgeslagen kan worden. Dit wil ik - indien mogelijk natuurlijk - doen zónder gebruik te maken van een If-statement aan het begin van de loop die kijkt of het huidige getal bevat is in B (wat vanwege de willekeurige volgorde van de elementen in B een complexiteit n heeft en bij grote netwerken dus énorm veel tijd gaat kosten).

Aangezien ik de verzamelingen niet snap : geen idee. C kent echter alleen wat simpele types en structuren, en ik denk niet dat die bruikbaar zijn. Maar goed, aangezien ik niet precies snap wat je nu eigenlijk wil kan ik hier verder weinig zinnigs over zeggen.

[MSalters]

Geen probleem. Weliswaar verandert B, maar het update van B' is niet veel extra werk (O log(N) per stap).

In feite zoek je naar een algoritme om A\B opnieuw te berekenen terwijl B verandert. Dat is niet handig; je kunt beter A\B een keer berekenen en vervolgens bedenken hoe A\B als B verandert zonder A\B opnieuw te bepalen.

[Ivo]

*knip*
Hier stond onzin.

[ Voor 93% gewijzigd door Ivo op 12-09-2005 18:16 ]

[Zoijar]

Hash table is ook een optie. Als je een genererende functie van set B hebt is het triviaal om te kijken of een element van A ook in B zit. Deze functie kan je benaderen met specifieke hash functies. Met sorteren zou het bij iteratie over alle elementen van A, en dan zoeken in B een O(n log n) operatie zijn, met hash tables is dit worst case, en zal het average case veel sneller zijn, ideaal O(n).

(als je range beperkt is, dus bv interval het [0,9], dan kan je met buckets werken, ie. ideale hash functies. Je alloceert gewoon een array met 10 bools, en om te kijken of een element n in B zit zoek je array[n] op. Maar met teveel mogelijkheden kost dit teveel, en dus een beperkende hash functie. Overigens kan je dit ook op A doen, en A\B direct bijhouden als je B genereert. Dat scheelt weer. Het ligt er maar aan wat groter is, en of je B toch al doorloopt of niet.)

[ Voor 38% gewijzigd door Zoijar op 12-09-2005 18:54 ]

[Grijze Vos]

A is gesorteerd (n elementen), en B niet (m elementen).
Als je nu een set A' maakt en daarna alle elementen van B verwijderd uit A' (kan in +- orde m * log n).

Is dat misschien een idee? Hangt een beetje van de grootte van B af gok ik.