algorithm - 旅のルートをグループ化する方法（セットカバー問題）

Question

この問題を解決する必要があります:

入力:

• 都市間のルートのリスト、すべてのルートは同じ出発地から始まります
• すべての都市のセット

出力:

• すべての都市を訪問できるパスのグループ。見つからない場合は、最小限のルートで都市の大部分をカバーするグループを返します。

例：

テストケース 1:

入力

• ルートリスト:

  1. Newyork -> Washington -> Los Angeles -> Chicago
  2. Newyork -> Houston -> Alaska
  3. Newyork -> Dallas
  4. Newyork -> Houston -> Washington -> Chicago -> Los Angeles -> Alaska
  5. Newyork -> Alaska
  6. Newyork -> Chicago
  7.Newyork -> Los Angeles

• 街：Newyork, Washington, Los Angeles, Chicago, Alaska, Dallas, Houston

出力：

1. Newyork -> Houston -> Washington -> Chicago -> Los Angeles -> Alaska
2.Newyork -> Dallas

ルートが 2 つしかないため、指定されたすべての都市を訪れることができるため、これが最適なグループです。

テストケース 2:

入力

• ルートリスト:

  1. Newyork -> Washington -> Los Angeles -> Chicago
  2. Newyork -> Houston -> Alaska
  3. Newyork -> Dallas
  4. Newyork -> Alaska
  5. Newyork -> Chicago
  6.Newyork -> Los Angeles

• 街：Newyork, Washington, Los Angeles, Chicago, Alaska, Dallas, Houston

出力：

1. Newyork -> Washington -> Los Angeles -> Chicago
2. Newyork -> Houston -> Alaska
3.Newyork -> Dallas

3 つのルートですべての都市を訪問できるため、これは最適なグループです。

テストケース 3:

入力

• ルートリスト:

  2. Newyork -> Houston -> Alaska
  3. Newyork -> Dallas
  4. Newyork -> Alaska
  5. Newyork -> Chicago
  6.Newyork -> Los Angeles

• 街：Newyork, Washington, Los Angeles, Chicago, Alaska, Dallas, Houston

出力：

1. Newyork -> Houston -> Alaska
2. Newyork -> Chicago
3. Newyork -> Dallas
4.Newyork -> Los Angeles

4 つのルートで 6/7 の都市を訪問できるため、これは最適なグループです ( を除くWashington)

実装

public static void main(String[] args){
    List<List<String>> allRoutes = new ArrayList<>();
    allRoutes.add(List.of("Newyork","Washington","Los Angeles","Chicago"));
    allRoutes.add(List.of("Newyork","Houston","Alaska"));
    allRoutes.add(List.of("Newyork","Dallas"));
    allRoutes.add(List.of("Newyork","Houston","Washington","Chicago","Los Angeles","Alaska"));
    allRoutes.add(List.of("Newyork","Alaska"));
    allRoutes.add(List.of("Newyork","Chicago"));
    allRoutes.add(List.of("Newyork","Los Angeles"));
    Set<String> cities = new HashSet<>(List.of("Newyork","Houston","Washington","Chicago","Los Angeles","Alaska"));

    List<List<String>> result = findBestRoute(allRoutes, cities);
    //expected allPaths:
    //`Newyork -> Houston -> Washington -> Chicago -> Los Angeles -> Alaska`\
    //`Newyork -> Dallas`

  }

private static void findBestRoute(List<List<String>> allRoutes, Set<String> cities){
   //implementation
}

それで、私が使用できるアルゴリズムのアドバイスはありますか?