問題タブ [greedy]

次の Python 正規表現があります。

次のテキストの場合:

返されるグループは次のとおりです。
(1) 望ましいグループ #1
(2) 望ましくないグループ #2
(3) 望ましくないグループ #3
(4) 望ましくないグループ #4

なぜこうなった？Desired Group #1 を取得し、貪欲でない .+ を使用しているので? flags=re.DOTALL を使用すると、目的のグループ 2 ～ 4 のいずれもスキップされないことが期待されます。

前もって感謝します。

アップデート：

次のように xml.etree.ElementTree を使用して終了しました。

NCBI BLAST 固有の XML 解析の例に役立つ次のリンクが見つかりました: http://www.dalkescientific.com/writings/NBN/elementtree.html

私はアルゴリズムに不慣れで、現在YouTubeのビデオチュートリアル/講義と本を使用して勉強しています。最初にビデオを見てから本を読み、最後に本から質問をして、トピックを正しく学習したことを確認します。私は現在、欲張りアルゴリズムに取り組んでおり、非常に混乱しています。

本の中にはいろいろな問題がありますが、特定の問題を理解して答えるのに苦労しています。

まず、問題が発生します（テキストをコピーしました）。

サイズが{x1;のn個のオブジェクトのセットがあります。x2;.....xn}と容量Bのビン。これらはすべて正の整数です。これらのオブジェクトのサブセットを見つけて、それらの合計サイズがB以下になるようにしますが、可能な限りBに近づけます。

すべてのオブジェクトは1次元です。たとえば、オブジェクトのサイズが4、7、10、12、15、およびB = 20の場合、合計サイズが19（または同等に7と12）の4と15を選択する必要があります。次の欲張りアルゴリズムのそれぞれについて、反例を作成して、それらが最適ではないことを示します。例をできるだけ悪くするようにしてください。「悪さ」は、最適なソリューションと貪欲なソリューションの比率によって測定されます。したがって、最良の解の値が10で、欲張り解の値が5の場合、比率は2になります。

次の場合、どうすればよいですか？

1）このオブジェクトとすでに選択されている他のすべてのオブジェクトの合計サイズがBを超えないように、常に最大サイズのオブジェクトを選択します。残りのオブジェクトについてもこれを繰り返します。

次の文字列があります。

正規表現パターンを作成し、「src」が最初に現れる前にすべてを取得する必要があります。

私はそのように使用しようとしました.+(src)が、貪欲を減らす必要があることを理解したので、誰か助けてもらえますか?

Javaで実装されたGSATおよびSA-SATアルゴリズムを探しています。誰かがそれについて知っていますか？ありがとうございました。

ハングマンというゲームでは、貪欲な文字頻度アルゴリズムは、勝率が最も高いアルゴリズムと同等でしょうか?

正しい答えを推測する可能性を高めるために、残りの命の保存を犠牲にする価値がある場合はありますか?

問題のさらなる明確化:

• 推測するために選択された単語は、既知の辞書から取得されています。
• N 個の命が与えられているので、N 個の間違いを犯さずに単語のすべての文字を推測できる確率を最大化する必要があります (つまり、正しい推測の数に制限はありません)。
• この演習のために、辞書内の各単語の確率は等しくなります (つまり、単語はランダムに選択されます)。
  • より困難な演習は、悪意のある全知の単語選択者に対する戦略を考え出すことです (ここでそれを求めているわけではありません)。

動機: この質問は、 http: //www.datagenetics.com/blog/april12012/index.html での興味深い議論に触発されています。

彼らは、単語ゲーム「ハングマン」を最適に解くためのアルゴリズムを提案しています。

彼らの戦略は次のように要約できます（明確化のために編集）：

• 単語が特定の辞書から引き出されたと仮定できます
• 私たちは単語の文字数を知っています
• 文字数が正しくない単語を辞書からすべて削除します。
• 辞書の残りのサブセット内の単語数が最も多い、まだ推測されていない文字を選択します。
• この手紙が現われれば、私たちはその場所を知っています。
• この文字が出現しない場合、単語には出現しないことがわかります。
• この正しいパターンに正確に適合しない辞書サブセット内のすべての単語を削除し、繰り返します。
• 2 つ (またはそれ以上) の文字が同じ頻度で出現する場合、アルゴリズムは位置のより深い分析を実行して、どちらが優先されるかを判断します (それが妥当な場合)。

各段階で、残りの可能な単語の最大数に出現する文字 (以前は推測されていません) を推測しています。

このアルゴリズムを気に入る動機はいくつかあります。人が命を失う可能性は常に最小限です。

しかし、これが必ずしも最善の解決策であるとは限らないことに気がつきました: (一定数の生活の中で) 単語を推測しようとしている場合、最も頻繁に出現する文字が最も有用な文字であるとは限りません。残りの使用可能な単語を区別します。

ただし、可能な限り命を失うことを回避するのが適切であるように思われるため、よくわかりません. 最適な戦略によって、勝つためのより良い機会のために命を犠牲にすることができるでしょうか?

質問: この貪欲なアルゴリズムは、勝利の可能性が最も高いアルゴリズムと同等でしょうか? そしてそれを証明できますか？

ディクショナリとゲームの例は、反証を示すのに理想的です。

n 人の中で誰がパーティに来てほしいか知っています。「知っている」が対称であると仮定します。私があなたを知っている場合、あなたは私を知っています。さらに、各人がパーティーで少なくとも 5 人の新しい人に会う必要があるという要件を作成します。また、誰も孤立していると感じないように、各人はパーティーで少なくとも 5 人を既に知っている必要があります。元のリストは、これらの追加の 2 つの条件を満たさない可能性があるため、招待リストから一部の人を削除する必要がある場合があります (または、これらの制限によりパーティーをまったく開催できない場合があります)。招待して他の 2 つの要件を満たすことができる n 人の可能な最大のサブセットを見つけます。基本的な問題について、O(n^3) アルゴリズムを見つけ、その順序と論理を説明します。

答えを求めるのではなく、どこから始めるべきかについてのガイダンスを求めます。

入力は、実数 x1、x2、...、x2n のシーケンスです。これらの数値をペアにして n ペアにしたいと思います。i 番目のペア (i = 1, 2, ..., n) について、そのペアの数の合計を Si とします。(たとえば、i 番目のペアとして x(2i−1) と x2i をペアにする場合、Si = x(2i−1) + x2i)。Maxi[Si] が最小になるように、これらの数値をペアにします。この問題を解決する貪欲なアルゴリズムを設計します。

それが問題です; 私の解決策は、単純に数字を並べ替えて、最初と最後の要素をペアにし、1 を加算/1 を減算して繰り返すことです。アルゴリズムは各ペアを最適化しようとするため、貪欲になります。これを行う線形時間アルゴリズムがあるかどうか疑問に思っていますか?

PS: これは宿題ではありませんが、非常によく似ていることは理解しています。

これは、人気のある El Goog 問題のバリエーションです。

次のスケジューリングの問題を考えてみましょう。n 個のジョブがあり、i = 1..n です。スーパーコンピュータ1台、PC台数無制限。各ジョブは、最初にスーパーコンピューターで前処理され、次に PC で処理される必要があります。スーパーコンピュータ上のジョブ i の所要時間は si, i = 1..n です。PC の場合は pi、i = 1..n です。PC は並行して作業できますが、スーパーコンピューターは一度に 1 つのジョブしか処理できません。スーパーコンピュータがジョブを処理するスケジュールSが作成されます。スケジュール S の完了時刻 Ti(S) は、PC 上でジョブが終了する時刻によって与えられます。Maxi[Ti(s)] を最小化するスケジュールを見つけたい(読み方: 最高終了時間を最小化するスケジュールを見つける必要がある). 次の貪欲なアルゴリズムが提案されています。このアルゴリズムの複雑さは O(nlogn) です。このアルゴリズムが最適解を生成することを証明するか、そうでないことを示す反例を提供してください。

私の解決策 (これが正しいかどうかはわかりません): ジョブの順序は重要ではないと思います。最高終了時間は変わりません。ジョブのリストに対する PC での処理時間の例を考えてみましょう: <5、7、17、8、10>。これにより、終了時間が <5、12、29、37、47> となります。アルゴリズムに従って、リストを <17, 10, 8, 7, 5> としてソートし、終了時間は <17, 27, 35, 42, 47> になります。したがって、技術的には、貪欲なアルゴリズムは最適な順序付けを行いますが、それには nlogn の時間がかかりますが、ジョブのリストを単純に反復しても同じ結果が得られます。

貪欲なアルゴリズムの方がうまく機能する、または私のアプローチに欠陥があると考える人がいる場合は、ご意見をお待ちしております。ありがとう！

更新：答えがあると思います。スーパーコンピュータにかかる時間は関係ありません。ここで重要なのは、PC が並行して実行されることです。pi = <5, 7, 17, 8, 10> の最初の例から、si = <8, 5, 1, 12, 9> を追加しましょう。デフォルトのソートされていない順序では、処理時間は <13, 20, (8 + 5 + 1 + 17 = )31, 34, 45> になります。したがって、45 は完了の時間です。パイが減少するソート順を想定します。出力は次のとおりです。<18、20、30、34、40>。[ソートされた入力: pi = <17, 10, 8, 7, 5>, si = <1, 9, 12, 5, 8>].

おそらくすべてをクリアする例を次に示します: si = <17, 10>, pi = <10, 17>. ソートされていない場合 (si の降順でソートされていることもあります) の出力は、<27, 44> になります。pi に基づいてソートすると、入力は si = <10, 17>、pi = <17, 10> になります。出力は <27, 37> です。PC は並行して実行されるため、最短のジョブを最後に送信する必要があります。

整数列X=x1、x2 ...、xnは、次の場合にZIG-ZAGで定義されます。

xiが奇数の場合はxi<xi+1xiが偶数の場合は
xi>xi+ 1

与えられたシーケンス内の最大ZIG-ZAGサブシーケンスの次元を見つけるために欲張りアルゴリズムが必要です

編集：例があります：
Y =（3、4、8、5、6、2）
出力は3、8、5、6、2または4、8、5、6、2の場合は5である必要があります

問題文

cn与えられた整数の配列です。問題は、この合計が最小化されるようにn整数の増加する配列を見つけることです。a (a[i] <= a[i+1])

aに出現する整数によってのみ作成された最適値が存在するため、次のcDPを使用してそれを解決できますO(n^2)。

しかし、おそらくもっと速い解決策があるはずO(n lg n)です。