優先順位関数/アルファベット順の極値を見つける

Question

Eというアルファベットの要素の配列a1,a2,...aNがあります。 |N| >> |E|と仮定します。

アルファベットの各記号について、固有の整数優先度= V(sym)を定義します。簡単にするためにV{i} := V(symbol(ai))を定義しましょう。

私はのための優先機能V見つけることができますどのように：つまり

Count(i)->MAX | V{i} < V{i+1} 

を、私は、条件V{i}<V{i+1}を満たし、位置i数のアルファベットの優先順位/順列を見つける必要があります最大です。

編集-1：お読みください。私は配列aiを与えられており、タスクは関数Vを生成することです。優先度関数を使用して入力配列をソートすることについては、ではなくです。

編集-2：実施例

E = {a,b,c}; A = 'abcab$';（ここで$ =人工終了シンボル、V {$} = +無限大）

最適優先機能の1つである：V{a}=1,V{b}=2,V{c}=3、米国与えます配列要素間の符号に続く：a<b<c>a<b<$、合計で5の4 '<'の符号が得られます。

Answer 1

要素が優先順位を縛ることができなかった場合、これは簡単なことです。ちょうど優先順位で並べ替えます。しかし、あなたは同等の優先順位を持つことができます。

まず、アルファベットを優先順位で並べ替えます。その後、私は最も長い上昇サブシーケンスを抽出します。それがあなたの答えの始まりです。残っているものから最も長い上昇部分列を抽出する。あなたの答えにそれを加えてください。アルファベット全体が抽出されるまで、抽出プロセスを繰り返します。

私はこれが最適な結果をもたらすと信じていますが、私はそれを証明しようとしていません。それが完全に最適でない場合、それはまだかなり良いでしょう。

私はこの問題を理解していると思うので、それを解決するアルゴリズムはありません。

これを見るには、頂点があなたの要素である有向グラフを作成し、そのエッジが1つの要素が別の要素の直前の何回を示すかを示しましょう。優先順位関数を作成するには、有向非循環グラフを得るために十分な辺を削除し、辺を使って部分的に順序付けられた集合を作成し、完全な線形秩序が得られるまで順序関係を追加します。どのエッジをドロップするかを考えれば、これは簡単です。逆に、有向グラフと最終的な優先順位関数を考慮すると、どの辺をドロップするか決定するのは簡単です。

したがって、あなたの問題は、非環式有向グラフ を取得する有向グラフ からドロップする必要があるエッジの最小セットを考え出すと全く同じです。しかし、 http://en.wikipedia.org/wiki/Feedback_arc_setによれば、これは最小フィードバックアークセットと呼ばれる既知のNP困難な問題です。 begin updateしたがって、あなたが考えることができるグラフのアルゴリズムは非常に少ないです。 最終更新

実際に解決する必要がある場合は、欲張りアルゴリズムのいくつかの並べ替えに行くことをお勧めします。それは必ずしも正しいとは限りませんが、それは一般的に合理的な時間にいくらか合理的な結果を与えます。

更新：モロンは正しいです、私はNP-hardを証明しませんでした。しかし、問題は実際にはNP困難であると考える良いヒューリスティックな理由があります。詳細はコメントを参照してください。

Answer 2

円弧をオイラーパスに配置できる有向グラフの最小帰還円弧集合からの些細な削減があります。私はhttp://www14.informatik.tu-muenchen.de/personen/jacob/Publications/JMMN07.pdfから引用：

我々の知る限り、そのようなグラフに設定された最小のフィードバックの 複雑ステータス アークが開いています。 しかし、ニューマン、陳の補題、 とLovász[1、定理4]により、[この問題】 ための多項式アルゴリズムは、問題の設定一般的な最小 フィードバックアークため16/9近似 アルゴリズムにつながります現在最もよく知られているO（log n log log n）アルゴリズム[2]に対して、 を改善しています。

1. Newman、A：最大非循環サブグラフ問題と次数-3のグラフ。 In：第4回 国際ワークショップ の近似アルゴリズム の近似アルゴリズム、最適化問題、 了解。有向グラフにおける近似最小帰還量 および有向グラフにおけるマルチカット（multiple-cuts）である。 In： 第4回国際シンポジウム予稿集 整数プログラミングに関する解説 と組み合わせ最適化。 LNCS （1995）14-28