Überdeckung von Fehlstellen

29.01.2025, 00:57

Dopap

Überdeckung von Fehlstellen

~~|||||||| |||||| |||||||||||||||| || ||| |||||||||||||~~||||||||||||||

*Am ersten Tag als Zimmermann war mein Auftrag mittels einer
Menge $\begin{eqnarray*} Q=\{q_1, q_2, \cdots ,q_n\} \end{eqnarray*}$ von Holzleisten, in Brusthöhe,
quer als Strang verbunden, einen maroden Lattenzaun zu stabilisieren.
Die einzelnen Längen sind durch den konstanten Lattenabstand des Zaunes definiert.
Nun hat der Zaun aber leider eine Menge $\begin{eqnarray*} P=\{p_1,p_2, \cdots ,p_{n-1}\} \end{eqnarray*}$ von Positionen mit fehlender Latte.
Nach Überprüfung, dass an der Position $\begin{eqnarray*} \sum Q \end{eqnarray*}$ keine Lücke bestand, konnte zur Tat
geschritten werden.
Die Bedingung der Stabilität verbietet den Stoß zweier Leisten auf einer Lücke
oder: jede störende Lücke muss überbrückt werden! Am nächsten Tag sollte es dann weitergehen.
Schnell war ein Permutation-Tupel oder Anordnung $\begin{eqnarray*} (q_1,\cdots ,q_n) \end{eqnarray*}$ gefunden, das den
Erfordernissen genügte.

Beispiel: Q={2,5,3,7,10} sum Q = 27 P={3,5,6,30} $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ (2,5,10,3,7 ) als Anordnung der Leisten.
( Die Stösse liegen somit bei S={2, 7, 17, 20, 27})

nicht schwer zu finden, funktioniert anscheinend immer.

wie könnte ein effizienter Algorithmus dafür aussehen? Jedenfalls nicht Einer, der lediglich
alle Permutationen abklappert.
Wie könnte man die Vermutung beweisen?

(*) verständlich formuliert:
Sei $\begin{eqnarray*} n \in \mathbb N^* \end{eqnarray*}$ sowie $\begin{eqnarray*} Q,P\subset \mathbb N^* \end{eqnarray*}$ mit $\begin{eqnarray*} |Q| = |P| +1 = n \end{eqnarray*}$ und $\begin{eqnarray*} \sum \! Q \notin P \end{eqnarray*}$ . Zu zeigen:
$\begin{eqnarray*} \bigvee_{ (q_1,q_2,\cdots,q_n)} \quad \bigwedge_{k \in \{1,\cdots ,n\}}\quad \sum_{i=1}^k q_i\notin P \end{eqnarray*}$
----------------------
vollständige Induktion über n?. Sonderfälle wie $\begin{eqnarray*} \max P > \sum Q \end{eqnarray*}$ etc. sind zu berücksichtigen.
Zu kompliziert, nicht mein Ding

29.01.2025, 08:10

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
funktioniert anscheinend immer.

Nun, damit wäre ich vorsichtig. Du hast vermutlich einige Parameterfälle gedanklich sofort ausgeschlossen, weil sie "praktisch" nicht vorkommen, aber so funktioniert natürlich die mathematische Formulierung der Voraussetzung nicht:

Beispielsweise klappt es nicht, wenn es $\begin{eqnarray*} u \end{eqnarray*}$ ununterbrochen hintereinander liegende Lücken gibt, die längste Leiste aber $\begin{eqnarray*} \leq u \end{eqnarray*}$ ist.

Wenn man sowas nicht irgendwie in den Voraussetzungen ausschließt, kann ein Beweis logischerweise ja gar nicht gelingen...

Außerdem habe ich noch einige Verständnisfragen:

1) Bei dir ist die Leistenanzahl um genau eins größer als die Lückenzahl - warum? Scheint mir unnötig einschränkend zu sein.

2) Dein Beispiel irritiert mich: So wie ich es verstehe, wird die letzte Lücke bei 30 von deinem Leistenstrang nicht überdeckt. Soll man das so verstehen, dass dein letzter Wert $\begin{eqnarray*} p_{n-1} \end{eqnarray*}$ keine Lücke, sondern das Zaunende kennzeichnet?

3) Der Leistenstrang in deinem Beispiel endet bei 27, also einige Positionen vor Ende des Zaunes. Ist es erlaubt, dass der Strang nicht bei 0, sondern vielleicht auch etwas "verschoben" anfängt? Falls nicht, hast du bei bestimmten Parameterkonstellationen ein Problem, z.B.

$\begin{eqnarray*} p_n = nd \end{eqnarray*}$ (also gleichabständige Lücken) und alle $\begin{eqnarray*} q_k \end{eqnarray*}$ nur Vielfache von $\begin{eqnarray*} d \end{eqnarray*}$ , dann klappt es nämlich nicht.

Es sei denn, auch sowas wird durch die Voraussetzungen (s.o.) ausgeschlossen.

All die Beispiele, die ich genannt habe, sind hinreichend dafür, dass es nicht klappt. Was man für einen ordentlichen Beweis hier benötigt sind aber eher hinreichende Bedingungen dafür, dass es klappt.

Zitat:

Original von Dopap
wie könnte ein effizienter Algorithmus dafür aussehen? Jedenfalls nicht Einer, der lediglich alle Permutationen abklappert.

Zum einen kann man ja aufhören, wenn eine passende Permutation gefunden wurde.

Zum anderen kann man ja in einem Branch-and-Bound-Verfahren die Permutationen nach und nach aufbauen und bereits abschneiden, wenn die Ausschlussbedingung "Leistennahtstelle = Zaunlücke" erkannt wird - derart angefangene Permutationen weiter zu betrachten wäre ja sinnlos.

30.01.2025, 04:55

Dopap

Auf diesen Beitrag antworten »

es ist nicht leicht für ein mathematisches Problem ein anschauliches Beispiel in der realen Welt zu
finden ohne damit ungewollt Einschränkungen oder Schwächen zu generieren.
Alles vorab wasserdicht zu machen, macht die Story lang und ermüdend. z. B. :

-Der Zaun ist länger wie der Grenzzaun zu Mexiko und ist/war ein Sichtschutzzaun
-die Menge an Latten für den ersten Tag enthällt nur verschieden lange Stücke
-entscheidend ist nur, dass am ersten Tag alle mitgebrachten Leisten als Strang korrekt angebracht wurden ...

Gültig ist natürlich nur (*)

Ein einziges Gegenbeispiel würde die Vermutung sofort zerstören.

Am Aufwendigsten, schwersten ist das Problem natürlich wenn alle $\begin{eqnarray*} p_i \end{eqnarray*}$
kleiner als $\begin{eqnarray*} \sum Q \end{eqnarray*}$ sind.
Q={1, 2, 3, 4, 7} und P={42, 0815, 4711, 666} hingegen überhaupt nicht, da jede
Permutations Anordnung von Q eine Lösung ist.
Wesentlich schwieriger wäre z. B.
Q={1,2,3, ... ,30} und P = {29 gleichverteilte Zufalls-Zahlen kleiner 500 aber ohne die 465}.
Das oder die Lösungstupel von Q kann wahrscheinlich nur ein [effektives(s.o)] Programm finden.

Eine andere "reale" Story hätt' ich noch, aber die darin vorkommenden Akteure
wie TESLA, AI gesteuerte Fahrzeugen und Sabotagen der Konkurrenz ist so glaubwürdig
wie .. wie ein Film mit Chuck Norris.

Ansonsten sollte doch jetzt alles klar sein oder? und von Zäunen möchte ich eigentlich vorerst verschont bleiben... Augenzwinkern

[attach]58085[/attach]

30.01.2025, 08:43

HAL 9000

Auf diesen Beitrag antworten »

Ok, ich hatte beim ersten Durchlesen nicht realisiert, dass deine Darstellung als Menge implizit bedeuten soll, dass die Leistenlängen paarweise verschieden sind - was bei großem $\begin{eqnarray*} n \end{eqnarray*}$ wohl reichlich praxisfern ist (hast mich da mit deinem "Am ersten Tag als Zimmermann" eingelullt). Das in Kombination mit der ebenso praxisfernen Bedingung $\begin{eqnarray*} |Q|=|P|+1 \end{eqnarray*}$ sichert natürlich, dass mein Gegenbeispiel

Zitat:

Original von HAL 9000
Beispielsweise klappt es nicht, wenn es $\begin{eqnarray*} u \end{eqnarray*}$ ununterbrochen hintereinander liegende Lücken gibt, die längste Leiste aber $\begin{eqnarray*} \leq u \end{eqnarray*}$ ist.

nicht den Voraussetzungen genügt.

Zitat:

Original von HAL 9000
Zum einen kann man ja aufhören, wenn eine passende Permutation gefunden wurde.

Zum anderen kann man ja in einem Branch-and-Bound-Verfahren die Permutationen nach und nach aufbauen und bereits abschneiden, wenn die Ausschlussbedingung "Leistennahtstelle = Zaunlücke" erkannt wird

Versuch das doch einfach mal auf dein Beispiel

Zitat:

Original von Dopap
Q={1,2,3, ... ,30} und P = {29 gleichverteilte Zufalls-Zahlen kleiner 500 aber ohne die 465}.

loszulassen. Die Permutationszahl $\begin{eqnarray*} 30! \approx 2.65\cdot 10^{32} \end{eqnarray*}$ muss einen dabei nicht schrecken, durch das Branch-and-Bound wird man nicht mal entfernt an diese Schleifenzahl herankommen müssen - solange dir eine Lösung genügt und du nicht alle haben willst.

Übrigens: Warum nicht gleich 29 Zufalls-Zahlen kleiner 465? Die Zahlen größer 465 vereinfachen doch nur das Suchproblem.

31.01.2025, 16:35

HAL 9000

Auf diesen Beitrag antworten »

Ok, hab das mal wie beschrieben implementiert. Leider fehlt mir ein Beispiel, welches den Algorithmus mal richtig stresst - bisher hatte ich nur Rechenzeiten <1ms (ohne Textausgabe), selbst bei $\begin{eqnarray*} |Q|=10000 \end{eqnarray*}$ ...

Neue Frage »

Antworten »

Überdeckung von Fehlstellen

Verwandte Themen