6

少なくとも1回は文字azを含む単語のリストがある場合、単語の組み合わせとして文字数（スペースを数えない）で数えた最短のパングラムを見つけるプログラムをどのように作成しますか？

短い答えが存在するかどうかわからないので、これはコードゴルフではなく、これにどのようにアプローチするかについての議論にすぎません。ただし、これを実行する短いプログラムを作成できると思われる場合は、先に進んでください。これはコードゴルフに変わる可能性があります:)

4

4 に答える 4

7

問題がNP困難であることを証明し、類似しているNP困難問題のヒューリスティックをチェックすることによってこれにアプローチします。

集合被覆問題を自分たちの問題に減らすことができます。集合被覆は、使用される文字の数が最小化されるのではなく、代わりに使用される単語の数が最小化されるという点で異なります。それぞれがM未満の長さのN個の単語が与えられた場合に、集合被覆問題を解決したいとします。与えられたセットを複製し、それぞれにN * Mの英語以外の文字、たとえばЖを連結して、別の単語のセットを作成しましょう。最小限の記号を必要とするパングラム（a、b、c ... x、y、z、жアルファベット）を作成できれば、すべてのЖ文字を削除すると、最小限の単語を含むパングラムになります。

これは、元の問題がNP困難であることを証明していますが、残念ながら、その（うまくいけばすでに知られている）ヒューリスティックを再利用するには、いくつかのNP困難問題に減らす必要があります。集合被覆は対数近似による欲張りヒューリスティックですが、元の問題には当てはまらないと思います（集合被覆問題の性質上、文字が豊富で長い単語を使用する必要があります。問題を解決する方法ではありません）。

そこで、関連するNP困難な問題のリストを検索し、何か興味深いものがあるかどうかを確認します。それが私がこれにアプローチする方法です。

于 2010-04-25T19:30:20.300 に答える
2

これは集合被覆問題（別名、集合被覆問題）の変形です。

入力として、いくつかのセットが与えられます。それらにはいくつかの共通の要素があるかもしれません。選択したセットに、入力のいずれかのセットに含まれるすべての要素が含まれるように、これらのセットの最小数を選択する必要があります。[...] 1972年にNP完全であることが示され[、]、集合被覆の最適化バージョンはNP困難です。

単語の最小数ではなく、文字の最小数を探しているため、これはバリアントです。しかし、それでもNP困難であると思います。つまり、ブルートフォースよりもはるかに優れたパフォーマンスを発揮することはできません。

于 2010-04-25T19:30:44.217 に答える
2

入力として単語のリストの代わりに文字列がある場合の別の問題O(n)のアルゴリズムを次に示します。。それは私の見落としでしたが、私はそれを削除したくないので、ここに解決策を残します:)

キャラクターだけに興味があるので、問題がずっと簡単になります。[a-z]文字列内のその位置への各文字のマップを維持します。このマップだけで、パングラムがあるかどうかとその長さを判断するのに十分です。

1. Initialize a map of all alphabets to null
2. Initialize shortest_pangram to { length: ∞, value: undefined }
3. Loop through each "character" in given string
  3.1 Update the value of map[character] to current string index
  3.2 If we have a pangram, and its the shortest so far, record its length/value
4. shortest_pangram should have our result

作成したマップは、パングラムがあるかどうかを判断するのに十分です。マップ内のすべての値がnullでない場合は、パングラムがあります。

現在のパングラムの長さを見つけるには、マップの最小値から最大値を引きます。長さを見つける前に、それがパングラムであるかどうかを確認する必要があることを忘れないでください。

これは、Rubyでの単純な最適化されていない実装です。

class Pangram
  def initialize(string)
    @input = string.downcase.split('')
    @map = {}
    ('a'..'z').each { |c| @map[c] = nil }
    infinity = 1.0/0.0
    @best = { :length => infinity, :string => nil }
  end

  def shortest
    @input.each_with_index do |c, index|
      @map[c] = index if @map.key?(c)
      if pangram? and length < @best[:length]
        @best[:length] = length
        @best[:string] = value
      end
    end
    @best
  end

  def pangram?
    @map.values.all? { |value| !value.nil? }
  end

  def length
    @map.values.max - @map.values.min
  end

  def value
    @input[@map.values.min..@map.values.max].join('')
  end
end

使用するには、クラスをインスタンス化し、文字列全体を渡します。.shortestを呼び出して、最短のパングラムと一致するサブストリングの長さを見つけます。

pangram = Pangram.new("..")
print pangram.shortest
于 2010-04-25T20:48:13.810 に答える
1

これは古い質問なので、おそらくあなたはすでに好きなヒューリスティックをいくつか見つけたでしょう。文字数が最も少ない完璧なパングラムを生成する方法を模索しているときに、この質問に出くわしました（アルファベットの各文字の使用は1回しか許可されていないため）。とにかく、私のような将来の発見者のために：

私はある程度の成功を収めたプログラムを書きました。私はこの問題を集合被覆よりもグラフ検索のように扱い、アルゴリズムの開始点としてA*を使用しました。githubでコードを調べることができます。

最も役に立ったのは次のとおりです。

状態空間を圧縮する

私は辞書を取り、すべての単語をソートされた文字セットに変換しました。たとえば、このように「BAD」と「DAB」は両方とも「ABD」として保存されます。私が使用した圧縮辞書は、約250,000語から約31,000の一意の文字の組み合わせになり、これは大成功です。

経験則

他の場所で述べたように、これはNP困難なので、ヒューリスティックを使い始めました。私が現在使用している3つは次のとおりです。

母音比

単語を選んだ後に残っている文字を調べるとき、私は#vowels/#unusedLettersを計算します。この動機は非常に単純です。母音が残っていると、それらの文字を使用して単語を選択できる可能性が高くなります。

文字の共通性

最初の単語セットを読むとき、アルファベットの各文字の辞書を作成し、各文字がすべての単語に出現する回数を数えます。私はこの辞書を使用して、残りの文字がより一般的な文字を含むノードを優先しました。（OPはコメントの1つでこれについて言及したと思います）

共有3文字コンボ

これは、文字の共通性ヒューリスティックに似ています。繰り返しになりますが、最初の単語セットを処理するときに、その単語で作成できる3文字の組み合わせをすべて含む辞書を作成しました。たとえば、文字セットABCには有効なコンボが1つしかありませんが、ABCDには[ABC、ABD、BCD]があります。覚えておいてください、私は最初のワードセットを圧縮した後にソートされた文字セットだけを気にします。

したがって、最終的には、文字の共通性の尺度が好きである必要があります。私は、26個すべての可能な文字セットをマッピングする辞書を持っています。これらのコンボが私のワードセット全体に現れる回数にマッピングされます。次に、これを使用して、残りの文字がより有効な3文字のコンボを持つノードの検索を優先します。

于 2016-01-01T20:39:25.600 に答える