まず、お粗末なタイトルで申し訳ありません。このアルゴリズムにふさわしい名前が思い浮かびません。
私はステージの順序付きリストを持っています。各ステージには、順不同のキャラクターのキャストがあります。キャラクターは複数のステージで発生する可能性があります。
交差は、2 つの連続するステージがキャストを連結できない場合に発生します。オーバーラップは許可され、両方のキャストで同じキャラクターが統合され、連結でキャラクターが複製されたままになります。または、非公式に言えば、交差とは、組み合わせたキャストのラインナップで、キャラクターが一度に 2 つの異なる場所にいる必要がある場合です。コード内:
uncrossed = [D, F], [N, V, S]
overlap = [D, F, V], [V, N, S]
crossed = [D, V, F], [N, V, S]
最初の例では、V は D および F と一緒ではないため、交差はありません。2 番目の例では、V は D と F を使用し、次に N と S を使用していますが、これは問題ではありません。なぜなら、この順序付けでは交差のない連結が (オーバーラップを使用して) 許可されているからです。ただし、3 番目の例では、順序付けによって交差が強制されます。
私の目的では、キャラクターが「ステージ上」にいないときに、キャラクターがキャストの以前の順序から実際に逸脱していないかのように、連続していないステージで交差が発生する可能性があります。
どうしても交差が避けられない状況が発生する可能性があることを理解し、可能な限り交差がないように各ステージのキャストを配置したいと思います。交差が必要なシリーズの例:
required = [A, B], [B, C], [A, C], [A, B]
これはすべて非常に抽象的でばかげているように聞こえるので、人間がこのアルゴリズムを私の目的と同様の目的で解決する具体的な例を示します: http://xkcd.com/657/この場合、美的観点から制約は意図的に無視されます。しかし、私が話していることを視覚的に理解することはまだ可能です。
私はすでにこれを解決する方法について大雑把なアイデアを持っていますが、手頃な価格のものはありません。これは、文献で既に取り上げられている問題と同型であるかどうか疑問に思っています。漠然としたトポロジーにも聞こえます。
人々から尋ねられたので、このアルゴリズムは、ストーリー内のキャラクターの絵コンテのきれいなタイムラインを自動的に生成するための鍵であるように見えます.