1

たとえば、 RPG のキャラクターは、いろいろな能力値をもっています。(体力・素早さ・etc...)

つまりは、それぞれのキャラクター能力は、ベクトルで表せる、と表現できます。

# 例えば、 pandas を用いてキャラクター能力値を表現する
chara1 = pd.Series({'power': 1, 'speed': 2, 'magic': 3})
chara2 = pd.Series({'power': 2, 'speed': 1, 'magic': 2})

今、キャラクター A とキャラクター B がいたとき、もし、 A の能力値がすべて B のそれと同等かそれ以上である場合、キャラクター A はキャラクター B の上位互換であるとします。

質問

キャラクターが N 体いたときに、上位互換が存在しないキャラクターの集合を求めたいです。どのように計算するのが効率的ですか?

(数学的な言い換え) ベクトル値の集合に対して、その上下関係を、「すべての要素について同等かそれ以上であって、かつ、少なくとも一つの要素が上回っている場合、そのベクトル値は、比較対象より上位であるとする」と定義した半順序集合に対して、その極大集合を効率的に求める方法は何でしょうか?

3
  • 全てのキャラクタの対について、上位互換かどうか
    – Fumu 7
    2019年4月15日 5:50
  • 総当たりで計算するしかないので、万能な『効率的』計算方法は存在しないはず。
    – Fumu 7
    2019年4月15日 6:29
  • ベクトルの次元よりNが十分大きければ、kd木使うだけでも総当たりよりはマシになりませんか
    – zakki
    2019年4月16日 5:11

0

この質問に回答するには、ログインする必要があります。

のタグが付いた他の質問を参照する。