np - VoidCC

np

0熱

1答えて

私は、整数リストの整数値を因数分解できるかどうかを判断するスクリプトを作成しようとしています。私がやったやり方は、有効な因子分解のためにrecursivleyを検索することです。有効な要素のツリー内でDFSを実行します（下記のコードを参照）。これは速く見つける貪欲なアルゴリズムを作ることは可能ですか？私の考えは、有効な因数分解が見つかるまで、残りの部分で最大の要素を探し続けることでした。この場合正

1熱

1答えて

kがサブセット合計でO（n^k）に対して定数であるかどうかをどのように知ることができますか？

サブセット合計問題：数字のセットSとターゲット番号が与えられたとすると、0となります。その目的は、サブセットS’がSであり、その要素が0になるようにすることです。私はこの問題がS’のサイズが与えられれば多項式になると聞いた。例えば、3の要素が0になるという手掛かりがある場合、複雑さはO(n^3)です。クラスPは、多項式時間で解ける問題から成ります。例えば、ある定数がkの場合、O(n^k)で解く

0熱

2答えて

データフレームパンダ

は、カントは、私が持っているすべてでこれを行うように見える追加名 ['BKH' 'EDE'] と私は new = pd.DataFrame(columns=['Name']) を持っているとのリストを出してくれる df.Name.unique() 私は基本的に新しく追加する名前のリストを新しく追加したい（column = 'Name）誰かが私が間違っていることを知っていますか？私は

2熱

1答えて

時間の複雑さn ^（O（k））は何を表していますか？

私は最近問題に遭遇し、それが時間n ^（O（k））で決定される可能性があり、これは依然として問題がNPにあることを意味することを読む。この複雑さは何を表していますか？どのように非決定論的な多項式時間の複雑さですか？

0熱

2答えて

可能な限り最短距離の距離を知ったら、トラベリングセールスマンを解決してください

私はTSP (Travelling Salesman Problem)を解決しようとしていますが、伝統的な方法では解決しません。私はこれらの手順に従っています。 1）まず私が真/偽問題へのTSPを変更します。この問題の定義は次のとおりです。「合計距離がkより小さいか等しいすべての都市のルートはありますか？」私はそれを解決するアルゴリズムTSP_tf(k)を持っていると仮定しよう。 2）そしてIが

-1熱

1答えて

{0,1}^nの半分の文字列を持つNFA

言語L（M）が{0,1} *のサブセットであるNFA Mがある場合、L（M） n> = 0の{0,1}^nの文字列の半分以下がNP-hardです。

1熱

1答えて

これはサブセットの合計を解決する良い方法ですか？

私は、より高速なサブセット和問題を解決するための基本的な方法をしようとしていたし、私は素朴な方法は、すべての2^n個の組み合わせをテストoldSS機能、である。このを思い付きました。しかし、その後、それぞれのケースをチェックする前に、現在のシナリオで可能な最小値と最大値を計算し、ターゲットがその範囲の横にある場合、潜在的にそこに解決策がある可能性があることに気付きました。これはnewSS関数です

4熱

1答えて

「自然な」NP完全型probとは何ですか？

私はNP-Complete、NP-Hardなどの一般的な知識はかなりあると思いますが、突然何らかの文献に間違いがありました。それらの引用符で。私は彼らが何を意味しているのか理解していなかったので、私はそれをグーグルにしようとしました - それは何度かポップアップしましたが、「自然な」NP完全な問題を言うときに意味するものは何ですか？

0熱

1答えて

特定のノードにアクセスする単純なパスが存在するかどうかを判断しますか？

グラフ<V, E>、開始ノードst、終了ノードedおよび特定のノードセットMが必要です。私の質問は、すべてを訪問している単純なパスを見つけることですM。また、私は知りたいです： 1パスは存在しますか？ 2存在する場合は、できるだけ早く見つける方法はありますか？

0熱

1答えて

矛盾によって硬度がどのように低下するか？

私は計算複雑なコースを受講する学生ではなく、そのテーマに興味があります。私は、このセクションに出くわした：と仮定我々が証明してきた問題は、を解決することは困難である必要があり、私たちは似た新しい問題を抱えています。私たちはそれが解決するのが難しいと思われるかもしれません。我々は矛盾によって議論する：新しい問題が解決しやすいであると仮定する。次に、古い問題のすべてのインスタンスを新しい問題