Алгоритм распечатки всех возможных расписаний курсов - PullRequest
Новая
       8

Алгоритм распечатки всех возможных расписаний курсов

0 голосов
/ 31 марта 2020

Это известный вопрос о расписании курсов, но вы хотите распечатать все возможные расписания курсов.

В: Существуют курсы «N», помеченные от «0» до «N-1». Каждый курс может иметь несколько обязательных курсов, которые необходимо завершить, прежде чем он может быть запланирован. Учитывая количество курсов и список обязательных пар, напишите метод печати всех возможных порядков курсов, соответствующих всем предварительным условиям. Предположим, что цикла нет.

Для примера в основном методе необходимо вывести [3, 2, 0, 1] [3, 2, 1, 0]

, но мой код печатает только один из них [3, 2, 1, 0]

Для его работы необходим возврат, но в какой-то момент мой возврат неверен и я не уверен, как это исправить, поскольку он продолжает выбирать то же самое заказ после возврата. Однажды выбрав 1, 0, а затем вернуться назад, он должен выбрать 0, 1, но продолжает выбирать тот же порядок 1, 0.

Может ли кто-нибудь помочь мне заставить его работать? 

class AllCourseOrders {
  static Map<Integer, List<Integer>> map = null;
  static int[] visited = null;
  static int n = 0;

  public static void printOrders(int courses, int[][] prerequisites) {
    List<Integer> sortedOrder = new ArrayList<>();

    // init
    n = courses;
    visited = new int[courses];
    map = new HashMap<>();
    for(int i =0; i < courses; i++) 
      map.put(i, new ArrayList<>());

    // 1. build graph
    for(int[] pre: prerequisites) {
      int from = pre[0], to = pre[1];
      List<Integer> list = map.get(from);
      list.add(to);
    }

    // 2. dfs
    List<List<Integer>> results = new ArrayList<List<Integer>>();
    List<Integer> result = new ArrayList<>();

    for(Integer u: map.keySet()) {
      if(visited[u] == 0) {
        dfs(u, result, results);
        if(result.size() == n) {
          results.add(new ArrayList<>(result));
          result.remove(result.size()-1);
          visited[u] = 0;
        }
      }
    }

    results.forEach(res -> System.out.println(res));
  }

  static void  dfs(Integer u, List<Integer> result, List<List<Integer>> results) {
    visited[u] = 1;

    for(Integer v: map.get(u)) {
      if(visited[v] == 0 ) {
        dfs(v, result, results);
     }
    }

    visited[u] = 2;
    result.add(0, u);
  }

  public static void main(String[] args) {
   printOrders(4, new int[][] { new int[] { 3, 2 }, new int[] { 3, 0 }, new int[] { 2, 0 }, new int[] { 2, 1 } });
 }
}

1 Ответ

2 голосов
/ 31 марта 2020

Ваш алгоритм находит первое возможное решение, а не каждое. Каждый раз, когда вам предоставляется несколько вершин для выбора следующих (вы можете выбрать разные начальные узлы, определенный класс вы можете выбрать в любом порядке), каждый выбор приведет к различному результату.

Задача курса - просто попытаться топологически отсортировать направленный ациклический c граф. GeeksForGeeks предоставляет алгоритм на своем сайте в java, где вершины - это курсы, а ребра - предварительные требования.

...