bruteforce

Kylanysik

grüße an alle
ich sitze nun schon seit stunden und langsam ist es frustrierend.

ich habe vor, mittels bruteforce in einer liste zwei punkte zu suchen, die sich von allen punkten in der liste am nächsten liegen
und möchte diese beiden punkte dann ausgeben bzw. zurückgeben .

das grundprinzip des algorithmuses ist klar. jedoch an der umsetzung scheitert es. ich komm einfach nicht drauf, wie ich den schreiben soll.

wäre dankbar, wenn ich denkanregungen oder ähnliches bekommen könnte.
vielen dank
grüße kylanysik

hustbaer

bester_A_index = 0
bester_B_index = 1
bester_abstand = abstand(L[0], L[1])

für alle punkte in L als A
   für alle punkte in L als B
       abstand_a_b = abstand(A, B)
       wenn (abstand_a_b < bester_abstand)
           bester_A_index = index von A
           bester_B_index = index von B
           bester_abstand = abstand_a_b

huh?

Kylanysik

vielen dank schonmal für deine schnelle antwort
ich werd es morgen mal probieren und hoffe doch mal, dass alles funzt

Danke

volkard

Kylanysik schrieb:

vielen dank schonmal für deine so schnelle antwort

würde es dir was ausmachen mir nur kurz zu erklären wie
"punkte in L als A" genau zu verstehen ist?

Danke

angenokmen vector<Punkt> L isses

for(vector<Punkt>::iterator iL=A.begin();iL!=A.end();++iL)
{
   Punkt& L=*iL;
   //hier das innere der schleife
}

die konkrete implementierung hängt sehr von den punktlisten ab. hustbaer ist ein ganz lieber und hätte dir den code fertig gemacht, wenn die typen ihm bekannt wären. so hat er pseudocode gebaut, der ganz ganz allgemein ist.
möglicherweise vielleicht wollte er auch noch ein wenig eigenleistung von dir nachgewiesen bekommen, um abzusichern, daß du nicht nur mit "jedoch an der umsetzung scheitert es" ihm eine lösung rauslockst, die eigentlich deine hausaufgabe ist, möglicherweise vielleicht wollte er dir die lösung geben, in der annahme, daß du dich in deinem algo verhospert hast und dich klar schiff bringen, weil er mit deinen angaben unmöglich mehr tun kann.

oder was ganz anderes. keine ahnung.

hustbaer

L = die Liste
"für alle Punkte in L als A"
heisst quasi
Wiederhole das folgende für jeden Punkt der in L gespeichert ist, und den Punkt nennst du dabei A.

In pseudo-C++:

//für alle punkte in L als A
for (int index_von_A = 0; index_von_A < Liste.size(); index_von_A++)
{
    Punkt A = Liste[index_von_A];
    // für alle punkte in L als B
    for (int index_von_B = 0; index_von_B < Liste.size(); index_von_B++)
    {
        if (index_von_A != index_von_B) // *
        {
            Punkt B = Liste[index_von_B];

            // ...
        }
    }
}

Natürlich hab ich nochwas vergessen: du musst die Fälle A == B ausnehmen, also du solltest nicht einen Punkt gegen sich selbst testen, logisch irgendwie (oben mit // * gekennzeichnet).

hustbaer

volkard schrieb:

angenokmen vector<Punkt> L isses

for(vector<Punkt>::iterator iL=A.begin();iL!=A.end();++iL)
{
   Punkt& L=*iL;
   //hier das innere der schleife
}

Du hast im Code L und A vertauscht

Wenn L die Liste ist und A der Punkt, dann muss das natürlich so heissen:

for(vector<Punkt>::iterator iL=L.begin();iL!=L.end();++iL)
{
   Punkt const& A=*iL;
   //hier das innere der schleife
}

Der Abstand zwischen Punkt A und Punkt B ist genauso groß wie der zwischen Punkt B und Punkt A. Der muß nicht zweimal "gemessen" werden.

volkard

hustbaer schrieb:

Du hast im Code L und A vertauscht

MIST.
und dein darauf folgender code ist eh viel hübscher.

hustbaer

@volkard: hübscher vielleich nicht, aber vermutlich einfacher (bzw. man muss erstmal nicht wissen was iteratoren oder referenzen sind)

@schlechtmacher: das ist richtig. andrerseits war brute-force gefragt