killing the hydra

08.10.2018, 08:35

Dopap

killing the hydra

eigentlich geht es um gestutzte und speziell nachwachsende grafische Bäume. Der Kampf gegen eine Hydra klingt aber griffiger. Damit es ohne Zeichnungen mit der Erklärung besser klappt verwende ich die Generationen-Begriffe Rumpf, Opa-, Vater-, Sohn-Kopf und vielleicht noch Enkel-Kopf.
R-O-V-S symbolisiert eine Hydra mit Rumpf und dann ein Hals mit Opa-Kopf, darauf einen Hals mit Vater-Kopf und und darauf einen Hals mit Sohn-Kopf.

Regel 1: man darf nur einen Kopf ohne Fortsätze schneiden (Endknoten).
Beispiel: Aus R-O-V-S entsteht nach dem einzig möglichen Schnitt R-O-V. Leider tritt dann

Regel 2 in Kraft: vom ehemals abgeschnittenen Kopf (S) geht es pfadmässig 2 Generationen rückwärts - hier zu R-O. Auf diesem Opa-Kopf wächst nun genau der Teilbaum doppelt nach, von dem gerade ein Kopf entfernt wurde. d.h. der Opa-kopf trägt nun mindestens 3 identische Strukturen (Teilbäume ) . Die Hydra hat jetzt die Pfade

1. R-O-V ( nachgewachsen )
2. R-O-V ( nachgewachsen )
3. R-O-V ( alt )
Schnitt II: jetzt wird zwangsläufig irgendein V entfernt, es entsteht die Hydra mit den Pfaden

R-O ( nachgewachsen )
R-O (nachgewachsen )
R-O ( alt )
R-O-V (alt )
R-O-V (alt )
zu deutsch: der Rumpf hat 5 Hälse mit 5 Köpfen und 2 davon tragen einen Hals mit Kopf.
Schnitt III: Einmal der Schnitt von a.) einem O oder b.) der Schnitt von einem V.

a.) es entsteht die Hydra
R-O
R-O
R-O-V
R-O-V oder

b.) die Hydra
R-O
R-O
R-O
R-O
R-O
R-O
R-O-V
nach weiteren 10 Schnitten ist die Hydra kopflos.
Nimmt man z.B. eine Hydra mit 18 Köpfen und 13 Pfaden wächst diese beim Schneiden im Umfang unglaublich an.

Frage: kann jede Hydra mit endlich vielen Schnitten besiegt werden?

Meine Ideen: ja, das geht mit der Begründung, dass die Hydra zwar im Umfang stark wächst nicht aber deren Komplexität, unter anderem deshalb, weil die maximale Pfadlänge durch Anfangsbedingung und Regel2 begrenzt ist. Jeder Schnitt vermindert dagegen die Komplexität und irgendwann ist K=0 erreicht.
Ich kann das aber nicht formal hinschreiben und begründen.

08.10.2018, 11:54

HAL 9000

Auf diesen Beitrag antworten »

Man betrachte folgende Zustandsfunktion der Hydra: $\begin{eqnarray*} N(O,V,S) = O + 3V + 9S \end{eqnarray*}$ , hierbei geben O,V,S die jeweiligen Kopfanzahlen an.

Dann kann man leicht zeigen, dass die Entfernung eines beliebigen Kopfes - sei es O,V oder S - den Zustandswert der Hydra um genau 1 vermindert. Also gibt $\begin{eqnarray*} N \end{eqnarray*}$ genau die Anzahl der möglichen Schnitte an - fertig. Augenzwinkern

Wie sich die Formel für Enkel, Urenkel usw. dann erweitern lässt, ist wohl offenkundig.

08.10.2018, 15:25

Dopap

Auf diesen Beitrag antworten »

warum kompliziert wenn's auch einfach geht. Freude

Sapperlot, eine geile Funktion dieses N da! Augenzwinkern

Irgendso'was schwebte mir mit K vor

08.10.2018, 15:37

HAL 9000

Auf diesen Beitrag antworten »

Eine nette andere Problemstellung, wo auch eine solche Zustandsfunktion zum Erfolg führt, die Zustandsfunktion an sich aber nicht so einfach zu finden ist:

Zitat:

Man betrachte ein regelmäßiges Fünfeck, an dessen 5 Ecken ganze Zahlen stehen, deren Summe positiv ist. Findet man eine Ecke, an der eine negative Zahl $\begin{eqnarray*} y \end{eqnarray*}$ steht, so werden diese Zahl sowie deren beiden Nachbarn $\begin{eqnarray*} x \end{eqnarray*}$ und $\begin{eqnarray*} z \end{eqnarray*}$ in einem Rutsch folgendermaßen geändert:

$\begin{eqnarray*} x\to x+y,\; z\to z+y,\; y\to -y \end{eqnarray*}$

Man überprüfe, ob eine solche Operation nur endlich oft durchgeführt werden kann. Falls ja, gebe man eine obere Abschätzung für die Maximalschrittzahl an, basierend auf der Anfangsformation.

08.10.2018, 18:32

Dopap

Auf diesen Beitrag antworten »

eine eher rhetorische Frage , denn ich bin geistig zur Zeit noch mit dem Schneiden von Tulpenköpfen beschäftigt...
Aber ich kenn' da jemand mit dem Namen eines berühmten Filmcomputers ... ;-)

08.10.2018, 21:55

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
Aber ich kenn' da jemand mit dem Namen eines berühmten Filmcomputers ... ;-)

Vielleicht Deep Thought ? Aber den Nutzer gibt es hier im Board ja noch gar nicht. Augenzwinkern

15.10.2018, 16:41

HAL 9000

Auf diesen Beitrag antworten »

Ok, des (nachgeschobenen) Rätsels Lösung: Man betrachtet - inspiriert durch ein eingezeichnetes Pentagramm ( Teufel

) - die Zustandsfunktion

$\begin{eqnarray*} S(a,b,c,d,e) := (a-c)^2 + (b-d)^2 + (c-e)^2 + (d-a)^2 + (e-b)^2 \end{eqnarray*}$ ,

also die Differenzen entlang der Pentagrammkanten quadriert und dann summiert.

Haben wir dann z.B. $\begin{eqnarray*} b<0 \end{eqnarray*}$ und wandeln entsprechend der obigen Regel die Werte um zu $\begin{eqnarray*} a'=a+b,b'=-b,c'=c+b,d'=d,e'=e \end{eqnarray*}$ , dann folgt mit ein klein wenig Rechnerei

$\begin{eqnarray*} S(a',b',c',d',e') - S(a,b,c,d,e) = 2b(a+b+c+d+e) = -2|b|s \leq -2s\qquad (*) \end{eqnarray*}$

mit $\begin{eqnarray*} s:=a+b+c+d+e \end{eqnarray*}$ . Wir halten außerdem fest, dass sich wegen $\begin{eqnarray*} a'+b'+c'+d'+e'=a+b+c+d+e \end{eqnarray*}$ die Summe $\begin{eqnarray*} s \end{eqnarray*}$ der fünf Werte bei einem solchen Schritt nicht ändert.

Nach $\begin{eqnarray*} n \end{eqnarray*}$ Schritten hat man daher einen Zustandswert $\begin{eqnarray*} S(a_n,b_n,c_n,d_n,e_n) \leq S(a_0,b_0,c_0,d_0,e_0)-2ns \end{eqnarray*}$ , andererseits ist aber konstruktionsbedingt $\begin{eqnarray*} S(a_n,b_n,c_n,d_n,e_n)\geq 0 \end{eqnarray*}$ . Daraus folgt $\begin{eqnarray*} n \leq \frac{1}{2s} S(a_0,b_0,c_0,d_0,e_0) \end{eqnarray*}$ , d.h., es gehen nur endlich viele Schritte, die Ungleichung eben liefert eine aus der Anfangskonfiguration direkt berechenbare obere Schranke für die maximale Schrittanzahl.

Beispiel: $\begin{eqnarray*} a=b=c=d=1,e=-3 \end{eqnarray*}$ liefert $\begin{eqnarray*} s=1 \end{eqnarray*}$ und $\begin{eqnarray*} S(a,b,c,d,e)=32 \end{eqnarray*}$ , damit ist $\begin{eqnarray*} \frac{32}{2}=16 \end{eqnarray*}$ eine obere Schranke für die Anzahl Umformungsschritte. Tatsächlich sind es echt weniger, da Gleichheit in (*) nur im Fall $\begin{eqnarray*} b=-1 \end{eqnarray*}$ gilt, was etwa gleich im ersten Schritt unmöglich erfüllt ist.

Neue Frage »

Antworten »

killing the hydra

Verwandte Themen