Informatik II - Übung 8

Pascal Schärli

knapsack@pascscha.ch

13.11.2020

Nachbesprechung

Bild: look again by corpus delicti from the Noun Project

Pascal Schärli 13.11.2020

Array-Listen und Generics

private boolean filter(Student student) {
    return student.getPoints() >= (IFilter.criteria / 100 * IFilter.maxNumberofPoints);
}

public ArrayList filterRaw(ArrayList groups) {
    ArrayList result = new ArrayList();
    for (int i = 0; i < groups.size(); i++) {
        ArrayList group = (ArrayList) groups.get(i);
        for (int j = 0; j < group.size(); j++) {
            Student student = (Student) group.get(j);
            if (filter(student)) {
                result.add(student);
            }
        }
    }
    return result;
}

public ArrayList<Student> filterGeneric(ArrayList<ArrayList<Student>> groups) {
    ArrayList<Student> result = new ArrayList<Student>();
    for (int i = 0; i < groups.size(); i++) {
        ArrayList<Student> group = groups.get(i);
        for (int j = 0; j < group.size(); j++) {
            Student student = group.get(j);
            if (filter(student)) {
                result.add(student);
            }
        }
    }
    return result;
}

Pascal Schärli 13.11.2020

Reversi Teil 1

  public Coordinates nextMove(GameBoard gb) {
    ArrayList<Coordinates> validMoves = new ArrayList<Coordinates>(gb.getSize() * gb.getSize());
    
    for (int row = 1; row <= gb.getSize(); row++) {
      for (int col = 1; col <= gb.getSize(); col++) {
        Coordinates coord = new Coordinates(row, col);
        if (gb.checkMove(color, coord)) {
          validMoves.add(coord);
        }
      }
    }
    
    if (validMoves.size() > 0) {
      int randIndex = rand.nextInt(validMoves.size());
      return validMoves.get(randIndex);
    }
    else {
      return null;
    }
  }

Pascal Schärli 13.11.2020

Vorlesung

Pascal Schärli 13.11.2020

Binäre Suche

Pascal Schärli 13.11.2020

Denkt an eine Zahl zwischen 0 und 1023

Binäre Suche

  • Gegeben wird ein sortierter Array [1,2,4,6,9,10,14,16,17,20,23,26]
     
  • Welcher Index hat 16?
    1. Alle Elemente durchprobieren.
      \(\rightarrow\) nicht sehr effizient
       
    2. Eventuell kann man ausnutzen, dass der Array bereits sortiert ist?
      \(\rightarrow\) Binäre Suche!

Pascal Schärli 13.11.2020

Binäre Suche

Binäre Suche:

Gesuchter Wert mit der Mitte/Pivot vergleichen.

Gleich wie die Mitte?
	-> Gefunden!

Grösser als die Mitte?
	-> rechts weitersuchen

Kleiner als die Mitte?
    -> links weitersuchen
26

1

2

4

6

9

10

14

16

17

20

23

11

0

1

2
3

4

5

6

7

8

9

10

pivot
10

Vergleich:

16
?

>

Pascal Schärli 13.11.2020

Binäre Suche

Binäre Suche:

Gesuchter Wert mit der Mitte/Pivot vergleichen.

Gleich wie die Mitte?
	-> Gefunden!

Grösser als die Mitte?
	-> rechts weitersuchen

Kleiner als die Mitte?
    -> links weitersuchen
26

1

2

4

6

9

10

14

16

17

20

23

11

0

1

2
3

4

5

6

7

8

9

10

pivot
17

Vergleich:

16
?

<

Pascal Schärli 13.11.2020

Binäre Suche

Binäre Suche:

Gesuchter Wert mit der Mitte/Pivot vergleichen.

Gleich wie die Mitte?
	-> Gefunden!

Grösser als die Mitte?
	-> rechts weitersuchen

Kleiner als die Mitte?
    -> links weitersuchen
26

1

2

4

6

9

10

14

16

17

20

23

11

0

1

2
3

4

5

6

7

8

9

10

pivot
14

Vergleich:

16
?

>

Pascal Schärli 13.11.2020

Binäre Suche

Binäre Suche:

Gesuchter Wert mit der Mitte/Pivot vergleichen.

Gleich wie die Mitte?
	-> Gefunden!

Grösser als die Mitte?
	-> rechts weitersuchen

Kleiner als die Mitte?
    -> links weitersuchen
26

1

2

4

6

9

10

14

16

17

20

23

11

0

1

2
3

4

5

6

7

8

9

10

pivot
16

Vergleich:

16
?

=

Pascal Schärli 13.11.2020

Backtracking

  • In Informatik I musstet ihr einen Sudoku-Solver Programmieren
     
  • Die einfachste Lösung wäre alle möglichen Zahlenkombinationen auszuprobieren.
    • Code ist kurz und überschaubar
    • Die Laufzeit ist dafür unmenschlich lange
       
  • Darum habt also nur Positionen geprüft, welche die Sudoku Regeln nicht verletzen.
    • Euer Programm wurde komplexer
    • Die Laufzeit war jedoch viel schneller.

Pascal Schärli 13.11.2020

Backtracking - Damen

  • Annahme: 10'000 Positionen/Sekunde,
    8x8 Spielbrett

     
  • Brute Force:
    • \(8^8 = \) 16'777'216 Pos.
    • \(\approx 28\) min
       
  • Backtracking:
    • 15'720 Pos.
    • \(\approx 1.5\) sek

Pascal Schärli 13.11.2020

Backtracking - Damen

Setze in jede Spalte eine Dame, so dass sich keine zwei Damen in einem Zug erreichen können:

current
Falls in der ersten unbesetzten Zeile Platz vorhanden ist
    -> setze möglichst weit unten

Falls kein Platz vorhanden ist
    -> Backtracking

Die Zeile vorher machte Backtracking
     Falls es oberhalb noch platz hat
         -> Dame nach oben verschieben
     Sonst
         -> Backtracking

Pascal Schärli 13.11.2020

Backtracking - Damen

current

Setze in jede Spalte eine Dame, so dass sich keine zwei Damen in einem Zug erreichen können:

Falls in der ersten unbesetzten Zeile Platz vorhanden ist
    -> setze möglichst weit unten

Falls kein Platz vorhanden ist
    -> Backtracking

Die Zeile vorher machte Backtracking
     Falls es oberhalb noch platz hat
         -> Dame nach oben verschieben
     Sonst
         -> Backtracking

Pascal Schärli 13.11.2020

Backtracking - Damen

current

Setze in jede Spalte eine Dame, so dass sich keine zwei Damen in einem Zug erreichen können:

Falls in der ersten unbesetzten Zeile Platz vorhanden ist
    -> setze möglichst weit unten

Falls kein Platz vorhanden ist
    -> Backtracking

Die Zeile vorher machte Backtracking
     Falls es oberhalb noch platz hat
         -> Dame nach oben verschieben
     Sonst
         -> Backtracking

Pascal Schärli 13.11.2020

Backtracking - Damen

current

Setze in jede Spalte eine Dame, so dass sich keine zwei Damen in einem Zug erreichen können:

Falls in der ersten unbesetzten Zeile Platz vorhanden ist
    -> setze möglichst weit unten

Falls kein Platz vorhanden ist
    -> Backtracking

Die Zeile vorher machte Backtracking
     Falls es oberhalb noch platz hat
         -> Dame nach oben verschieben
     Sonst
         -> Backtracking

Pascal Schärli 13.11.2020

Backtracking - Damen

current

Setze in jede Spalte eine Dame, so dass sich keine zwei Damen in einem Zug erreichen können:

Falls in der ersten unbesetzten Zeile Platz vorhanden ist
    -> setze möglichst weit unten

Falls kein Platz vorhanden ist
    -> Backtracking

Die Zeile vorher machte Backtracking
     Falls es oberhalb noch platz hat
         -> Dame nach oben verschieben
     Sonst
         -> Backtracking

Pascal Schärli 13.11.2020

Backtracking - Damen

current

Setze in jede Spalte eine Dame, so dass sich keine zwei Damen in einem Zug erreichen können:

Falls in der ersten unbesetzten Zeile Platz vorhanden ist
    -> setze möglichst weit unten

Falls kein Platz vorhanden ist
    -> Backtracking

Die Zeile vorher machte Backtracking
     Falls es oberhalb noch platz hat
         -> Dame nach oben verschieben
     Sonst
         -> Backtracking

Pascal Schärli 13.11.2020

Backtracking - Damen

current

Setze in jede Spalte eine Dame, so dass sich keine zwei Damen in einem Zug erreichen können:

Falls in der ersten unbesetzten Zeile Platz vorhanden ist
    -> setze möglichst weit unten

Falls kein Platz vorhanden ist
    -> Backtracking

Die Zeile vorher machte Backtracking
     Falls es oberhalb noch platz hat
         -> Dame nach oben verschieben
     Sonst
         -> Backtracking

Pascal Schärli 13.11.2020

Backtracking - Damen

current

Setze in jede Spalte eine Dame, so dass sich keine zwei Damen in einem Zug erreichen können:

Falls in der ersten unbesetzten Zeile Platz vorhanden ist
    -> setze möglichst weit unten

Falls kein Platz vorhanden ist
    -> Backtracking

Die Zeile vorher machte Backtracking
     Falls es oberhalb noch platz hat
         -> Dame nach oben verschieben
     Sonst
         -> Backtracking

Pascal Schärli 13.11.2020

Backtracking - Damen

current

Setze in jede Spalte eine Dame, so dass sich keine zwei Damen in einem Zug erreichen können:

Falls in der ersten unbesetzten Zeile Platz vorhanden ist
    -> setze möglichst weit unten

Falls kein Platz vorhanden ist
    -> Backtracking

Die Zeile vorher machte Backtracking
     Falls es oberhalb noch platz hat
         -> Dame nach oben verschieben
     Sonst
         -> Backtracking

Pascal Schärli 13.11.2020

Backtracking - Damen

current

Setze in jede Spalte eine Dame, so dass sich keine zwei Damen in einem Zug erreichen können:

Falls in der ersten unbesetzten Zeile Platz vorhanden ist
    -> setze möglichst weit unten

Falls kein Platz vorhanden ist
    -> Backtracking

Die Zeile vorher machte Backtracking
     Falls es oberhalb noch platz hat
         -> Dame nach oben verschieben
     Sonst
         -> Backtracking

Pascal Schärli 13.11.2020

Backtracking - Damen

current

Setze in jede Spalte eine Dame, so dass sich keine zwei Damen in einem Zug erreichen können:

Falls in der ersten unbesetzten Zeile Platz vorhanden ist
    -> setze möglichst weit unten

Falls kein Platz vorhanden ist
    -> Backtracking

Die Zeile vorher machte Backtracking
     Falls es oberhalb noch platz hat
         -> Dame nach oben verschieben
     Sonst
         -> Backtracking

Pascal Schärli 13.11.2020

Backtracking - Damen

current

Setze in jede Spalte eine Dame, so dass sich keine zwei Damen in einem Zug erreichen können:

Falls in der ersten unbesetzten Zeile Platz vorhanden ist
    -> setze möglichst weit unten

Falls kein Platz vorhanden ist
    -> Backtracking

Die Zeile vorher machte Backtracking
     Falls es oberhalb noch platz hat
         -> Dame nach oben verschieben
     Sonst
         -> Backtracking

Pascal Schärli 13.11.2020

Backtracking - Damen

current

Setze in jede Spalte eine Dame, so dass sich keine zwei Damen in einem Zug erreichen können:

Falls in der ersten unbesetzten Zeile Platz vorhanden ist
    -> setze möglichst weit unten

Falls kein Platz vorhanden ist
    -> Backtracking

Die Zeile vorher machte Backtracking
     Falls es oberhalb noch platz hat
         -> Dame nach oben verschieben
     Sonst
         -> Backtracking

Pascal Schärli 13.11.2020

Backtracking - Damen

current

Setze in jede Spalte eine Dame, so dass sich keine zwei Damen in einem Zug erreichen können:

Falls in der ersten unbesetzten Zeile Platz vorhanden ist
    -> setze möglichst weit unten

Falls kein Platz vorhanden ist
    -> Backtracking

Die Zeile vorher machte Backtracking
     Falls es oberhalb noch platz hat
         -> Dame nach oben verschieben
     Sonst
         -> Backtracking

Pascal Schärli 13.11.2020

Backtracking - Damen

current

Setze in jede Spalte eine Dame, so dass sich keine zwei Damen in einem Zug erreichen können:

Falls in der ersten unbesetzten Zeile Platz vorhanden ist
    -> setze möglichst weit unten

Falls kein Platz vorhanden ist
    -> Backtracking

Die Zeile vorher machte Backtracking
     Falls es oberhalb noch platz hat
         -> Dame nach oben verschieben
     Sonst
         -> Backtracking

Pascal Schärli 13.11.2020

Backtracking - Damen

Setze in jede Spalte eine Dame, so dass sich keine zwei Damen in einem Zug erreichen können:

Falls in der ersten unbesetzten Zeile Platz vorhanden ist
    -> setze möglichst weit unten

Falls kein Platz vorhanden ist
    -> Backtracking

Die Zeile vorher machte Backtracking
     Falls es oberhalb noch platz hat
         -> Dame nach oben verschieben
     Sonst
         -> Backtracking

\(\rightarrow\) Lösung gefunden!

Pascal Schärli 13.11.2020

Rucksack Problem

  • Ein Dieb ist in ein Haus eingebrochen
     
  • Der Dieb kennt von jedem Gegenstand dessen Wert \(v_i \geq 0\) sowie dessen Gewicht \(g_i \geq 0\).
     
  • Er hat eine Tasche, in welche ein Gewicht \(G\) passt.
     
  • Welche der Gegenstände  \(x_1, ...., x_K\) soll er einpacken um den Wert der Beute zu maximieren.

Pascal Schärli 13.11.2020

Rucksack - Brute Force

000

001

010

011

100

101

110

111

0kg
0.-

2kg
200.-

1kg
50.-

3kg
250.-

4kg
100.-

6kg
300.-

5kg
150.-

7kg
350.-

00X

0kg
0.-

01X

1kg
50.-

10X

4kg
100.-

11X

5kg
150.-

0XX

0kg
0.-

1XX

4kg
100.-

XXX

0kg
0.-

Kapazität: 3kg

Alter Laptop: 4kg, 100.-

Michaels: 1kg, 50.-

Katze: 2kg, 200.-

Pascal Schärli 13.11.2020

Rucksack - Brute Force

000

001

010

011

100

101

110

111

0kg
0.-

2kg
200.-

1kg
50.-

3kg
250.-

4kg
100.-

6kg
300.-

5kg
150.-

7kg
350.-

Kapazität: 3kg

Alter Laptop: 4kg, 100.-

Michaels: 1kg, 50.-

Katze: 2kg, 200.-

Zu schwer

Beste Lösung:

Michaels & Katze mit Wert 250.-

Pascal Schärli 13.11.2020

Rucksack - Backtracking

000

001

010

011

0kg
0.-

2kg
200.-

1kg
50.-

3kg
250.-

00X

0kg
0.-

01X

1kg
50.-

0XX

0kg
0.-

1XX

4kg
100.-

XXX

0kg
0.-

Kapazität: 3kg

Alter Laptop: 4kg, 100.-

Michaels: 1kg, 50.-

Katze: 2kg, 200.-

Zu schwer

Viel Arbeit erspart

Pascal Schärli 13.11.2020

Pascal Schärli 13.11.2020

Vorbesprechung

Pascal Schärli 13.11.2020

Binäre Suche Textaufgaben

Zeichnet "Entscheidungsbaum" für Binäre Suche.

Beispiel: Entscheidungsbaum für 9

1

2

4

6

9

10

14

0

1

2
3

4

5

6

6

10

9

Pascal Schärli 13.11.2020

Binäre Suche Programmieren

  • Gegeben wird ein Interface für einen Binären Suchbaum mit zwei generischen Typen:
    • Key extends Comparable<Key>
      • Einen "Key", also das Element nach welchem ihr sortieren müsst.
      • Keys könnt Ihr mit key1.compareTo(key2) vergleichen
        • 0 \(\rightarrow\) key1 = key2
        • negativ \(\rightarrow\) key1 < key2
        • positiv \(\rightarrow\) key1 > key2
    • Value
      • Ein "Value", das ist der Wert welcher ihr nach der Suche zurückgeben müsst

Pascal Schärli 13.11.2020

Rucksackproblem und Backtracking Textaufgaben

  • Gibt es beim Rucksackproblem immer nur eine Lösung?
     
  • Falls Ja \(\rightarrow\) Beweis
     
  • Falls Nein \(\rightarrow\) Gegenbeispiel

Pascal Schärli 13.11.2020

Rucksackproblem und Backtracking Programmieren

  • Klasse Selection:
    • Effizientere Art Booleans zu speichern:
      • anstatt [true, false, true, true, false, false]
      • bits = 0b101100 (= 44)
      • Bits werden hier in einem Integer gespeichert
    • Selection s = new Selection(size, bits)
      • \(\rightarrow\) Neue Selektion
    • s.set(index,value)

      • \(\rightarrow\) Bestimmtes Bit auf value (true/false) setzen

    • s.sum(werteliste)
      • \(\rightarrow\) bestimme den Wert eine Selektion aufgrund von einer Werteliste (ArrayList<Integer>)

Pascal Schärli 13.11.2020

Rucksackproblem und Backtracking Programmieren

  • Selection Beispiel:

Pascal Schärli 13.11.2020

ArrayList<Integer> values = new ArrayList(4);
values.add(10);
values.add(20);
values.add(30);
values.add(40);

// Initialize selection as 0b0101
Selection selection = new Selection(values.size(), 5);
// 0*40 + 1*30 + 0*20 + 1*10 = 40
System.out.println(selection.sum(values));

// Change selection to 0b1101
selection.set(3, true);
// 1*40 + 1*30 + 0*20 + 1*10 = 80
System.out.println(selection.sum(values));

// Change selection to 0b1001
selection.set(2, false);
// 1*40 + 0*30 + 0*20 + 1*10 = 50
System.out.println(selection.sum(values));

40

80

50

Rucksackproblem und Backtracking Programmieren

  • Brute-Fore
    • Probiert alle Selections von \(0\) bis \(2^{values.size()}\) aus und findet die beste.
  • Backtracking 
    • Vom Interface gegeben:
public Selection findBest(ArrayList<Integer> values, 
ArrayList<Integer> weights, int maxWeight);

    • Helferfunktion:
public Selection findBest(ArrayList<Integer> values,ArrayList<Integer> weights,int maxWeight,
int ptr, Selection s);

Pascal Schärli 13.11.2020

Reversi [Teil 2]

  1. Check Move
    • Gut um ein Gespür für das Gameboard zu bekommen
    • Gar nicht relevant für das Turnier
    • Besser ihr investiert mehr Zeit in andere Reversi Projekte
  2. Greedy Player
    • Macht einen Spieler, welcher immer so spielt, dass er im nächsten Zug möglichst viele Steine drehen kann
    • Kopiert das Spielbrett und probiert die möglichen Züge auf einem "hypotetischen" Gameboard aus
    • GameBoard hypothetical = gb.clone(); hypothetical.makeMove(...);

Pascal Schärli 13.11.2020

Viel Spass!

Pascal Schärli 13.11.2020