Ist das Verfahren allgemeingültig?

ShredderButtonOn

Moin, kurze Frage an unsere Algorithmiker.

Folgendes Problem kann mit folgendem Verfahren gelöst werden:

import java.util.*;

public class Dyn {
    public static void main(String[] args) {
        customBreadthFirstSearch();
    }

    public static void customBreadthFirstSearch() {
        int n = 5;
        Deque<int[]> solutions = new ArrayDeque<>();
        int[] first = new int[n];
        //Arrays.fill(first, 11);
        solutions.addLast(first);
        int[] best = checkSolution(first);
        while (!solutions.isEmpty()) {
            int[] solution1 = solutions.removeFirst();
            int[] check = checkSolution(solution1);
            System.out.println(Arrays.toString(solution1) + " " + Arrays.toString(check) + " (was " + Arrays.toString(best) + ")");
            if (containsOnlyZero(check)) {
                System.out.printf("     %d      %n", 86);
                System.out.printf("    %d %d    %n", 47, 39);
                System.out.printf("  %d %d %d   %n", solution1[0], solution1[1], solution1[2]);
                System.out.printf(" %d %d %d %d %n", 12, solution1[3], solution1[4], 5);
                System.out.println("numberOfCheckCalls = " + numberOfCheckCalls);
                return;
            }
            if (Arrays.compare(check, best) > 0) {
                continue;
            }
            if (Arrays.compare(check, best) < 0) {
                best = check;
            }
            int[] solution2 = new int[n];
            System.arraycopy(solution1, 0, solution2, 0, n);
            for (int i = 0; i < n; i++) {
                solution2[i]++;
                int[] solution3 = new int[n];
                System.arraycopy(solution2, 0, solution3, 0, n);
                solutions.addLast(solution3);
            }
        }
    }

    private static int numberOfCheckCalls = 0;

    private static int[] checkSolution(int[] a) {
        numberOfCheckCalls++;
        int[] b = {
                86,
                47, 39,
                a[0], a[1], a[2],
                12, a[3], a[4], 5
        };
        int[] result = {
                b[3] + b[4] - b[1],
                b[4] + b[5] - b[2],
                b[6] + b[7] - b[3],
                b[7] + b[8] - b[4],
                b[8] + b[9] - b[5],
        };
        for (int i = 0; i < result.length; i++) {
            result[i] = Math.abs(result[i]);
        }
        return result;
    }

    private static boolean containsOnlyZero(int[] a) {
        for (int i : a) {
            if (i != 0) {
                return false;
            }
        }
        return true;
    }
}

Nun frage ich mich, ob das Verfahren allgemeingültig ist, also für alle Probleme, die auch eine Lösung haben, eine Lösung finden würde. Meine Vermutung geht eher Richtung Nein.

Eigentlich müsste man doch "nur" 12 und 5 durch etwas anderes austauschen, womit das Verfahren keine Lösung findet, oder irre ich?

DNKpp

Vorweg, ich werde jetzt nicht auf deinen Code im Speziellen eingehen.

Es geht scheinbar um eine Pyramide mit konstant 4 Ebenen, bei denen immer genau diese Parameter bekannt sind. Intuitiv würde ich behaupten, dass ist eine Variante des Pascalschen Dreickes.
Für deine konkrete Aufgabenstellung gilt also ausgeschrieben:

b = d + e
c = e + f

d = g + h
e = h + i
f = i + j

Mit ein wenig Substituieren kommen wir also zu

b = g + h + h + i = g + 2h + i
c = h + i + i + j = h + 2i + j

Da b, c, g und j bekannt sind, gilt es jetzt also nur noch passende Parameter für h und i zu finden.
Bringen wir also alles Konstanten auf die eine und alle Parameter auf die andere Seite:

2h + i = b - g
h + 2i = c - j

Mit Z1 - 2*Z2 (mit anschließendem Zeilentausch) folgt dann entsprechend:

h + 2i = c - j
0h - 3i = b - g - 2(c - j) <=> 3i = g - b + 2(c -j)

Also:

i = (g - b + 2(c -j)) / 3
h = c - j - 2i

Die Frage, die nun also zu klären wäre: Hält dein Verfahren strikt diese Bedingungen ein?

ShredderButtonOn

@DNKpp Danke. Ich probiere es nachher mal aus, bin gerade in der Mittagspause...

ShredderButtonOn

@DNKpp sagte in Ist das Verfahren allgemeingültig?:

Also:
i = (g - b + 2(c -j)) / 3
h = c - j - 2i

Danke, aber die Formeln sind nutzlos.

So ... für:

        int[] b = {
                160,
                55, 105,
                a[0], a[1], a[2],
                0, a[3], a[4], 10
        };

also

   160
  55 105
 5  50 55
0  5  45 10

funktioniert es nicht mehr. Auch nicht, wenn ich das continue auskommetiere -> dann läuft der Heap-Space voll.

Also ist das Verfahren nicht allgemeingültig (Beweis durch Gegenbeispiel). Mehr wollte ich gar nicht wissen.

oxide

Also die Quelle für diese Meisterleistung an Java Software kommt aus dem Computer Base Forum:

https://www.computerbase.de/forum/threads/bin-zu-doof-mathe-3-klasse.2212978/page-4#post-29969370

Da es sich dabei um einen bekannten Forentroll handelt, würde ich das „Programm“ nicht weiter betrachten.

Habe es auch nicht gelesen oder versucht zu verstehen was da passiert. Würde es ignorieren und meine Zeit in sinnvolle Aktivitäten packen wie eine Mittagspause.

Quiche Lorraine

@oxide
Danke für deinen Hinweis. Es bestätigt meine Vermutung.

Apropos, die Reinkarnationen scheinen auch wieder in Aktion zu sein:

https://www.c-plusplus.net/forum/topic/355138/private-nachrichten-verschicken

DNKpp

@oxide sagte in Ist das Verfahren allgemeingültig?:

Also die Quelle für diese Meisterleistung an Java Software kommt aus dem Computer Base Forum:

https://www.computerbase.de/forum/threads/bin-zu-doof-mathe-3-klasse.2212978/page-4#post-29969370

Da es sich dabei um einen bekannten Forentroll handelt, würde ich das „Programm“ nicht weiter betrachten.

Habe es auch nicht gelesen oder versucht zu verstehen was da passiert. Würde es ignorieren und meine Zeit in sinnvolle Aktivitäten packen wie eine Mittagspause.

Verstehe ich das richtig? @ShredderButtonOn ist besagter Troll?

Quiche Lorraine

@DNKpp
https://www.c-plusplus.net/forum/topic/355123/hallo-und-wer-ich-bin/10

ShredderButtonOn

Ich fände es gut, wenn ihr dieses Thema nicht durch Off-topic zweckentfremden würdet.

ShredderButtonOn

@oxide sagte in Ist das Verfahren allgemeingültig?:

Würde es ignorieren und meine Zeit in sinnvolle Aktivitäten packen wie eine Mittagspause.

Das ist schön und gut. Ich war aber ehrlich und habe gesagt, dass ich eine lange Mittagspause gemacht habe. Andere sind da nicht so ehrlich, und verschweigen dies oder schwurbeln halt herum. Mir sind aufrichtige Menschen immer lieber, als solche, die das nur vorgeben. Darin unterscheiden wir uns auch, ich kann mir Blabla nicht erlauben.