wake-up-neo.com

Wie berechnet man die Zeitkomplexität des Backtracking-Algorithmus?

Wie lässt sich die Zeitkomplexität für diese Backtracking-Algorithmen berechnen und haben sie dieselbe Zeitkomplexität? Wenn anders wie? Erklären Sie bitte ausführlich und danke für die Hilfe. 

1. Hamiltonian cycle:

        bool hamCycleUtil(bool graph[V][V], int path[], int pos) {
            /* base case: If all vertices are included in Hamiltonian Cycle */
            if (pos == V) {
                // And if there is an Edge from the last included vertex to the
                // first vertex
                if ( graph[ path[pos-1] ][ path[0] ] == 1 )
                    return true;
                else
                    return false;
            }

            // Try different vertices as a next candidate in Hamiltonian Cycle.
            // We don't try for 0 as we included 0 as starting point in in hamCycle()
            for (int v = 1; v < V; v++) {
                /* Check if this vertex can be added to Hamiltonian Cycle */
                if (isSafe(v, graph, path, pos)) {
                    path[pos] = v;

                    /* recur to construct rest of the path */
                    if (hamCycleUtil (graph, path, pos+1) == true)
                        return true;

                    /* If adding vertex v doesn't lead to a solution, then remove it */
                    path[pos] = -1;
                }
            }

            /* If no vertex can be added to Hamiltonian Cycle constructed so far, then return false */
            return false;
        }

2. Word break:

       a. bool wordBreak(string str) {
            int size = str.size();

            // Base case
            if (size == 0)
                return true;

            // Try all prefixes of lengths from 1 to size
            for (int i=1; i<=size; i++) {
                // The parameter for dictionaryContains is str.substr(0, i)
                // str.substr(0, i) which is prefix (of input string) of
                // length 'i'. We first check whether current prefix is in
                // dictionary. Then we recursively check for remaining string
                // str.substr(i, size-i) which is suffix of length size-i
                if (dictionaryContains( str.substr(0, i) ) && wordBreak( str.substr(i, size-i) ))
                    return true;
            }

            // If we have tried all prefixes and none of them worked
            return false;
        }
    b. String SegmentString(String input, Set<String> dict) {
           if (dict.contains(input)) return input;
           int len = input.length();
           for (int i = 1; i < len; i++) {
               String prefix = input.substring(0, i);
               if (dict.contains(prefix)) {
                   String suffix = input.substring(i, len);
                   String segSuffix = SegmentString(suffix, dict);
                   if (segSuffix != null) {
                       return prefix + " " + segSuffix;
                   }
               }
           }
           return null;
      }


3. N Queens:

        bool solveNQUtil(int board[N][N], int col) {
            /* base case: If all queens are placed then return true */
            if (col >= N)
                return true;

            /* Consider this column and try placing this queen in all rows one by one */
            for (int i = 0; i < N; i++) {
                /* Check if queen can be placed on board[i][col] */
                if ( isSafe(board, i, col) ) {
                    /* Place this queen in board[i][col] */
                    board[i][col] = 1;

                    /* recur to place rest of the queens */
                    if ( solveNQUtil(board, col + 1) == true )
                        return true;

                    /* If placing queen in board[i][col] doesn't lead to a solution then remove queen from board[i][col] */
                    board[i][col] = 0; // BACKTRACK
                }
            }
        }

Ich bin tatsächlich etwas verwirrt, da für Word Break (b) die Komplexität O (2) istn) aber für Hamilton 's Zyklus ist es anders und dies gilt auch für das Drucken verschiedener Permutationen der gleichen Zeichenfolge und dann für das Lösen von n Damenproblemen. 

16
da3m0n

Zusamenfassend:

  1. Hamilton-Zyklus: O(N!) im schlimmsten Fall
  2. WordBreak und StringSegment: O(2^N)
  3. NQueens: O(N!)

Hinweis: Für WordBreak gibt es eine dynamische O (N ^ 2) -Programmierlösung.


Mehr Details:

  1. Im Hamilton-Zyklus wird in jedem rekursiven Aufruf im ungünstigsten Fall einer der verbleibenden Eckpunkte ausgewählt. Bei jedem rekursiven Aufruf wird der Verzweigungsfaktor um 1 verringert. In diesem Fall kann die Rekursion als n verschachtelte Schleifen betrachtet werden, wobei in jeder Schleife die Anzahl der Iterationen um eins verringert wird. Daher ist die zeitliche Komplexität gegeben durch:

    T(N) = N*(T(N-1) + O(1))
    T(N) = N*(N-1)*(N-2).. = O(N!)

  2. In ähnlicher Weise nimmt in NQueens der Verzweigungsfaktor jedes Mal um 1 oder mehr ab, jedoch nicht viel, daher die Obergrenze von O(N!)

  3. Für WordBreak ist es komplizierter, aber ich kann Ihnen eine ungefähre Vorstellung geben. In WordBreak hat jedes Zeichen der Zeichenfolge im schlimmsten Fall zwei Auswahlmöglichkeiten: entweder der letzte Buchstabe im vorherigen Wort oder der erste Buchstabe eines neuen Wortes. Daher ist der Verzweigungsfaktor 2. Daher sowohl für WordBreak als auch für SegmentString T(N) = O(2^N)

24
Vikram Bhat

Rückverfolgung von Algo:

n-queen Problem: O (n!)

farbproblem der Grafik: O (nm ^ n) // wobei n = no. des Scheitelpunkts, m = nein. der verwendeten Farbe

hamilton-Zyklus: O (N!)

WordBreak und StringSegment: O (2 ^ N)

summenproblem der Teilmenge: O(nW)

2
Shyam Bhimani