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