ABP – Alpha-Beta Pruning

private BiPredicate<Integer, Node> searchLimitingPredicate; private int depth; public AlphaBetaSearch(BiPredicate<Integer, Node> searchLimitingPredicate) { this.searchLimitingPredicate = searchLimitingPredicate; } public Pair<Node, Double> search(Node start, Function<Node, Double> evalFunction) { Node winner = start; double value = Double.NEGATIVE_INFINITY; double alpha = Double.NEGATIVE_INFINITY; double beta = Double.POSITIVE_INFINITY; for (Node n : start.adjacent()) { double temp = min(n, evalFunction, alpha, beta); if …

DLS – Depth-Limited Search

private StackWithFastContains<Node> path; private int limit; public DLDFS(int limit) { this.limit = limit; } public Node search(Node start, Predicate<Node> endPredicate) { //Initial the stackWithFastContains path = new StackWithFastContains<>(); return searchForNode(start, endPredicate, limit); } private Node searchForNode(Node currentNode, Predicate<Node> toSearchFor, int depth){ path.push(currentNode); if (depth >= 0) { //As long as we are depth > or …

GBFS – Greedy Best-First Search

private Function<Node, Double> heuristic; public GBFS(Function<Node, Double> heuristic) { this.heuristic = heuristic; } public Node search(Node start, Predicate<Node> endPredicate) { //Check if the start node is the endPredicate if (endPredicate.test(start)) return start; //The queue containing all the nodes we have to search for StablePriorityQueue<Double, Node> nodeQueue = new StablePriorityQueue<>(); //Add the start node as the …

MM – MinMax Search

private BiPredicate<Integer, Node> searchLimitingPredicate; private int depth; /** * To limit the extent of the search, this implementation should honor a * limiting predicate. The predicate returns ‘true’ as long as we are below * the limit, and ‘false’, if we exceed the limit. * * @param searchLimitingPredicate */ public MinMaxSearch(BiPredicate<Integer, Node> slp) { this.searchLimitingPredicate …

A* – AStar

private Function<Node, Double> heuristic; private Function<Node, Double> cost; public ASTAR(Function<Node, Double> heuristic, Function<Node, Double> cost) { this.heuristic = heuristic; this.cost = cost; } //A class to store heuristic and costs and also the possibility to compare each other. private class CostPair implements Comparable<CostPair> { private double heuristic; private double cost; private CostPair(double heuristic, double cost) …

UCS – Uniform Cost-Search

private Function<Node, Double> cost; public UCS(Function<Node, Double> cost) { this.cost = cost; } public Node search(Node start, Predicate<Node> endPredicate) { //The queue containing all the nodes we have to search for StablePriorityQueue<Double, Node> nodeQueue = new StablePriorityQueue<>(); //Add the start node as the head. The priority does not matter since we remove it anyway. nodeQueue.add(new …

BFS – Breadth-First Search

public Node search(Node start, Predicate<Node> endPredicate) { //Check if the start node is the endPredicate if(endPredicate.test(start)) return start; //The queue containing all the nodes we have to search for //We used ArrayDeque because it has the best performance of all queues. ArrayDeque<Node> nodeQueue = new ArrayDeque<>(start.adjacent()); //Adjacent, definition from the handbook.pdf contain all neighbors. //That …

Heapsort

  Die Datenstruktur des Heapsortes ist ein Binärbaum. An der “Wurzel” des Baumes befindet sich immer das Element, welches als nächstes benötigt wird. (Min,Max,Priority,etc.) Somit muss beim Einfügen und beim Entfernen eines Elementes der Baum immer wieder sortiert werden. Die Laufzeit ist hierbei asymptotisch und beträgt O(n * log(n)).

Base64 En/Decode

Base64 ist ein Verfahren, um Daten mit insgesamt nur 64 ASCII-Zeichen darstellen zu können. Die codierten Daten können von jedem System gelesen und zurückkonvertiert werden. Vorteile Lesbar von jedem System Codepage unabhängige Zeichen Nicht alle Protokolle können erlauben eine 8bit Kodierung. Nach Base64 sind die Daten 6bit kodiert. Der neue Bytestream besteht nur aus den …

IPv4 in Int32

Gewöhnliche Subnet Rechner verwenden einen 32-bit Integer für die Berechnung der benötigten Daten. (Mask, Wildcard, Host, Host-range etc…) Jedoch wie ist da möglich? Wie passt eine Zeichenkette wie: 255.255.255.255 in einen Integer? Theorie Sehen wir uns die IP-Adresse einmal etwas genauer an. In der folgenden Tabelle seht Ihr, dass jede Zahl von 0 bis 255 …