21

サイクルを含む、指定された重み付けされていない有向グラフでトポロジカル ソートを実行する方法を探しています。結果には、頂点の順序だけでなく、指定された順序に違反しているエッジのセットも含まれている必要があります。このエッジのセットは最小限にする必要があります。

入力グラフが大きくなる可能性があるため、指数時間アルゴリズムを使用できません。多項式時間で最適解を計算することが不可能な場合、与えられた問題に対してどのヒューリスティックが妥当でしょうか?

4

2 に答える 2