Letný semester, prednáška č. 9

Oznamy

• Dnes po prednáške bude zverejnené zadanie štvrtej domácej úlohy, ktorú bude potrebné odovzdať do pondelka 26. apríla, 9:00 (čiže do začiatku jedenástej prednášky).
• Počas stredajších cvičení bude prebiehať štvrtý test zameraný predovšetkým na grafy a grafové algoritmy.
• V rámci stredajších cvičení tiež bude zverejnené zadanie tretej bonusovej úlohy s termínom odovzdania do stredy 21. apríla, 11:30.

Prehľadávanie s návratom na grafoch: pokračovanie

Hľadanie najdlhšej cesty

Uvažujme problém nájdenia niektorej z najdlhších ciest z vrcholu u do vrcholu v daného orientovaného grafu (ak existuje aspoň jedna). Je dokázané, že za predpokladu platnosti určitých hypotéz z teoretickej informatiky pre túto úlohu neexistuje žiaden efektívny algoritmus. Použijeme teda prehľadávanie s návratom. To bude realizovať trieda LongestPath, ktorú získame drobnou úpravou triedy FixedLengthPaths z minulej prednášky.

• Počas prehľadávania si budeme pamätať najdlhšiu doposiaľ nájdenú cestu.
• Vždy, keď prídeme do cieľového vrcholu, porovnáme dĺžku práve nájdenej cesty s najdlhšou doposiaľ nájdenou cestou.

package graphs;

import java.util.*;

/**
 * Trieda realizujuca najdenie najdlhsej cesty medzi danou dvojicou vrcholov grafu.
 */
public class LongestPath {
    /**
     * Graf, v ktorom sa hladanie ciest realizuje.
     */
    private Graph g;

    /**
     * Pociatocny vrchol hladanych ciest.
     */
    private int from;

    /**
     * Koncovy vrchol hladanych ciest.
     */
    private int to;

    /**
     * Pomocny zoznam, v ktorom sa budu pomocou prehladavania s navratom postupne generovat jednotlive cesty.
     */
    private LinkedList<Integer> path;

    /**
     * Pomocny zoznam, v ktorom si budeme pocas generovania ciest pre kazdy vrchol pamatat, ci sa nachadza alebo
     * nenachadza v doposial vygenerovanej casti cesty.
     */
    private ArrayList<Boolean> visited;

    /**
     * Zoznam, v ktorom bude ulozena najdlhsia cesta medzi danou dvojicou vrcholov (pocas prehladavania pojde
     * o najdlhsiu doposial najdenu cestu).
     */
    private List<Integer> longestPath;

    /**
     * Konstruktor, ktory rovno aj spusti prehladavanie s navratom a do zoznamu longestPath ulozi niektoru spomedzi
     * najdlhsich ciest medzi danou dvojicou vrcholov grafu.
     * @param g      Graf, v ktorom sa hladanie ciest realizuje.
     * @param from   Pociatocny vrchol hladanych ciest.
     * @param to     Koncovy vrchol hladanych ciest.
     */
    public LongestPath(Graph g, int from, int to) {
        this.g = g;
        this.from = from;
        this.to = to;

        visited = new ArrayList<>();
        for (int i = 0; i <= g.getNumberOfVertices() - 1; i++) {
            visited.add(false);
        }
        path = new LinkedList<>();
        path.add(from);
        visited.set(from, true);
        search();
    }

    /**
     * Metoda realizujuca samotne rekurzivne prehladavanie s navratom. V pripade, ze sa vygenerovala cesta konciaca
     * vo vrchole to, porovna sa jej dlzka s dlzkou doposial najdlhsej najdenej cesty a ak je dlhsia, ulozi sa ako nova
     * doposial najdlhsia cesta. V opacnom pripade sa vyskusaju vsetky moznosti predlzenia cesty.
     */
    private void search() {
        if (path.getLast() == to) {
            if (longestPath == null || path.size() > longestPath.size()) {
                longestPath = new LinkedList<>(path);
            }
        } else {
            for (int successor : g.outgoingEdgesDestinations(path.getLast())) {
                if (!visited.get(successor)) {
                    visited.set(successor, true);
                    path.add(successor);
                    search();
                    path.removeLast();
                    visited.set(successor, false);
                }
            }
        }
    }

    /**
     * Metoda, ktora vrati najdenu najdlhsiu cestu medzi danou dvojicou vrcholov.
     * @return Nemodifikovatelny pohlad na zoznam vrcholov na najdlhsej ceste z vrcholu from do vrcholu to.
     */
    public List<Integer> getLongestPath() {
        if (longestPath != null) {
            return Collections.unmodifiableList(longestPath);
        } else {
            return null;
        }
    }
}

Použitie triedy:

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    System.out.println("Zadaj graf:");
    Graph g = readGraph(scanner, GraphType.DIRECTED_SUCCESSOR_LISTS);
    System.out.println("Zadaj pociatocny a koncovy vrchol:");
    int from = scanner.nextInt();
    int to = scanner.nextInt();

    LongestPath longestPath = new LongestPath(g, from, to); 
    List<Integer> longest = longestPath.getLongestPath();
    if (longest != null) {
        System.out.println("Najdlhsia cesta: " + longest);
    } else {
        System.out.println("Ziadna cesta neexistuje.");
    }
}

Príklad výstupu pre graf na obrázku vyššie, počiatočný vrchol 0 a koncový vrchol 3:

Najdlhsia cesta: [0, 1, 2, 4, 3]

Hľadanie najväčšej kliky v neorientovanom grafe

Uvažujme teraz neorientované grafy bez slučiek (slučky síce nebudeme zakazovať, ale v našich nasledujúcich úvahách ich budeme ignorovať; najvhodnejšia predstava teda je, že pracujeme s grafmi, ktoré žiadne slučky neobsahujú).

• Klikou (angl. clique) v neorientovanom grafe rozumieme jeho úplný podgraf, čiže podmnožinu K množiny vrcholov grafu takú, že každé dva rôzne vrcholy z K sú navzájom spojené hranou. Veľkosťou kliky rozumieme počet vrcholov kliku tvoriacich. Špeciálne každý vrchol sám o sebe tvorí kliku veľkosti jedna a ľubovoľné dva vrcholy spojené hranou tvoria kliku veľkosti dva.
• V grafoch na nasledujúcom obrázku sú vyznačené kliky veľkosti tri a štyri.

Budeme sa teraz zaoberať problémom nájdenia najväčšej kliky (angl. maximum clique) v neorientovanom grafe.

• Ide o nájdenie kliky s najväčšou veľkosťou spomedzi všetkých klík daného grafu.
• Pozor na terminológiu: maximálna klika (angl. maximal clique) je ľubovoľná klika, ktorú nemožno pridaním ďalšieho vrcholu rozšíriť na väčšiu kliku. Nie každá maximálna klika ale musí byť aj najväčšia. My sa budeme zaoberať prakticky užitočnejším problémom hľadania najväčších klík.
• Aj pre problém najväčšej kliky je dokázané, že v prípade platnosti určitých hypotéz z teoretickej informatiky preň neexistuje žiaden efektívny algoritmus. Použijeme teda prehľadávanie s návratom – nebudeme ním však teraz konštruovať cesty, ale množiny vrcholov grafu.