問題タブ [np-hard]

したがって、基本的に次のような問題があります。文字列がたくさんあり、すべてのパスが文字列に対応するように、またはその逆になるようにDAGを構築したいと思います。ただし、文字列を任意に並べ替える自由があります。文字の順序は関係ありません。私が生成するDAGには、それに関連するコストがあります。基本的に、DAGのブランチのコストは、その子パスの長さに比例します。

たとえば、文字列BAAA、CAAA、DAAAがあり、それらを並べ替えることなくそれらを表すDAGを作成するとします。私は得る：

（）->（B、C、D）-> A-> A-> A

ここで、タプルは分岐を表します。

私の目的のためのより安価な表現は次のようになります：

（）-> A-> A-> A->（B、C、D）

問題は次のとおりです。n個の文字列が与えられた場合、対応するDAGのコストが最も低くなるように文字列を並べ替えます。ここで、コスト関数は次のとおりです。多様性を持って訪問してください。

したがって、最初の例のコストは12です。これは、トラバーサルでAを複数回訪問する必要があるためです。2番目の例のコストは6です。これは、ブランチを処理する前にAを1回だけ訪問するためです。

この問題はNP困難だと感じています。形式言語についての質問のようで、私はそのような種類のアルゴリズムに精通していないため、削減をどのように行うべきかを理解できません。完全な答え自体は必要ありませんが、誰かが関連していると思われるよく知られた問題のクラスを指摘できれば、それをいただければ幸いです。

グラフ問題として定式化できる多くの問題に遭遇しました。一般にNP困難ですが、グラフが平面であることが証明される場合があります。したがって、これらの問題とアルゴリズムを学ぶことに興味があります。

私が知る限り：

1. 平面グラフの最大カット
2. 平面グラフの 4 色
3. 立方平面グラフの最大独立集合

誰かがこのリストを完成させてくれることを願っています。

それぞれ値が 1<=X<=10^6 の N 個の整数を含むセット S があります。問題は、セット S を k 個のパーティションに分割することです。パーティションの値は、そこに存在する要素の合計です。分割は、セット S の合計値が k 個の分割に均等に分配されるように行われます。公正さの数学的意味も定義する必要があります (たとえば、目的は、集合 S の平均値からのパーティションの値の標準偏差 (つまり、sum(S)/k) を最小化することである可能性があります)。

例: S = {10, 15, 12, 13, 30, 5}, k=3

適切なパーティショニングは、{30}、{10, 15}、{12, 13, 5} です。

不適切なパーティショニングは {30, 5}、{10, 15}、{12, 13} です。

最初の質問は、あるパーティションが他のパーティションよりも優れている条件を数学的に表現することです。2番目の質問は、問題を解決する方法です。問題は NP-Hard です。ヒューリスティックはありますか？

N <= (k*logX)^2 を解決しようとしている問題で、K は 2 から 7 まで変化します。

================================================== ================================

他の関連する SO の質問に基づいて、分布を評価するための 2 つの合理的な関数があります。

a) 最大値を持つパーティションの値を最小化します。

よく考えてみると、これは良い指標ではありません。セット {100, 40, 40} を 3 つのサブセットに分割するとします。このメトリックは、次の 2 つの分布を区別しませんが、一方が他方よりも明らかに優れています。

分布 1: {100}、{40}、{40} および分布 2: {100}、{40、40}、{}

b) 特定のパーティション内の任意の 2 つの値の差の最大値を最小化します。つまり、max|AB| を最小化します。任意の A、B

私は1つの問題で髪を引っ張ってきました...全体的な問題は複雑です...しかし、本当に重要な部分を説明するために最善を尽くします...

各エッジが接続された2つのノード間の相関を表すグラフがあります。各ノードはタイムコース（TC）（つまり、400の時点）であり、イベントはさまざまな時点で発生します。2つのノード間の相関は、重複するイベントのパーセンテージとして定義されます。この例を簡単にするために、各ノードで発生するイベントの総数が$tn$と同じであると仮定します。また、2つのTC（ノード）に$ on $のオーバーラップイベント（つまり、まったく同じ時点で発生したイベント）がある場合。次に、相関は単純に$ on $ / $tn$として定義できます。

今、私は11ノードのネットワークを持っています。そして私は2つのノードごとの相関関係を知っています。相関制約を満たす11ノードすべてのTCを生成するにはどうすればよいですか？

2つのノード間の相関関係がわかっている場合、2つのノードに対してこれを行うのは簡単です。TC_1とTC_2の相関値が0.6であると想定します。これは、2つのTCで60％の重複イベントがあることを意味します。また、イベントの総数は、TC_1とTC_2の両方で$tn$と同じであると想定します。2つのTCにイベントを配置する簡単なアルゴリズムは、最初に0.6 * $ tn $の時点をランダムに選択し、それらを両方のTCで重複したイベントが発生したタイムスロットと見なします。次に、TC_1で（1-0.6）* $ tn $の時点をランダムに選択して、TC_1の残りのイベントを配置します。最後に、TC_2の対応する時点でイベントが発生しなかったTC_2の（1-0.6）* $tn$時点をランダムに選択します。

ただし、生成された3つのTCが3つの相関制約すべて（つまり、3つのエッジ）を満たす必要がある3ノードネットワークを考えると、難しくなり始めます...11ノードネットワークではこれを行うことはほとんど不可能です。 ..。。

これはあなたにとって意味がありますか？そうでない場合はお知らせください...

これは単なる計算機科学のプログラミングの問題だと思っていましたが、考えれば考えるほど線形計画問題のようですね。

誰かが合理的な解決策を持っていますか？私はこれをRで行っていますが、どのコードでも問題ありません...

開始点に戻る方法を考慮したTSPw/ oの問題名と、これを解決するためのアルゴリズムを知りたいです。

最短経路問題を調べましたが、それは私が探しているものではありません。問題は、割り当てられた2つのポイントから最短経路を見つけるだけです。しかし、私が探しているのは、nポイントを与え、1つの開始点のみを入力するという問題です。次に、すべてのポイントを1回だけ移動する最短経路を見つけます。（終点は任意の点にすることができます。）

ハミルトン閉路問題も調べましたが、定義された問題を解決するのではなく、ハミルトン閉路があるかどうかを調べました。

指定されたスケジュール問題 P||Cmax では:

n- スケジュールするタスクの数
m- マシン
ベクトルの数p- n 個のタスクのそれぞれの作業時間を保持します。

pは毎回どのように定義されますか?

つまり、整数か浮動小数点数か?

NP完全であることがわかっている問題Aを多項式時間で別の問題Bに還元できる場合、Bは（A）NP完全（B）NP困難です。

問題BがNPにあるかどうかにかかわらず、問題Bについては何も示されていません。Hopcraft and Ullmanの本には、NP完全問題P1を多項式時間で問題P2に還元できる場合、P2はNP完全であるという定理があるため、私は混乱しています。ただし、問題がNP完全である必要があり、それがNPクラスに属している必要があります。男はこの概念を理解するのに役立ちます。

すべての行が単語を形成し（左から右）、すべての列が単語を形成する（上から下）ように、可能な限り最大の文字の長方形を見つけるプログラムを作成します。

この興味深い質問を見つけました。宿題ではありませんが、そのように聞こえるかもしれません。（私は学校にいません）。私は楽しみのためにこれをやっています。

例

cat、car、ape、api、rep、tipから、次の長方形（正方形）が得られます。

私の最初のアイデアは、特定の文字列で始まるすべての単語を取得できるように、ある種のプレフィックスツリーを構築することです。これは、すでに2つ以上の単語（上から下または左から右のいずれかを読んでいる）があり、追加する次の単語を見つける必要がある場合に役立ちます。

他のアイデアはありますか？

編集

これは直方体（3D長方形）で行うことができますか？

対角線上に有効な単語が必要な場合はどうなりますか（アイデアクレジット：user645466）。そのためのアルゴはどのように最適化されますか？

問題が np-hard であることを示したい場合、既存の np-hard 問題を複数回使用しても問題ありませんか? たとえば、n が頂点の数であるグラフでハミルトニアン サイクルを n 回使用しますか? または、グラフを、1回使用された既存のnp困難な問題で簡単に解決できるものに変換する必要がありますか?

ウィキによると、ポリ時間の np complte 問題を A に変換すると、 A は np ハードです。http://en.wikipedia.org/wiki/NP-hardを参照

しかし、以下の pdf は、多項式時間で np ハード問題を問題 A に変換すると、A は np ハード http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/21-nphard であると述べています。 pdf

どっちを信じればいい?