grootste afstand tussen 2 punten uit willekeurig verzameling

[H!GHGuY]

Ik moet voor mijn programma dat ik op stage schrijf, uit een set punten in een 2D vlak de 2 punten halen die het verst uit elkaar liggen. De simpele (brute-force) methode is O(n²), en als je die optimaliseert kom je tot O(n log(n)) door geen afstanden dubbel te meten.

Ik ben beginnen denken en zoeken op internet of het niet sneller kon. Toen ik een scriptie las over een onderwerp dat er nauw bij aansluit, kreeg ik plots een idee.
Het komt erop neer dat ik een O(n) methode heb gemaakt. Nu ben ik verder beginnen zoeken op internet, om te weten of dit niet al bestaat, of om iets dergelijks te vinden die ook O(n) levert voor dit probleem, maar ik vind echt niets.

Ik zal nu dus de O(n log(n)) vorm en mijn O(n) oplossing implementeren om te zien of ik door verborgen constanten niet even snel ben als de O(n log(n)) variant. Resultaten zal ik dan hier ook wel posten.

Kan iemand me meer vertellen over dit probleem en of er al O(n) of snellere oplossingen bestaan?
(kortom, mag ik een heel hoofdstuk in mijn thesis aan dit probleem en mijn oplossing ervan besteden, of heb ik het wiel heruitgevonden?)

[MSalters]

Geen afstanden dubbel meten levert je N²/2 op, geen N logN
Overigens geloof ik direct dat er een O(N logN) oplossing is, 2D is wat dat betreft simpel genoeg.

Sneller dan O(N) is overigens triviaal uit te sluiten. Elke oplossing waarbij je minder dan O(N) tijd gebruikt betekent dat je tenminste 1 punt niet bekijkt. Dat punt kan overal liggen, en dus ook deel zijn van het paar punten wat je had moeten hebben .

[Janoz]

Ik ben erg benieuwd naar de O(N) oplossing. Ik kom zelf niet verder dan O(N log N). Ik heb wel een O(N) oplossing middels een convex hull, maar die gaat er vanuit dat alle punten al gesorteerd zijn. En sorteren gaat niet sneller dan O(N log N).

[H!GHGuY]

ik zoek even op het convex hull algoritme, wat het inhoudt...

edit: als ik me niet vergis maakt jouw convex hull oplossing een convexe polygon met de buitenste punten ?

ik heb inmiddels beide methodes (brute-force met optimalisatie en mijn methode) geprogrammeerd
en ben op dit moment aan het testen met random punten.
de resultaten komen al iedere run gelijk uit en de snelheidswinst is VEEL meer dan ik verwacht had.
om eerlijk te zijn geloof ik het bijna niet

[ Voor 78% gewijzigd door H!GHGuY op 23-09-2005 15:37 ]

[Janoz]

Het is niet het convex hull algoritme, maar een convex hull algoritme.

Convex hull is het omsluitend polygon waar alle punten binnenin liggen. Als alle punten spijkers zijn is de convex hull het elastiekje om alle spijkers heen. Ik neem aan dat het makkelijk te bewijzen is dat de twee punten die het verest uit elkaar liggen onderdeel zijn van deze convex hull.

Wanneer je alle punten gesorteerd hebt kun je in O(N) de convex hull bepalen. Van de overgebleven punten kun je vervolgens de grootste afstand bepalen. Als je voor die laatste gewoon alles controleerd dan ligt de complexiteit van dit algoritme in best case(alle punten liggen op een lijn) op O(N) en worstcase (convex hull bestaat uit alle punten) O(N^2).

Maar zoals ik eerder ook vroeg, ik ben best neiuwschierig naar het O(N) algo

[Verwijderd]

Bedenk goed dat als je de boel al moet sorteren, je ALTIJD al O(n log n) bezig bent... Volgens mij is het niet mogelijk in O(n) te doen.

Kijk ook eens naar Plain Sweep algorithmen, veel gebruikt voor dit soort zaken. Kost overigens O(n log n) looptijd, door de sortering.

edit:

Misschien dat je mbv heuristieken de verwachte looptijd nog sneller dan O(n log n) kunt krijgen, theoretisch is worst-case volgens mij sneller dan O(n log n) niet mogelijk.

[ Voor 28% gewijzigd door Verwijderd op 23-09-2005 15:30 ]

[Rac-On]

ik weet niet of er een O(n) oplossing bestaat, maar wat MSalters aangeeft is dat sneller dan O(n) niet mogelijk is.

@BubbelUrp: je gaat altijd uit van een worst-case bij dit soort dingen voor zover mij bekend, omdat je van de werkelijke looptijd alleen een schatting kan maken

[H!GHGuY]

ik moet er wellicht wel bijzeggen dat een minimale fout mogelijk kan zijn wegens 1 afronding.
Als die fout ook werkelijk een invloed KAN hebben op het resultaat, (wat me op het eerste ogenblik niet waarschijnlijk lijkt) moet ik nog even wiskundig uitzoeken.

C++:

int main()
{
    
    srand(time(NULL));
    clock_t start, end;
    xypoint pt1, pt2;
    

    for (int NR = 100; NR < 1000001; NR *=10)
    {
        cout<<"initializing/randomizing: "<<NR<<endl;
        xypoint* pts = new xypoint[NR];
        for (int i = 0; i < NR; i++)
        {
            pts[i].x = (rand()*1.0)/RAND_MAX;
            pts[i].y = (rand()*1.0)/RAND_MAX;
        }
        
        cout<<"starting bruteforce..."<<endl;

        start = clock();
        float dist1 = bruteforce(pts, NR, pt1, pt2);
        end = clock();

        cout<<"distance: " << dist1 << " point1: " << pt1.x << "," << pt1.y
            <<" point2: " << pt2.x << "," << pt2.y << endl << " time: " 
            << (end - start)/CLOCKS_PER_SEC<< "(" << end-start << ")" <<endl;

        cout<<"starting myproggy"<<endl;

        start = clock();
        float dist2 = mine(pts, NR, pt1, pt2);
        end = clock();

        cout<<"distance: " << dist2 << " point1: " << pt1.x << "," << pt1.y
            <<" point2: " << pt2.x << "," << pt2.y << endl << " time: " 
            << (end - start)/CLOCKS_PER_SEC<< "(" << end-start << ")" <<endl;


        delete pts;
    }
    getch();
    return 0;   
}

Dit is m'n main code. ik update straks ff met de resultaten die ik nu aan et draaien ben naar een tekstfiletje

[.oisyn]

Euh ja, wat hebben we aan die main code? Je mine() functie is veel interessanter imho

[H!GHGuY]

.oisyn schreef op vrijdag 23 september 2005 @ 15:54:
Euh ja, wat hebben we aan die main code? Je mine() functie is veel interessanter imho

dat weet'k wel, en daarom post ik em net niet

je moet blijven bedenken dat ik m'n thesis maak, en als het waar is wat ik heb gemaakt, dan heb ik liever niet dat een copy-paster met m'n ID wegloopt voordat ik et in m'n thesis kan schrijven.

[.oisyn]

Er bestaat zoiets als auteursrecht, en door het hier te posten bewijs je alleen maar dat je het nu al gemaakt hebt ipv iemand anders die het later pas publiceert

Maar ik ben gewoon benieuwd, je mag het me ook best mailen, ik zal plechtig beloven het voor mezelf te houden.

[ Voor 26% gewijzigd door .oisyn op 23-09-2005 16:01 ]

[MrBucket]

Verwijderd schreef op vrijdag 23 september 2005 @ 15:24:
Bedenk goed dat als je de boel al moet sorteren, je ALTIJD al O(n log n) bezig bent... Volgens mij is het niet mogelijk in O(n) te doen.

Volgens mij ook niet. O(n) betekent dat je het probleem zonder een zoekstructuur (zoals bv. een binary tree) zult moeten oplossen, en dat er dus een logische volgorde moet zijn in de manier waarop je de punten bekijkt.
En dat zie ik nog niet gebeuren, eerlijk gezegd.

Weet je zeker dat je uitvoer in alle gevallen klopt, en dat je geen fout hebt gemaakt in je tijdsanalyse?

[H!GHGuY]

ik heb even wiskundig die fout bekeken.
ze bestaat inderdaad, en ze kan in het slechtste geval ervoor zorgen dat je de op-een-na-grootste afstand vind. maar dit moet omzeilbaar zijn door tijdens het algo deze fout te berekenen op te sporen en te corrigeren.

voor zover ik kan denken is dit dan nog steeds een zelfde orde algoritme.

[H!GHGuY]

MrBucket schreef op vrijdag 23 september 2005 @ 16:10:
[...]

Volgens mij ook niet. O(n) betekent dat je het probleem zonder een zoekstructuur (zoals bv. een binary tree) zult moeten oplossen, en dat er dus een logische volgorde moet zijn in de manier waarop je de punten bekijkt.
En dat zie ik nog niet gebeuren, eerlijk gezegd.

Weet je zeker dat je uitvoer in alle gevallen klopt, en dat je geen fout hebt gemaakt in je tijdsanalyse?

die tijdsanalyse zit in de main die ik gepost heb. (das ook beetje de reden waarom ik ze heb gepost.)

edit:

code:

de huidige voortgang:
initializing/randomizing: 100
starting bruteforce...
distance: 1.24068 point1: 0.150945,0.964232 point2: 0.976287,0.037904 time: 0(0)
starting myproggy
distance: 1.24068 point1: 0.976287,0.037904 point2: 0.150945,0.964232 time: 0(0)
initializing/randomizing: 1000
starting bruteforce...
distance: 1.39325 point1: 0.994171,0.990234 point2: 0.00509659,0.00897244 time: 0(31)
starting myproggy
distance: 1.39325 point1: 0.00509659,0.00897244 point2: 0.994171,0.990234 time: 0(0)
initializing/randomizing: 10000
starting bruteforce...
distance: 1.40708 point1: 0.996673,0.00134281 point2: 0.00482192,0.99939 time: 1(1953)
starting myproggy
distance: 1.40708 point1: 0.996673,0.00134281 point2: 0.00482192,0.99939 time: 0(16)
initializing/randomizing: 100000
starting bruteforce...
distance: 1.41042 point1: 0.00192267,0.000488296 point2: 0.998627,0.998413 time: 223(223359)
starting myproggy
distance: 1.41042 point1: 0.00192267,0.000488296 point2: 0.998627,0.998413 time: 0(31)
initializing/randomizing: 1000000

[ Voor 48% gewijzigd door H!GHGuY op 23-09-2005 16:17 ]

[MrBucket]

HIGHGuY schreef op vrijdag 23 september 2005 @ 16:14:
ik heb even wiskundig die fout bekeken.
ze bestaat inderdaad, en ze kan in het slechtste geval ervoor zorgen dat je de op-een-na-grootste afstand vind. maar dit moet omzeilbaar zijn door tijdens het algo deze fout te berekenen op te sporen en te corrigeren.
voor zover ik kan denken is dit dan nog steeds een zelfde orde algoritme.

Dan is de kans groot dat het antwoord ook willekeurig slecht kan worden, d.w.z. dat het de op 2 na grootste afstand geeft, of op 3 na, etc. Of heb je redenen om aan te nemen dat dat nooit zal gebeuren?

En met tijdsanalyse bedoelde ik de theoretische looptijd, in big-O notatie
M.a.w.: weet je zeker dat het O(n) is?

[Verwijderd]

HIGHGuY schreef op vrijdag 23 september 2005 @ 16:14:
voor zover ik kan denken is dit dan nog steeds een zelfde orde algoritme.

Bewijs dat dan; een stopwatch gebruiken is niet genoeg. Het gaat zoals eerder gezegd om worst-case input, dus niet om het gemiddelde snelheid van je implementatie.

Post een bewijs of het algoritme zodat we het voor je uit kunnen zoeken. Anders ben je er alleen maar omheen aan het draaien

[H!GHGuY]

ik mail het geheel naar .oisyn met het vertrouwen dat hij dit niet publiceert, misbruikt, op zijn naam schrijft of eender wat dat in mijn nadeel of zijn voordeel kan spelen.

Hij kan dan mijn werkwijze bekijken, testen en verifieren dat het inderdaad een O(n) implementatie is.
bovendien leg ik hem ook uit wat de fout kan zijn, en hoe ze gecorrigeerd kan worden.

@oisyn: you have mail

[ Voor 4% gewijzigd door H!GHGuY op 23-09-2005 17:03 ]

[ACM]

Jouw tijden zijn O(log n) toch? Verdubbeling van 16 naar 31 bij vertienvoudiging van het aantal mogelijkheden.
Maak je niet per ongeluk gebruik van een structuur die al in de bruteforce gevuld wordt, waardoor je een deel van het werk overslaat? Of allerlei aannames die wel voor jouw geval kloppen, maar in het algemeen niet? En natuurlijk wat de anderen al gezegd hebben.

Zonee... dan is het waarschijnlijk best een knappe oplossing.

[ Voor 6% gewijzigd door ACM op 23-09-2005 16:51 ]

[Verwijderd]

ACM schreef op vrijdag 23 september 2005 @ 16:50:
Maak je niet per ongeluk gebruik van een structuur die al in de bruteforce gevuld wordt, waardoor je een deel van het werk overslaat?

Dit kan je simpel testen trouwens.. gewoon jouw algo eerst doen en dan de bruteforce

[H!GHGuY]

nee, er gebeuren enkel toewijzingen naar de desbetreffende variabelen.

ik denk zelfs dat je kan zien dat de volgorde van de waarden niet altijd na beide functies gelijk is...

[MisterData]

Verwijderd schreef op vrijdag 23 september 2005 @ 16:58:
[...]

Dit kan je simpel testen trouwens.. gewoon jouw algo eerst doen en dan de bruteforce

Nee, het gaat er om dat de data wordt gegenereerd met een rand() functie. Dan worden de punten redelijk verspreid. Maar wat doet het algoritme als de verdeling wat minder uniform is?

[H!GHGuY]

dan blijft alles lekker werken

@oisyn: you have mail

Ik kan alvast 1 ding zeggen: voor de toepassing waarvoor ik het zal gebruiken is de fout verwaarloosbaar aangezien het resultaten zijn van een meettoestel met een bepaalde nauwkeurigheid.

voor exacte resultaten, moet een klein beetje extra code geschreven worden, maar dit is echter miniem en zou geen invloed mogen hebben, behalve in 1 worst-case scenario. maar om zulke resultaten in dit algo te stoppen moet je wel hard je best doen, ofwel heb je geen voorspelling van je input waarden gemaakt voor je besliste dit algo te gebruiken voor dat ene specifieke doeleinde.

[ Voor 119% gewijzigd door H!GHGuY op 23-09-2005 17:13 ]

[Verwijderd]

MisterData schreef op vrijdag 23 september 2005 @ 17:06:
[...]


Nee, het gaat er om dat de data wordt gegenereerd met een rand() functie. Dan worden de punten redelijk verspreid. Maar wat doet het algoritme als de verdeling wat minder uniform is?

Daar gaat het inderdaad uiteindelijk om Alleen is de verdubbeling van de tijdsduur bij 100x grotere dataset wel vreemd.. dat zou, zoals ACM hinten naar een O(log n) algoritme, wat zeer vreemd is aangezien dit toch echt Omega(n) is (minstens lineaire tijd nodig want elk punt zal toch minstens even bekeken moeten worden als de lijst ongesorteerd wordt aangeleverd).

HighGuy: kan je nog grotere, en wat meer datasets testen met alleen je eigen algo? Dan kan je in ieder geval een schatting maken van wat de complexiteit minimaal moet zijn.

edit: de datasets moeten nog wel in je geheugen passen natuurlijk.. swappen zou wat sneu zijn voor je tijdsmetingen

[ Voor 19% gewijzigd door Verwijderd op 23-09-2005 17:16 ]

[MSalters]

ACM schreef op vrijdag 23 september 2005 @ 16:50:
Jouw tijden zijn O(log n) toch? Verdubbeling van 16 naar 31 bij vertienvoudiging van het aantal mogelijkheden.

Zegt niets: een O(N)stap+O(logN) stap is in totaal O(N), maar indien de constante voor de log N maar groot genoeg is merk je de O(N) stap in eerste instantie niet. En zoals ik al bewezen had is het voor een ongesorteerde collectie onmogelijk om onder de O(N) te komen.

[H!GHGuY]

het is werkelijk wel O(n) hoor:
getuige dit stukje resultaat:

C++:

pts[i].x = log10(i+1);//(rand()*1.0)/RAND_MAX;
pts[i].y = log(i+1);//(rand()*1.0)/RAND_MAX;

resultaat:

code:

initializing/randomizing: 100
starting bruteforce...
starting myproggy
distance: 5.02072 point1: 0,0 point2: 2,4.60517
-time: 0(0)
-time: 0
initializing/randomizing: 1000
starting bruteforce...
starting myproggy
distance: 7.53107 point1: 0,0 point2: 3,6.90776
-time: 0(0)
-time: 0
initializing/randomizing: 10000
starting bruteforce...
starting myproggy
distance: 10.0414 point1: 0,0 point2: 4,9.21034
-time: 0(0)
-time: 0
initializing/randomizing: 100000
starting bruteforce...
starting myproggy
distance: 12.5518 point1: 0,0 point2: 5,11.5129
-time: 0(31)
-time: 0
initializing/randomizing: 1000000
starting bruteforce...
starting myproggy
distance: 15.0621 point1: 0,0 point2: 6,13.8155
-time: 0(344)
-time: 0
initializing/randomizing: 10000000
starting bruteforce...
starting myproggy
distance: 17.5725 point1: 0,0 point2: 7,16.1181
-time: 3(3454)
-time: 3
done... press enter

als ik er nog een factor 10 bij gooi, wil m'n PC niet meer mee wegens het alloceren van geheugen voor de input waarden

[Verwijderd]

HIGHGuY schreef op vrijdag 23 september 2005 @ 17:31:

C++:

pts[i].x = log10(i+1);//(rand()*1.0)/RAND_MAX;
pts[i].y = log(i+1);//(rand()*1.0)/RAND_MAX;

waarom dat?

edit: de random waardes binnen [0.0,1.0] voor beide assen is toch prima? Met deze nieuwe code liggen de punten allemaal op een rechte lijn..

[ Voor 25% gewijzigd door Verwijderd op 23-09-2005 22:47 ]

[H!GHGuY]

dunno ?
gewoon een wiskundige functie ertegenaan schoppen, die geen te grote waarden levert voor grote i...

ik ga nu huiswaarts. ik neem dit alles mee, maar ik zal er deze avond waarschijnlijk niet meer naar kunnen kijken. ik verlang echter naar wat algemene commentaar van oisyn!!

[Verwijderd]

HIGHGuY schreef op vrijdag 23 september 2005 @ 17:36:
ik verlang echter naar wat algemene commentaar van oisyn!!

Yup.. als het kan, zou het leuk zijn. Kon inderdaad op google en google scholar niet iets vinden sneller dan O(n log n).. maar dat kan ook altijd omdat ik niet de officiele naam van het probleem ken

[H!GHGuY]

ik heb net nog even zitten denken.

Het algoritme is eigenlijk zo, dat ik fouten creeer. Als een zeer kleine fout niet erg is, is dit algo ideaal. bvb voor meetresultaten waarop een onnauwkeurigheid kan zitten, of wanneer een heel klein verschil verwaarloosbaar is. Dan heb je O(n) altijd.
De fouten kunnen er echter terug uit gehaald worden. maar dan heb je een algo dat:
- in het beste(?) en gemiddelde(?) geval nog steeds O(n) is.
- in het allerslechtste geval O(n²) (~brute force met optimalisatie)

Ik denk niet dat dit algo een best of gemiddeld geval heeft. enkel een slechtst en een normaal geval.

[.oisyn]

Het algoritme is idd O(n), alleen klopt hij niet, en dat kan ik bewijzen . Ik zal 't je morgen mailen, of hier posten als je daar geen problemen mee hebt.

[writser]

NP probleem lineair oplossen? Bijna een doorbraak in de informatica..

[ Voor 6% gewijzigd door writser op 26-09-2005 03:55 ]

[Macros]

Het is geen NP probleem.

[Ivo]

Macros schreef op maandag 26 september 2005 @ 04:31:
Het is geen NP probleem.

Tenzij P = NP, maar dat zal wel niet.

[writser]

Excuses, het was laat.

[Tomatoman]

De discussie gaat tot dusverre als volgt:

Ik heb een algoritme dat Y oplevert als je er X stopt. En als bewijs laat ik zien dat als ik er A instop, er B uitkomt. Zie je wel dat het algoritme klopt?

Een discussie over hoe een algoritme werkt is natuurlijk onzinnig als je niet wilt verklappen hoe het algoritme eruitziet. Wil de topicstarter dat zijn algoritme op geldigheid wordt gecheckt, dan zal hij het toch echt moeten posten. Omgekeerd: wil de topicstarter zijn algoritme niet openbaren, dan valt er natuurlijk ook niets over te zeggen. Bovendien is hier al meerdere malen aangegeven dat een O(n)-oplossing niet mogelijk is, wat impliceert dat het algoritme niet klopt. Wat is nou eigenlijk de bedoeling van dit topic?

[.oisyn]

Heb je de topic wel helemaal gelezen? Hij heeft mij de code gemaild (ik snap dat hij wat huiverig kan zijn om de code hier maar gewoon te posten als het voor z'n thesis is, en ook nog iets claimt te doen wat veel mensen niet mogelijk achten), en ik zeg dat het niet klopt. Aangezien het niet klopt lijkt me dat het "geheim" houden van het algoritme ook niet meer nodig is, maar ik wacht nog even een reactie van HIGHGuY af

[ Voor 11% gewijzigd door .oisyn op 26-09-2005 13:21 ]

[Cuball]

waar gaat hij in de fout ? was zijn algoritme enkel voor bepaalde gevallen correct?

[Verwijderd]

Macros schreef op maandag 26 september 2005 @ 04:31:
Het is geen NP probleem.

Het is een probleem in P, dus is het ook een probleem in NP. Alleen is het niet NP-compleet (de set van moeilijkste problemen in NP). Ik denk dus dat je 'het is geen NP-compleet probleem' bedoelt

[.oisyn]

Cuball schreef op maandag 26 september 2005 @ 15:28:
waar gaat hij in de fout ? was zijn algoritme enkel voor bepaalde gevallen correct?

Zonder uit te weiden over het algoritme: z'n algoritme heeft een redelijk grote kans om het goede antwoord te rapporteren, alleen is het niet altijd correct. Je kunt het dus meer zien als een benadering.

[Zoijar]

Verwijderd schreef op maandag 26 september 2005 @ 15:43:
Het is een probleem in P, dus is het ook een probleem in NP. Alleen is het niet NP-compleet (de set van moeilijkste problemen in NP). Ik denk dus dat je 'het is geen NP-compleet probleem' bedoelt

offtopic:
er zijn ook 'moeilijke' (waarschijnlijk niet in P) problemen in NP die waarschijnlijk niet in NPC vallen, zoals priem ontbinding of graaf isomorfismen. Anyway, andere discussie

[H!GHGuY]

@oisyn

ik had graag je commentaar in een mailtje ontvangen...
wie weet is m'n algo nog steeds goed genoeg voor mijn doeleinden.

die fout die jij zegt, is die dezelfde als die die ik aangeef, incl oplossing?

edit: ik heb waarschijnlijk een mailtje gezonden vanaf een ***co.com adres?
kun je mailen naar <mijn nick>[@t] gmail pt com ?

[ Voor 25% gewijzigd door H!GHGuY op 26-09-2005 19:32 ]

[Rac-On]

niet heel lullig bedoeld of zo, maar het wordt een beetje een topic waar alleen .oisyn en HIGHGuY iets aan hebben, en daarmee een beetje overbodig hier? 1on1 kan volgens mij heel goed via msn/email oid?

[H!GHGuY]

rac-on schreef op maandag 26 september 2005 @ 19:21:
niet heel lullig bedoeld of zo, maar het wordt een beetje een topic waar alleen .oisyn en HIGHGuY iets aan hebben, en daarmee een beetje overbodig hier? 1on1 kan volgens mij heel goed via msn/email oid?

mijn vraag was oorspronkelijk bedoeld om info te vragen over het probleem, en om te vragen of er nog performante oplossingen/algo's bestonden. Dus als je iets bij te dragen hebt, kun je't nog steeds hier posten. Idem van mijn kant.

[Confusion]

.oisyn schreef op maandag 26 september 2005 @ 16:04:
Je kunt het dus meer zien als een benadering.

Dat is alleen handig als je ook in O(n) kan voorspellen hoe goed de benadering is, maar daarvoor zal je er een aanname in moeten stoppen over de verdeling van de afstanden tussen de punten en daarmee is het niet universeel bruikbaar als benadering.

[ Voor 24% gewijzigd door Confusion op 26-09-2005 22:51 ]

[MrBucket]

Nogmaals, als het algoritme in O(n) loopt, dan moet het volgens mij ook mogelijk zijn om een dataset te construeren waarbij het algoritme een willekeurig slecht resultaat geeft (dat wil zeggen, een puntenpaar waarvan de afstand een fractie van de maximum afstand is).

Maar zonder algoritme wordt het lastig om hierover concrete uitspraken te doen, ben ik bang.

[Tomatoman]

MrBucket schreef op maandag 26 september 2005 @ 23:05:
Nogmaals, als het algoritme in O(n) loopt, dan moet het volgens mij ook mogelijk zijn om een dataset te construeren waarbij het algoritme een willekeurig slecht resultaat geeft (dat wil zeggen, een puntenpaar waarvan de afstand een fractie van de maximum afstand is).

Maar zonder algoritme wordt het lastig om hierover concrete uitspraken te doen, ben ik bang.

Dat is precies waar ik op doelde, zonder algoritme valt er niets zinnigs over te zeggen. Ik begrijp de topicstarters overweging wel om zijn algoritme geheim te houden, maar het maakt deze discussie tot een sinterklaasavond zonder surprises om uit te pakken.

.oisyn schreef op maandag 26 september 2005 @ 13:20:
Heb je de topic wel helemaal gelezen?

offtopic:
Moet ik die vraag na 700+ posts in P&W serieus nemen?

[ Voor 13% gewijzigd door Tomatoman op 27-09-2005 00:27 ]

[MBV]

Ik ben heel benieuwd naar het algoritme, en hoe fout het is. Het lijkt mij dat een O(N) benadering al heel leuk zou zijn.
@TS: je hebt nu een theoretische kans dat .iosyn hier een patent op vraagt, voordat jij een publicatie hebt gedaan. Als je dat algoritme hier had gepost was daarvoor Prior Art aangetoond. Dat iedereen schijnt te denken dat alle gegevens en foto's enz die je met internet kan vinden gratis is, betekent nog niet automatisch dat het ook zo is. Als ik mijn foto's ergens anders tegen kom mag ik de desbetreffende site/persoon/bedrijf er op aanspreken en een vergoeding eisen. _{Mag ook een vermelding van mijn naam eisen omdat ik trots ben natuurlijk}

edit:
Ja Curry, via een omweg bedoelde ik dat ook. Eigenlijk snap ik de TS ook wel, omdat iedereen denkt dat alles op internet gratis is. Maar wettelijk gezien heb je na publicatie gewoon het copyright

[ Voor 16% gewijzigd door MBV op 27-09-2005 12:34 . Reden: theoretisch +edit-verhaaltje toegevoegd ]

[curry684]

MBV schreef op maandag 26 september 2005 @ 23:57:
@TS: je hebt nu kans dat .iosyn hier een patent op vraagt, voordat jij een publicatie hebt gedaan. Als je dat algoritme hier had gepost was daarvoor Prior Art aangetoond.

Academisch natuurlijk gezien het feit dat oisyn hier posts kan trashen en goede vriendjes is met de mensen die ze permanent uit database en backups kunnen verwijderen. Er is ook nog zoiets als vertrouwen

Het topic is op dit moment redelijk nutteloos, maar ik ga er vooralsnog nog even gevoeglijk van uit dat TS het algoritme deelt zodra hij tevreden is met de uitleg waarom deze niet functioneert

[Verwijderd]

MBV schreef op maandag 26 september 2005 @ 23:57:
Ik ben heel benieuwd naar het algoritme, en hoe fout het is. Het lijkt mij dat een O(N) benadering al heel leuk zou zijn.

Ik vermoed dat het niet een benadering is, maar een heuristiek. Het verschil is belangrijk: bij een benadering weet je hoe ver van het optimum je maximaal af zit. Een heuristiek is meer 'werkt snel en redelijk goed, maar kan er compleet naast zitten'. Aangezien er al O(N log N) algoritmes zijn om de optimale oplossing te berekenen, is het de vraag of een benadering of heuristiek in O(N) nuttig is.

[Zoijar]

Je kan ook nog bedenken welke moeilijke problemen je sneller op kan lossen als dit in O(n) zou kunnen. Als je bv sneller dan O(nlog n) kan sorteren, dan bestaat er dus geen O(n) oplossing.

[D4Skunk]

Ok, zo even uit de losse pols (niet echt over nagedacht)

Er bestaat een algoritme waarmee je een cirkel kunt mappen op 3 punten.
1. Neem 3 willekeurige punten uit je verzameling, en map de cirkel daar op.
2. Neem het volgende punt, en kijk of dit punt buiten of binnen de cirkel valt. Als het buiten de cirkel valt, bereken je de cirkel waarmee je zeker bent dat alle punten op of in deze cirkel liggen (=de grootste dus)
3. ga naar 2

Wanneer je alle punten overlopen hebt, ben je zeker dat je een cirkel hebt die om alle punten heengaat. Logischerwijze moeten dan ook de verst uit elkaar liggende punten hierin liggen, en voila, je bent er....

FF nagedacht... Damn, niet echt... als de drie laatste punten een gelijkbenige driehoek vormen, kan er nog steeds een lijn zijn iets kleiner dan de diameter, die bv vanaf de top dwars door het midden loopt, en iets langer dan een zijde... damnit....

Better luck next time

[Janoz]

@D4Skunk:

En toen lagen je eerste drie punten op 1 lijn....


Ik heb echter wel het vermoeden dat het een hierop lijkend algoritme is. Gewoon proberen een omsluitende elipse te vinden om de dataset, en hiervan vervolgens de grootste diameter nemen.

[ Voor 63% gewijzigd door Janoz op 27-09-2005 10:59 ]

[.oisyn]

tomatoman schreef op maandag 26 september 2005 @ 23:41:

offtopic:
Moet ik die vraag na 700+ posts in P&W serieus nemen?

Met mijn 7000+ posts in P&W wil ik ook nog wel eens een post vergeten hoor, het was dus meer een oprechte vraag en geen verwijt

MrBucket schreef op maandag 26 september 2005 @ 23:05:
Nogmaals, als het algoritme in O(n) loopt, dan moet het volgens mij ook mogelijk zijn om een dataset te construeren waarbij het algoritme een willekeurig slecht resultaat geeft (dat wil zeggen, een puntenpaar waarvan de afstand een fractie van de maximum afstand is).

Is niet zo . Hij stopt de punten in x groepen, en gaat vervolgens die x groepen in O(x²) controleren. Omdat x altijd constant is werkt dat in O(1), de O(n) komt dan uiteindelijk van het indelen van elk punt in een groep.

Maar ik ben het er mee eens dat de topic momenteel een beetje nutteloos is. HIGHGuY, ik zal je vanmiddag even een bewijs mailen (gisteren niet aan toegekomen), maar je moet je wel realiseren dat je algoritme allesbehalve the best thing since sliced bread is . Het is zelfs heel erg flauw, je werkt een O(n²) weg door die n punten te mappen op x andere punten en daar dan vervolgens een brute force op te doen. Ik zou voor je thesis ook iets meer moeite doen door een O(n log n) algo te zoeken.

[ Voor 22% gewijzigd door .oisyn op 27-09-2005 11:38 ]

[H!GHGuY]

voor mijn gebruik is dit algo ideaal. gezien de nauwkeurigheid van mijn algo boven die van het meettoestel ligt.

Ik weet echter nog steeds niet die fout die jij bedoelt. Voor zover ik weet is de fout die ik beschrijf de enige. En daarvoor had ik een oplossing met slechts 1 worst-case singuliere oplossing die O(n²) doet.

Voor diegenen die het over sorteren hebben, gebruik ik eigenlijk een soort van bucket sort.
in O(1) ga ik dus elk punt sorteren.

Het is zelfs heel erg flauw, je werkt een O(n2) weg door die n punten te mappen op x andere punten en daar dan vervolgens een brute force op te doen. Ik zou voor je thesis ook iets meer moeite doen door een O(n log n) algo te zoeken.

je hebt het hiermee op die laatste brute force ? dat kan ook nog altijd... maar dan doe ik enkel een constante omlaag, en kan ik dus de precisie verhogen zonder verlies van snelheid.

wat de simpelheid van het algo betreft: KISS
daarenboven heb ik dit in een half dagje uitgewerkt. ik heb sindsdien (wegens familiale omstandigheden) nog niet meer tijd gehad dan af en toe hier een reply'tje te plaatsen. Een uitgebreidere wiskundige onderbouwing, dan wat logisch in het hoofd rederen met schetsjes op een noteblock moet ik nog maken. Die onderbouwing was ook het doel van m'n topic niet, voor de critici onder ons. Ik wou enkel meer info over het onderwerp.

[ Voor 22% gewijzigd door H!GHGuY op 27-09-2005 12:38 ]

[.oisyn]

Je algoritme is feitelijk O(n + p²), waarbij p je precisie is. Maar nee, wat je zegt klopt niet, ik kan aantonen dat het niet per se de op één na grootste lengte is (als je die 2 andere punten die een langere afstand van elkaar hebben 10x dupliceert en ze over een heel erg kleine afstand verplaatst heb je al meteen de op 10 na grootste lengte). Daarnaast vraag ik me af hoe je daarvoor gaat compenseren, het kan zelfs zo zijn dat de punten van de daadwerkelijk grootste afstand niet eens in dezelfde bin zitten als de twee bins die je gevonden hebt.

daarenboven heb ik dit in een half dagje uitgewerkt

Beetje naïef om dan te denken dat je iets revolutionairs hebt verzonnen waar je vervolgens heel erg beschermend over bent . Ik zou zeggen: post je algo hier gewoon, dan kan iedereen z'n zegje erover doen en je tips geven, en dan heeft deze topic ook nog enig nut

[ Voor 24% gewijzigd door .oisyn op 27-09-2005 12:46 ]

[Janoz]

Bucketsort is geen O(1) maar O(N).

[TD-er]

Janoz schreef op dinsdag 27 september 2005 @ 12:49:
Bucketsort is geen O(1) maar O(N).

Maar per punt is 'ie natuurlijk wel O(1) en daar had 'ie het over.

[Cuball]

offtopic:
Ik vind het topic persoonlijk enorm irritant aan het worden, telkens ik hier kom lezen nog steeds geen algoritme... post gewoon je algoritme ipv erover te zeveren. Wees gerust, als je het op een half dagje in elkaar gestampt hebt dan zal het wel niet zo revolutionair zijn als je denkt... je schrijft erover alsof je HET gevonden hebt, maar in feite geloof ik veeleer .oisyn dan jou verhaal.

Post het gewoon of laat het topic sluiten.

[H!GHGuY]

@oisyn, met die meerdere punten heb ik wel rekening gehouden, maar dat stond nog niet in m'n mail naar jou. en dan kom ik in het slechtste geval aan O(n²) zoals ik al steeds zeg, maar blijft het gemiddeld O(n).

ik zal het algo posten als ik mailtje gekregen heb van oisyn, tenzij dit de fout was die hij voor ogen had.
edit: bovendien was het enkel mijn bedoeling om info over andere algo's te vinden. niet om m'n algo te posten of om over de implementatie van mijn algo te gaan. Dat was ook meteen gezegd, dus eigenlijk vind ik alle commentaren "geef nou toch je algo" een beetje overdreven en misplaatst. Nieuwsgierigheid is menselijk, maar ook diefstal is dat.

edit2:
Ik bedenk net: alles wat ik tijdens mijn stage en thesis bedenk is eigenlijk eigendom van het bedrijf. Dus ik zal dit eigenlijk moeten bespreken met mijn stagebegeleider van het bedrijf. Ik zou in gebreke gesteld kunnen worden wanneer ik dit zonder overleg meteen openbaar.

[ Voor 56% gewijzigd door H!GHGuY op 27-09-2005 13:41 ]

[MBV]

HIGHGuY schreef op dinsdag 27 september 2005 @ 13:32:
[...]
Nieuwsgierigheid is menselijk, maar ook diefstal is dat.

Tja, vind ik een beetje overdreven. Mijn mening, ik ben voorstander van GPL enz

edit2:
Ik bedenk net: alles wat ik tijdens mijn stage en thesis bedenk is eigenlijk eigendom van het bedrijf. Dus ik zal dit eigenlijk moeten bespreken met mijn stagebegeleider van het bedrijf. Ik zou in gebreke gesteld kunnen worden wanneer ik dit zonder overleg meteen openbaar.

Daar heb je een punt. Veel (kleine) bedrijven zijn daar nogal paranoia over. Op mijn stageverslag moest een NDA omdat er een ERD van de database in zat (die ze niet gaan verkopen) Echt té triest was dat, zeker omdat dat tegen afspraken in ging...

[.oisyn]

HIGHGuY schreef op dinsdag 27 september 2005 @ 13:32:
@oisyn, met die meerdere punten heb ik wel rekening gehouden, maar dat stond nog niet in m'n mail naar jou. en dan kom ik in het slechtste geval aan O(n²) zoals ik al steeds zeg, maar blijft het gemiddeld O(n).

Hoe kom je aan gemiddeld O(n) als de best-case O(n) is en de worst-case niet? Dat is gemiddeld langzamer dan O(n) . Maar we hebben het idd over dezelfde fouten dus het mailtje heeft niet zoveel nut meer. Deze topic ook niet overigens, totdat je de code hier wilt/mag posten, dus tot die tijd gooi ik 'm op slot. Je weet me te vinden als je besluit toch je code te posten

.edit: deze topic heeft inmiddels een staartje: [rml][ Alg] Grootste afstand tussen 2 punten[/rml]

[ Voor 17% gewijzigd door .oisyn op 11-10-2005 21:54 ]