Optimale Suchstrategie für spezielle Integerfunktion



  • Hallo liebe Foristen,

    ich arbeite an einem Problem, wo umformuliert folgende Frage auftritt:
    Gegeben eine Funktion f mit
    [latex] f(i_1, i_2, ..., i_5) \in {0, 1}, i_1, i_2, \dots , i_5 \in {1, 2, \dots, N} [/latex] und [latex] i_1 \geq i_2 \geq \dots \geq i_5 [/latex]. N kann als 8 angenommen werden (könnte prinzipiell aber auch etwas größer oder kleiner sein (aber ist immer eine natürliche Zahl)).

    Sei nun der Index idx definiert als
    [latex] idx \coloneqq i_1*(N+1)^4 + i_2 *(N+1)^3 + i_3 * (N+1)^2 + \dots + i_5 [/latex].

    Es ist bekannt, dass f für große Werte von idx 1 und für kleine 0 ist und es nur einen Sprung von 1 zu 0 gibt, also aus f(idx) = 0 => f(idx-1) = 0 und f(idx) = 1 -> f(idx + 1) = 1 folgt. (d.h. ist z.B. f(6, 6, 5, 5, 4) = 0, dann auch für alle kleineren Indizes also z.B. auch für f(6, 5, 4, 4, 4) = 0)

    Wie finde ich mit den wenigsten Schritten den höchsten Index idx für den gerade f noch 0 ist?

    Das ganze stammt aus einer Versuchsanordnung wo das Auswerten der Funktion f sehr teuer ist, d.h. man möchte möglichst wenig Iterationen durchführen.

    Hat da jemand eine Idee?



  • @Namenloser324
    Naiver Weg:

    • Ermittle alle erlaubten Eingabewertkombinationen
    • Berechne die idx-Funktion und sortiere nach dem idx-Wert
    • Führe eine binäre Suche durch