[java / algoritme]

[Dieter]

hoi,

ik heb een probleem

ik heb 2 lijsten. Eentje van 5 elementen lang en eentje van 30 elementen lang. Dit is in mijn testprogramma en dus ZEER beperkt. Uiteindelijk gaan er heel grote lijsten gebruikt moeten worden.

De bedoeling is van een zoekboom op te stellen. Elk element wordt met elk andere element verbonden. En alle mogelijke combinaties moeten voorzien zijn. Op dit moment implementeer ik een Depth First Search algoritme. Maar de complexiteit is te hoog !

30^5 = al een groot getal. En aangezien dit maar een testcase is zal ik dus een algortime moeten zoeken met een lagere complexiteit.

Ik heb al zitten zoeken en nadenken, maar kom er echt niet uit. Ik heb wel wat extra informatie over de mogelijke links, maar die is niet echt voldoende om serieuze cuts te maken in zoektijd ...

Heeft er iemand suggesties ?

[Alarmnummer]

Als je een hashcode kan berekenen, dan zou je ook een hashstructuur kunnen gebruiken. Dan heb je O(c)

En verder vind ik het vreemd dat iedere element uit de lijst is verbonden met ieder ander element. Je hebt dan ook geen boom, maar een netwerk.

[ Voor 53% gewijzigd door Alarmnummer op 31-03-2003 18:13 ]

[Dieter]

Alarmnummer schreef op 31 March 2003 @ 18:11:
Als je een hashcode kan berekenen, dan zou je ook een hashstructuur kunnen gebruiken. Dan heb je O(c)

maar dan verandert de complexiteit toch niet ?

[Alarmnummer]

Dieter schreef op 31 maart 2003 @ 18:13:
[...]


maar dan verandert de complexiteit toch niet ?

Als je een hashstructuur kan gebruiken wel. Ongeacht het aantal elementen ben je altijd een constante hoeveelheid tijd kwijt.

Maar je moet eerst maar eens beter uitleggen wat voor soort elementen er in die lijst komen te staan. Want ik kan hier eerlijk gezegd niet veel mee.

[ Voor 22% gewijzigd door Alarmnummer op 31-03-2003 18:15 ]

[Dieter]

ok, fijn

maar een hashfunctie is niet mogelijk ... er wordt trouwens nog een evaluatie gedaan op de gevonden combinaties en die vraagt ook tijd ...

Maar deze optie ga ik toch eens bespreken met mijn mede programmeur. Nog tips ? of ideeën ?

[Alarmnummer]

tip: meer uitleg over het probleem. Ik kan hier niets mee.

En waarom is een hashfunctie niet mogelijk?

[edit]
misschien heb je hier nog iets aan.

[ Voor 63% gewijzigd door Alarmnummer op 31-03-2003 18:24 ]

[Dieter]

ok, het probleem is als volgt :

ik heb een aantal velden in een database. Die wil ik linken aan velden in een kennis-databank. Deze links ga ik evalueren met een evaluatieboom.
Nu wil ik een boom genereren die al deze mogelijke combinaties uitprobeerd en evalueert. Dat is me gelukt, enkel deze is VEEL te traag. 37 seconden voor 5 velden uit de kennis databank en 30 velden uit de echte databank.

Mijn 2 lijsten zijn dus langs de ene kant DbFields (objecten). Die ik op voorhand genereer. En PredArguments, die uit het kennis schema komen. Deze lijsten zijn arrayLists

Uiteindelijk is 1 oplossing de beste. En dat moet mijn algoritme uiteindelijk zoeken. Heb ook al gedacht van bepaalde takken gewoon af te snijden... Maar heb geen idee hoe !

Dat is het probleem... vergeet ik nog iets ?

edit:

bedankt voor de link, ga hem eens bekijken

[ Voor 4% gewijzigd door Dieter op 31-03-2003 18:37 ]

[Alarmnummer]

Je zou misschien kunnen proberen om een minder optimale combinatie zo vroeg mogelijk te detecteren, en die tak af te snijden. Verder weet ik niet echt een betere oplossing voor je probleem.

[Alarmnummer]

Wat je eventueel ook nog kan doen is stukken van een expressie laten staan.

vb:

stel dat ik (a+b)+c heb, en a b en c kunnen varieren van 1..5.

Je krijgt dan:
1+1+1
1+1+2
1+1+3 etc

Maar je kan ook zeggen:

2+1
2+2
2+3

Je berekent eerst a+b en dan ga je over c roteren, net zolang totdat het niet meer kan en dan neem je de volgende van b (2 dus) en doe je het weer opnieuw. Hierdoor neemt de lengte van de te berekenen expressies af.

[ Voor 30% gewijzigd door Alarmnummer op 31-03-2003 18:58 ]

[Soultaker]

Ik vind het echt knap dat Alarmnummer al zoveel heeft kunnen helpen, want ik begrijp nog steeds niets van het probleem (of de probleemomschrijving). Misschien kun je een voorbeeldje geven?

Ik zie namelijk niet zo 1-2-3 hoe je met twee lijsten 'elk element wordt met elk andere element' gaat verbinden en hoe je dan opeens op 30 ^ 5 (maar niet 5 ^ 30?) iteraties komt. Misschien moet je ook eens redeneren vanuit je doel, in plaats van de implementatie die je schijnbaar al vastgesteld hebt (maar niet erg praktisch blijkt te zijn).

[SWfreak]

Als je ieder van de vijf elementen uit de ene lijst met alle 30 de elementen uit de andere lijst wil combineren heb je toch 5*30=150 combinaties Zie niet helemaal in wat je hier met een DFS wilt.

[Dieter]

Nee zo simpel is het niet :

Stel we hebben één lijst : [A B C]
en een andere lijst [1 2 3]

dan wil ik ALLE MOGELIJKE combinaties checken op hun 'correctheid' dus :

code:

  1A 
   |
 -----
 |    |
 2B 2C
 |     |
---   ----
|      |
3C    3B

 1B 
   |
 -----
 |    |
 2A 2C
 |     |
---  ----
|      |
3C    3A


 1C 
   |
 -----
 |    |
 2B 2A
 |     |
---  ----
|      |
3A    3B

dit zouden mogelijke combinaties zijn... de takken bijvoorbeeld [1c , 2b , 3a] worden ge-evalueerd op hun correctheid. Ze krijgen een gewicht. De tak die uiteindelijk het beste gewicht oplevert, die is de beste en zal uiteindelijk gekozen worden.

Ik hoop dat het wat duidelijker is zo... het heeft ook even geduurd voor ik alles doorhad

[Soultaker]

Dat werkt toch niet met de ongelijke lijsten zoals je in je eerste bericht vermeldde?

Voor twee lijsten van elk N elementen, is het aantal verschillende paringen N! (== N faculteit); dat komt inderdaad in de buurt van N^M.

Daarmee beantwoord je echter nog niet de vraag wat je er nu eigenlijk mee wilt? Wat wil je controleren en wat denk je daarmee te bereiken? Weet je zeker dat dit de beste manier is om je doel te bereiken?

[Dieter]

Soultaker schreef op 31 March 2003 @ 22:51:
Dat werkt toch niet met de ongelijke lijsten zoals je in je eerste bericht vermeldde?

Voor twee lijsten van elk N elementen, is het aantal verschillende paringen N! (== N faculteit); dat komt inderdaad in de buurt van N^M.

Daarmee beantwoord je echter nog niet de vraag wat je er nu eigenlijk mee wilt? Wat wil je controleren en wat denk je daarmee te bereiken? Weet je zeker dat dit de beste manier is om je doel te bereiken?

mh, het werkt wel met ongelijke lijsten ...niet alle waarden uit de kennis-tabel moeten namelijk gebruikt worden... nu ja ik wil de beste combinatie zoeken. Ik heb een algoritme dat de combinaties evalueert.

Het werkt al. Maar het gaat VEEL te traag. Ik ben er niet zeker van dat dit de beste oplossing is maar volgens mij wel de enigste.

Ik vrees dat ik het niet beter kan uitleggen ...

Die n^m heb ik van mijn stagementor ... misschien was ie fout
Ik zal morgen nog eens een team gesprek aanvragen

[Verwijderd]

dit zouden mogelijke combinaties zijn... de takken bijvoorbeeld [1c , 2b , 3a] worden ge-evalueerd op hun correctheid. Ze krijgen een gewicht. De tak die uiteindelijk het beste gewicht oplevert, die is de beste en zal uiteindelijk gekozen worden.

Ik hoop dat het wat duidelijker is zo... het heeft ook even geduurd voor ik alles doorhad

Misschien zou je nog even kunnen uitleggen aan welke voorwaarden een tak moet voldoen, om als beste tak geselecteerd te worden. Met andere woorden kun je uitleggen hoe het gewicht berekent wordt en wanneer dat gewicht optimaal is.

[Dieter]

Die eisen worden in een evaluatie boom gezet. Deze kent het gewicht van combinaties.

vb : gewicht 1c = 10.

De boom bevat ook operatoren die gewichten kan bewerken (AND / OR / NOT / + / - / MAX / MIN)
Zo wordt een gewicht berekent voor een tak. De beste tak is diegene met het grootste gewicht

[Soultaker]

Dieter schreef op 31 March 2003 @ 23:07:
Die n^m heb ik van mijn stagementor ... misschien was ie fout

In het nieuwe scenario (met N < M en je combineert elk van N met 1 van M, waarbij sommige M overblijven) kom ik op M! / (M - N)!, maar dat is wel ongeveer N^M geloof ik (maal een constante factor).

Dieter schreef op 01 April 2003 @ 12:24:
Die eisen worden in een evaluatie boom gezet. Deze kent het gewicht van combinaties.

Hoe ziet zo'n ding er uit dan? Hoe doorloop je die? Kun je misschien een kort maar compleet voorbeeld geven (met bijvoorbeeld N=4 en M=6 ofzo).

[ Voor 32% gewijzigd door Soultaker op 01-04-2003 13:15 ]

[Juup]

Hmmm de mist trekt langzaam op.
Je wilt van alle mogelijke meta-combinaties weten wat het gewicht is, en daar de maximale van hebben. De vraag is nu of er trucjes zijn om het sneller te doen.

Is het gewicht ook afhankelijk van andere nodes in dezelfde tak? M.a.w. als 2c onder 1a hangt, heeft die dan een ander gewicht dan wanneer hij onder 1b hangt?

Zo niet, dan kun je die 2c opslaan en vaker gebruiken, dat scheelt rekentijd (maar kost memory)

[ Voor 1% gewijzigd door Juup op 01-04-2003 13:27 . Reden: typo ]

[PiepPiep]

Is het niet een idee als het een benadering van oneindig duurt om de perfecte te vinden, om dan maar niet de perfecte te vinden maar een die daar redelijk in de buurt komt?

[Dieter]

Juup schreef op 01 April 2003 @ 13:27:
Hmmm de mist trekt langzaam op.
Je wilt van alle mogelijke meta-combinaties weten wat het gewicht is, en daar de maximale van hebben. De vraag is nu of er trucjes zijn om het sneller te doen.

Is het gewicht ook afhankelijk van andere nodes in dezelfde tak? M.a.w. als 2c onder 1a hangt, heeft die dan een ander gewicht dan wanneer hij onder 1b hangt?

Zo niet, dan kun je die 2c opslaan en vaker gebruiken, dat scheelt rekentijd (maar kost memory)

Wel, een evaluatie boom KAN rekening houden met deze combinatie. Er kan bijvoorbeeld instaan :

"ALS er een element c aan een element 1 hangt EN een element a aan een element 2 hangt DAN is het gewicht 15"

het probleem is dat zowel de combinaties als de evaluatieboom helemaal niet vastligt. Ik weet dus niet op voorhand welke evaluaties voordeliger zullen zijn.

Dit probleem lijkt me vrij onoplosbaar voor veel elementen ...

[Verwijderd]

Je gaat nu alle combinaties langs die er mogelijk zijn, maar misschien is het handiger om in plaats van alle combinaties langs te gaan 1 combinatie op te bouwen met behulp van gegevens die je al hebt. Dat is volgens mij veel sneller, neem een japanse puzzel bijvoorbeeld. Je kunt bij een japanse puzzel alle mogelijkheden nagaan om tot de juiste uitkomst te komen, maar je kunt ook met behulp van de gegevens die je hebt de uitkomst "berekenen".