Кратчайший путь с помощью Meet In The Middle
Дана перестановка P = p 1 , p 2 ,…., P n первых n натуральных чисел (1 ≤ n ≤ 10) . Можно поменять местами любые два последовательных элемента p i и p i + 1 (1 ≤ i <n) . Задача состоит в том, чтобы найти минимальное количество перестановок, чтобы заменить P на другую перестановку P '= p' 1 , p ' 2 ,…., P' n .
Примеры:
Input: P = “213”, P’ = “321”
Output: 2
213 <-> 231 <-> 321
Input: P = “1234”, P’ = “4123”
Output: 3
Подход: эту проблему можно решить с помощью алгоритма кратчайшего пути Дейкстры. Кажется, что в заявлении нет ничего, что связано с графиком. Но предположим, что одна перестановка - это одна вершина, тогда каждая перестановка элементов перестановки - это ребро, которое соединяет эту вершину с другой вершиной. Таким образом, поиск минимального количества свопов теперь становится простой проблемой BFS / кратчайшего пути.
Теперь проанализируем временную сложность. У нас есть n! вершин, каждая вершина имеет n - 1 смежную вершину. Мы также должны хранить вершины, посещенные в состоянии по карте, потому что их представления трудно сохранить в обычных массивах. Таким образом, общая временная сложность составляет O (N log (N!) * N!) . Для ускорения решения можно использовать технику Meet In The Middle.
Решение Meet In The Middle похоже на решение Дейкстры с некоторыми изменениями.
- Пусть P - начальная вершина, а P ' - конечная вершина.
- Пусть и начало, и конец будут корнями. Мы запускаем BFS из обоих корней, запускаем и заканчиваем одновременно, но используя только одну очередь.
- Поместите начало и конец в конец очереди, посещенное начало = посещение финиш = истина .
- Пусть src u - корень вершины u в прогрессии BFS. Итак, src start = start и src finish = finish .
- Пусть D u - кратчайшее расстояние от вершины u до корня дерева. Итак, D start = D finish = 0 .
- Пока очередь не пуста, вытолкните переднюю часть очереди, которая является вершиной u, затем вытолкните все вершины v , смежные с u и еще не посещенные (посещенные v = false), в заднюю часть очереди, затем пусть D v = D u + 1 , src v = src u и посетил v = true . В частности, если v был посещен и src v ! = Src u, мы можем немедленно вернуть D u + D v + 1 .
Ниже представлена реализация описанного выше подхода:
C ++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to find minimum number of // swaps to make another permutation int ShortestPath( int n, string start, string finish) { unordered_map<string, bool > visited; unordered_map<string, int > D; unordered_map<string, string> src; visited[start] = visited[finish] = true ; D[start] = D[finish] = 0; src[start] = start; src[finish] = finish; queue<string> q; q.push(start); q.push(finish); while (!q.empty()) { // Take top vertex of the queue string u = q.front(); q.pop(); // Generate n - 1 of it's permutations for ( int i = 1; i < n; i++) { // Generate next permutation string v = u; swap(v[i], v[i - 1]); // If v is not visited if (!visited[v]) { // Set it visited visited[v] = true ; // Make root of u and root of v equal src[v] = src[u]; // Increment it's distance by 1 D[v] = D[u] + 1; // Push this vertex into queue q.push(v); } // If it is already visited // and roots are different // then answer is found else if (src[u] != src[v]) return D[u] + D[v] + 1; } } } // Driver code int main() { string p1 = "1234" , p2 = "4123" ; int n = p1.length(); cout << ShortestPath(n, p1, p2); return 0; } |
Джава
// Java implementation of the approach import java.util.*; class GFG{ // Function to find minimum number of // swaps to make another permutation static int ShortestPath( int n, String start, String finish) { HashMap<String, Boolean> visited = new HashMap<String, Boolean>(); HashMap<String, Integer> D = new HashMap<String, Integer>(); HashMap<String, String> src = new HashMap<String, String>(); visited.put(start, true ); visited.put(finish, true ); D.put(start, 0 ); D.put(finish, 0 ); src.put(start, start); src.put(finish, finish); Queue<String> q = new LinkedList<>(); q.add(start); q.add(finish); while (q.size() != 0 ) { // Take top vertex of the queue String u = (String)q.peek(); q.remove(); // Generate n - 1 of it's permutations for ( int i = 1 ; i < n; i++) { // Generate next permutation StringBuilder tmp = new StringBuilder(u); char t = tmp.charAt(i); tmp.setCharAt(i, tmp.charAt(i - 1 )); tmp.setCharAt(i - 1 , t); String v = tmp.toString(); // If v is not visited if (!visited.getOrDefault(v, false )) { // Set it visited visited.put(v, true ); // Make root of u and root of v equal src.put(v, src.get(u)); // Increment it's distance by 1 D.put(v, D.get(u) + 1 ); // Push this vertex into queue q.add(v); } // If it is already visited // and roots are different // then answer is found else if (src.get(u) != src.get(v)) return D.get(u) + D.get(v) + 1 ; } } return 0 ; } // Driver Code public static void main(String[] args) { String p1 = "1234" , p2 = "4123" ; int n = p1.length(); System.out.println(ShortestPath(n, p1, p2)); } } // This code is contributed by pratham76 |
Python3
# Python3 implementation of the approach from collections import deque, defaultdict # Function to find minimum number of # swaps to make another permutation def shortestPath(n: int , start: str , finish: str ) - > int : visited, D, src = defaultdict( lambda : False ), defaultdict( lambda : 0 ), defaultdict( lambda : '') visited[start] = visited[finish] = True D[start] = D[finish] = 0 src[start], src[finish] = start, finish q = deque() q.append(start) q.append(finish) while q: # Take top vertex of the queue u = q[ 0 ] q.popleft() # Generate n - 1 of it's permutations for i in range (n): v = list (u) v[i], v[i - 1 ] = v[i - 1 ], v[i] v = ''.join(v) if not visited[v]: # Set it visited visited[v] = True # Make root of u and root of v equal src[v] = src[u] # Increment it's distance by 1 D[v] = D[u] + 1 # Push this vertex into queue q.append(v) # If it is already visited # and roots are different # then answer is found elif u in src and src[u] ! = src[v]: return D[u] + D[v] + 1 # Driver Code if __name__ = = "__main__" : p1 = "1234" p2 = "4123" n = len (p1) print (shortestPath(n, p1, p2)) # This code is contributed by # sanjeev2552 |
C #
// C# implementation of the approach using System; using System.Collections; using System.Text; using System.Collections.Generic; class GFG{ // Function to find minimum number of // swaps to make another permutation static int ShortestPath( int n, start, string string finish) { Dictionary< string , bool > visited = new Dictionary< string , bool >(); Dictionary< string , int > D = new Dictionary< string , int >(); Dictionary< string , string > src = new Dictionary< string , string >(); visited[start] = true ; visited[finish] = true ; D[start] = 0; D[finish] = 0; src[start] = start; src[finish] = finish; Queue q = new Queue(); q.Enqueue(start); q.Enqueue(finish); while (q.Count != 0) { // Take top vertex of the queue string u = ( string )q.Peek(); q.Dequeue(); // Generate n - 1 of it's permutations for ( int i = 1; i < n; i++) { // Generate next permutation StringBuilder tmp = new StringBuilder(u); char t = tmp[i]; tmp[i] = tmp[i - 1]; tmp[i - 1] = t; string v = tmp.ToString(); // If v is not visited if (!visited.GetValueOrDefault(v, false )) { // Set it visited visited[v] = true ; // Make root of u and root of v equal src[v] = src[u]; // Increment it's distance by 1 D[v] = D[u] + 1; // Push this vertex into queue q.Enqueue(v); } // If it is already visited // and roots are different // then answer is found else if (src[u] != src[v]) return D[u] + D[v] + 1; } } return 0; } // Driver Code public static void Main( string [] args) { string p1 = "1234" , p2 = "4123" ; int n = p1.Length; Console.Write(ShortestPath(n, p1, p2)); } } // This code is contributed by rutvik_56 |
3
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.