3

Techgig.com で問題を解決しているときに、ある問題にぶつかりました。問題は次のようなものです。

ある会社は、従業員のために年に 2 回の旅行を計画しています。彼らは、すべての従業員を旅行に派遣できるかどうかを知りたがっています。条件は、従業員が両方の旅行に行くことができないようなものです。また、どの従業員が一緒に働くことができるかを決定するための制約は、過去に一緒に働いた従業員が同じグループに属さないことです。問題の例:

作業履歴が次のように与えられているとします: {(1,2),(2,3),(3,4)}; その場合、4 人の従業員全員を 2 回の旅行 (従業員 1 と 3 で構成される 1 回の旅行と、従業員 2 と 4 で構成される旅行) で収容することができます。同じ出張に参加した 2 人の従業員は、過去に一緒に働いたことはありません。職歴が {(1,2),(1,3),(2,3)} の場合、会社の規則を満たし、全従業員を収容する 2 回の出張はあり得ません。

この問題の進め方を誰か教えてもらえますか?

このコードを DFS に使用し、頂点に色を付けています。

static boolean DFS(int rootNode) {
        Stack<Integer> s = new Stack<Integer>();
        s.push(rootNode);
        state[rootNode] = true;
        color[rootNode] = 1;
        while (!s.isEmpty()) {
            int u = s.peek();
            for (int child = 0; child < numofemployees; child++) {
                if (adjmatrix[u][child] == 1) {
                    if (!state[child]) {
                        state[child] = true;
                        s.push(child);
                        color[child] = color[u] == 1 ? 2 : 1;
                        break;
                    } else {
                        s.pop();
                        if (color[u] == color[child])
                            return false;
                    }    

                }
            }
        }
        return true;
    }
4

2 に答える 2

4

この問題は、無向グラフが二部かどうかをテストすることと機能的に同等です。二部グラフは、すべてのノードを 2 つのセットに分散できるグラフであり、各セット内で別のノードに隣接するノードはありません。

この問題を解決するには、次の手順を実行します。

  1. 隣接ペアを使用して、無向グラフを作成します。これは非常に簡単です。各番号はノードを表し、指定された各ペアに対して、それらのノード間の接続を形成します。
  2. 新しく生成されたグラフの二部性をテストします。ここで説明されているように、これは線形時間で達成できます。
  3. グラフが 2 部構成で、2 つのノード セットを生成した場合、問題の答えは「はい」であり、各ノード セットとそのノード (従業員) は 2 つのトリップのいずれかに対応します。

二部性をテストする方法の抜粋:

深さ優先探索を使用して、グラフが 2 部構成かどうかをテストし、線形時間で 2 色 (2 部構成の場合) または奇数サイクル (2 部構成でない場合) を返すことができます。主なアイデアは、深さ優先検索ツリーの親の色とは異なる色を各頂点に割り当て、深さ優先検索ツリーの事前順トラバーサルで色を割り当てることです。これにより、必ず、頂点をその親に接続するエッジで構成されるスパニング ツリーの 2 色が提供されますが、非ツリー エッジの一部は適切に色付けされない場合があります。深さ優先検索ツリーでは、すべての非ツリー エッジの 2 つのエンドポイントの 1 つが他のエンドポイントの祖先であり、深さ優先検索でこのタイプのエッジが検出された場合、これら 2 つの頂点の色が異なることを確認する必要があります。そうでない場合は、次に、祖先から子孫へのツリー内のパスは、色の誤ったエッジとともに、奇妙なサイクルを形成します。これは、グラフが 2 部ではないという結果とともにアルゴリズムから返されます。ただし、このタイプの奇数サイクルを検出せずにアルゴリズムが終了した場合は、すべてのエッジを適切に色付けする必要があり、アルゴリズムはグラフが 2 部であるという結果と共に色付けを返します。

于 2012-09-01T06:53:18.390 に答える
0

再帰的な解決策も使用しましたが、これも同じ数のケースを渡しています。特殊なケースの処理は任せますか?

以下は、問題の再帰的な解決策です。

static void dfs(int v, int curr) {
        state[v] = true;
        color[v] = curr;

        for (int i = 0; i < numofemployees; i++) {
            if (adjmatrix[v][i] == 1) {
                if (color[i] == curr) {
                    bipartite = false;
                    return;
                }

                if (!state[i])
                    dfs(i, curr == 1 ? 2 : 1);
            }
        }
    }

は開始頂点であり、色の 1 つであるため、この関数main()を呼び出しています。dfs(0,1)01

于 2012-09-02T09:10:55.647 に答える