5

私は NP 困難であると思われる組み合わせ最適化問題に取り組んでおり、遺伝的アルゴリズムは私たちのデータセットでうまく機能しています。私たちは研究グループであり、私たちの分野 (数学や CS ではなく) で結果を公開する予定です。原稿をレビューに送る前に、NP 困難な問題を調査したいと思います。

主な質問は 2 つあります。

1) この特定の最適化問題が研究されているかどうか知りたいです。私はライトを徹底的に検索しましたが、まったく同じものは見たことがありません.

2）問題が研究されていない場合は、還元可能性の証明を行うことに挑戦する可能性があり、還元のための優れたNP完全候補へのいくつかのポインターが必要です。

この問題は、サブシーケンス バリアントと 2 部グラフ問題の 2 つの方法で説明できます。

サブシーケンス フレーバーでは、順列を許可する「リラックスした」サブシーケンスを見つけ、最適化して順列数を最小限に抑えたいと考えています。例: (. = その他の文字)

クエリ: abc、ターゲット: ..babc、結果: abc (通常のサブシーケンス)

クエリ: abc、ターゲット: ..baca、結果: bac (1 つの順列を持つサブシーケンス)

二部定式化は、マッチング問題または線形代入問題であり、グラフはクエリ文字ノードとターゲット文字ノードに分割されます。エッジは、各クエリ文字からターゲット文字へのエッジが 1 つだけ存在するように、クエリ文字をターゲット文字に接続します。目的関数は、エッジ交差の数 (「交差数」とも呼ばれます) を最小化することです。これは、エッジの交差を最小限に抑えるためにノードの配置を並べ替える 2 部グラフ レイアウト アルゴリズムに似ていますが、私の問題では、両方のノードの順序が固定されている必要があります。

質問 1 または 2 に関する専門家からの意見はありますか?

前もって感謝します！

4

4 に答える 4

1

これはNP困難ではないと思います。Pevzner と Hannehali の作品をご覧ください。「キャベツからカブまで」というタイトルの論文が思い浮かびます。アイデアは、ある文字列から別の文字列に移動するための反転の最小数を見つけることです。このための polytime アルゴリズムがあります。

于 2014-01-03T02:48:17.560 に答える
1

ちょっとしたアイデア: 配列をソートするために必要な最小数のスワップ (MIN-SBR) を見つけることと何らかの形で同等ですか? はいの場合、これはNP-Hardです。

（ところで、これに似たものに取り組んでいますか？）

于 2010-10-14T00:44:42.900 に答える
0

クエリ: abc ターゲット: ..cbaa 結果: cba、3 つの順列 (用語の使用による) でしょうか? もしそうなら、順列ではなく転置を意味しているのかもしれません。転置とは、隣接する 2 つの文字を入れ替えることです。

良い質問。交差 ができるだけ少ないクエリ -> ターゲットからのマッピングに関心があります。これが、元の投稿で 2 部エッジ クロッシングについて言及した動機です。または、Spearman の Rho のように、マッピングでランク統計を最大化することを考えることができます。

また、好奇心から、クエリ/ターゲットにはいくつの一意の文字がありますか? – ジャスティン・ピール 18

典型的なクエリ: 100、典型的なターゲット: 1000。組み合わせ的に、これは巨大なソリューション スペースです。

于 2010-10-15T16:03:33.357 に答える
0

「単語問題」の問題はもっと難しいはずですよね？– J-16 SDiZ 14

はい、ターゲットに char が複数回出現すると、MIN-SBR よりも問題が難しくなるように思われるため、その角度から見ると、少なくとも NP 完全と同じくらい難しい問題になります。一方で、ブロック反転の中心的な概念が NP 完全性の私の主張にどのように影響するかについては、まだ明確ではありません。

私の最適化が多項式時間で解決できるかどうかを知りたいです。別の言い方をすれば、レビュアーが O(n) でグローバルな最大値を見つける 5 行の疑似コードで戻ってきたら、確かに恥ずかしいでしょう.

于 2010-10-14T19:13:29.687 に答える