Vraag over matrix

[sylvester-ponte]

ik ben heel benieuwd naar de reactie van TS
mijn interpretatie van de vraag is
zoek een verzameling unieke cellen uit een matrix van 100 * 100 zodanig dat
de cellen zijn zodanig over de matrix verdeeld, dat er in iedere rij en in iedere kolom van de matrix slechts één cel voorkomt,
dat de hoogste min de laagste waarde van de verzameling zo klein mogelijk is

groet sylvester

 

[Thoralf]

Door de voortdurende reactietijd van TS in samenhang met de intrigerende probleemstelling kom ik tot de conclusie dat ik in mijn reactie, bericht 20, toch een tweetal aanpassingen moet doen:

5 - tenslotte dient de som van de verschillen per koppel minimaal te zijn.

dient te worden gewijzigd in:

5 - tenslotte dient het verschil van de celwaardes van de cellen die slechts éénmaal voorkomen (dus het begin en het einde van de reeks) minimaal te zijn.

en daarmee samenhangend dient de probleemstelling voor de puur wiskundigen

Probleemstelling:
Vindt binnen de verzameling van knooppunten het kortste pad bestaande uit n knopen, zodanig dat er geen deelverzameling van knopen is die meer dan één knoop bevat en de labeling van de verbindingen van de knooppunten niet negatief is en oplopend in grootte.

te worden gewijzigd in:

Probleemstelling:
Vindt binnen de totale verzameling van knooppunten een deelverzameling bestaande uit n knopen, zodanig dat er geen deelverzameling van knopen (van de oorspronkelijke groep van deelverzamelingen) is die meer dan één knoop bevat en de labeling van de verbindingen van de knooppunten niet negatief is en oplopend in grootte, waarbij de labeling van de directe verbinding van de begin- en eindknoop minimaal is.

Daarnaast roept de formulering van bericht 10 van TS nog vragen op, maar mede met het oog op de implicaties daarvan kan ik die nog niet echt formuleren. Ik wacht daarom voorlopig maar even de reactie van TS af.


Tenslotte moet ik nog een nadere precisering van de formele definitie geven. Daarin moet

We hebben een graaf met n-kwadraat knopen, waarbij de knopen zodanig zijn in te delen, dat er 2 maal n deelverzamelingen van knopen ontstaan met als eigenschap dat de doorsnede van ieder tweetal deelverzamelingen uit slechts één element bestaat. Daarbij geldt dan tevens dat iedere knoop voorkomt als doorsnede van een tweetal deelverzamelingen.

vervangen worden door:

We hebben een graaf met n-kwadraat knopen, waarbij een 2-tal sets van ieder n deelverzamelingen kan worden beschreven, zodanig dat iedere deelverzameling n knopen bevat, per set de doorsnede van ieder tweetal deelverzamelingen leeg is en de doorsnede van een deelverzameling uit de ene set met een deelverzameling uit de andere één en slechts één knoop bevat. Daarbij geldt dan tevens dat iedere knoop voorkomt als doorsnede van een dergelijk tweetal deelverzamelingen.

 

[sylvester-ponte]

Toralf ???????
dit lijkt wel ambtenaren praat
meestal kan ik je aardig volgen.

het gaat volgens mij niet om de som van allen cellen uit de gevonden verzameling,
maar om het verschil tussen de cel met de hoogste waarde en de cel met de laagste waarde.

dus stel je vindt uit een 4 x 4 matrix 2 oplossingen met de waarden:
1,3,3,3 -->som=10 hoogste-laagste=2
1,1,1,4 -->som= 7 hoogste-laagste=3
dan wordt voor de eerste gekozen, op basis van hoogste-laagste

groet sylvester

 

[Thoralf]

@ Sylvester
Dit mag dan ambtenarenpraat lijken, het is meer conform het taalgebruik in de wetenschappelijk-wiskundige hoek om onduidelijkheden in interpretatie te vermijden en aan te sluiten bij eerder gedefinieerde begrippen.
Dat ik mede gekozen heb ook deze vorm van probleemstelling te geven komt voort uit het intrigerende karakter van mijn interpretatie van de vraag en het daarbij dan ook voor puur wiskundigen in hun taal binnen hun theoretisch begrippenkader te plaatsen opdat dit kan leiden tot een aanduiding van de naam van een oplossingsalgoritme.

En het klopt ook dat je zegt dat TS kennelijk vraagt om een zodanig pad dat het verschil tussen de hoogste en laagste waarde minimaal is en niet dat de totale padlengte minimaal is. In mijn formuleringen ga ik daar in elk geval van uit.

 

[Thoralf]

De vraag vond en vind ik erg intrigerend. Ik ben er ondanks het feit dat de TS al enige tijd niets van zich heeft laten horen toch verder gegaan en ben thans zo ver dat ik een werkmap operationeel heb die voor een n x n-matrix met n maximaal 1000 (dit vanwege de beperkingen van Excel 2007 en hoger) in elk geval de kleinste waarde en de grootste waarde geeft voor het minimale traject dat wordt gevraagd. Wat nog gedaan moet worden is een daarbij behorende reeks van cellen bepalen. Het algoritme daarvoor heb ik handmatig al wel geprobeerd op het 10 x 10 voorbeeldbestand en daar geeft het een resultaat.
De vermoedelijk enkele enthousiasteling die er ook wel iets in zou zien, die kan mij eventueel mailen op thoralf bij hetepost

Aanvulling:
De gevonden waardes geven de minimale grenzen van het traject aan. Dit betekent dat er geen traject gevonden kan worden dat korter is. Echter er is nog geen garantie dat er binnen deze waardes ook altijd werkelijk een traject realiseerbaar is. De verdeling van de waardes kan in een aantal gevallen roet in het eten gooien: bijv als er een enkele rijen of kolommen zijn die steeds in onderlinge combinatie een reeks waardes bevatten.

 

[snb]

@Thoralf

Ik vind het ook niet erg als je je code hier plaatst.

In jouw interpretatie is het dus niet het handelsreizigersvraagstuk (zo las ik de vraag van TS).

 

[sylvester-ponte]

Thoralf, ik ben heel benieuwd naar jouw benadering van het probleem

bij het maximum de cellen vinden is goed mogelijk, er zullen vele oplossingen zijn, het gaat immers alleen om het verschil tussen laagste en hoogste waarde en dat iedere rij en kolom maar 1 punt bevat
maar bij het minimum is het moeilijker om de tussenliggende cellen te bepalen, ik ben benieuwd naar je algoritme. en de rekentijd

ik ben ook bezig.
voorlopig is (bij mij) de rekentijd voor een 10 * 10 matrix nog ongeveer 15 minuten (om een minimum reeks te bepalen).
ik ben de boel aan het optimaliseren. als de rekentijd binnen de minuut komt zal ik hem hier plaatsen.

de maximum reeks, daar kijk ik niet naar, maar is met een kleine aanpassing van jouw algoritme uit voorgaande post's snel te bepalen.


ik hoop nog steeds een keer wakker te worden met een soort oplossing als het "Hongaarse Algoritme":d

groet en succes

 

[Thoralf]

Bij deze dan.
Bedenk wel dat programmeren in VBA nu niet direct mijn ding is. De specialisten zullen ongetwijfeld een aantal aanpassingen voor efficiency weten.

Aanvulling:
De hierbij geplaatste versie is beperkt tot een 100 x 100 matrix, maar via een eenvoudige aanpassing in de VBA (1 maal een nul toevoegen) is dat te wijzigen in 1000 x 1000.

 

[sylvester-ponte]

Thoralf, er staat in jouw programma ergens
max aantal waardes per kolom = 2 ; wat bedoel je daar mee? bij mij mag iedere kolom maar een keer voorkomen in de oplossing.

groet sylvester

 

[Thoralf]

Waar vindt je die verwijzing?

Ik zie het al: In het begin. Echter dat gedeelte is nog over van mijn eerdere oplossing, en wordt in dit gedeelte niet gebruikt. De regel had, evenals de regel erboven op commentaar gezet kunnen worden.