Upgrade to Pro — share decks privately, control downloads, hide ads and more …

競技プログラミングとマトロイド

 競技プログラミングとマトロイド

マトロイドの基礎と競技プログラミングにおける問題演習です。この資料は「限界!アルゴリズム」での7/1の発表向けに作られました。自由に活用、共有していただいて構いませんが自作発言および商用利用はお控えください。
Matroid/Competitive Programming

seekworser

July 01, 2023
Tweet

Other Decks in Programming

Transcript

  1. 競技プログラミングとマトロイド
    seekworser(ぷせうど)
    Twitter: @pseudo_thermal

    View Slide

  2. 目次
    ◼ 貪欲法
    ◼ マトロイド
    ◼ 問題演習

    View Slide

  3. View Slide

  4. Greed: 強欲・貪欲
    Greedy: 貪欲な

    View Slide

  5. 貪欲法で解くことができる問題
    N枚のカードがあります。i枚目のカードにはaiという数が書かれています。
    AliceとBobは、これらのカードを使ってゲームを行います。ゲームではAliceとBobが交互に1枚ずつカードを取っていきます。
    Alice が先にカードを取ります。
    2人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2人とも自分の得点
    を最大化するように最適な戦略を取った時、AliceはBobより何点多く取るか求めてください。
    制約
    Nは1以上100以下の整数
    ai(1≤i≤N) は1以上100以下の整数
    ABC088B - Card Game for Two (diff 93、灰色)

    View Slide

  6. 貪欲法で解くことができる問題
    N枚のカードがあります。i枚目のカードにはaiという数が書かれています。
    AliceとBobは、これらのカードを使ってゲームを行います。ゲームではAliceとBobが交互に1枚ずつカードを取っていきます。
    Alice が先にカードを取ります。
    2人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2人とも自分の得点
    を最大化するように最適な戦略を取った時、AliceはBobより何点多く取るか求めてください。
    制約
    Nは1以上100以下の整数
    ai(1≤i≤N) は1以上100以下の整数
    ABC088B - Card Game for Two (diff 93、灰色)
    20 18 2 18

    View Slide

  7. 貪欲法で解くことができる問題
    N枚のカードがあります。i枚目のカードにはaiという数が書かれています。
    AliceとBobは、これらのカードを使ってゲームを行います。ゲームではAliceとBobが交互に1枚ずつカードを取っていきます。
    Alice が先にカードを取ります。
    2人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2人とも自分の得点
    を最大化するように最適な戦略を取った時、AliceはBobより何点多く取るか求めてください。
    制約
    Nは1以上100以下の整数
    ai(1≤i≤N) は1以上100以下の整数
    ABC088B - Card Game for Two (diff 93、灰色)
    20 18 2 18
    Alice

    View Slide

  8. 貪欲法で解くことができる問題
    N枚のカードがあります。i枚目のカードにはaiという数が書かれています。
    AliceとBobは、これらのカードを使ってゲームを行います。ゲームではAliceとBobが交互に1枚ずつカードを取っていきます。
    Alice が先にカードを取ります。
    2人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2人とも自分の得点
    を最大化するように最適な戦略を取った時、AliceはBobより何点多く取るか求めてください。
    制約
    Nは1以上100以下の整数
    ai(1≤i≤N) は1以上100以下の整数
    ABC088B - Card Game for Two (diff 93、灰色)
    20 18 2 18
    Alice Bob

    View Slide

  9. 貪欲法で解くことができる問題
    N枚のカードがあります。i枚目のカードにはaiという数が書かれています。
    AliceとBobは、これらのカードを使ってゲームを行います。ゲームではAliceとBobが交互に1枚ずつカードを取っていきます。
    Alice が先にカードを取ります。
    2人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2人とも自分の得点
    を最大化するように最適な戦略を取った時、AliceはBobより何点多く取るか求めてください。
    制約
    Nは1以上100以下の整数
    ai(1≤i≤N) は1以上100以下の整数
    ABC088B - Card Game for Two (diff 93、灰色)
    20 18 2 18
    Alice Bob
    Alice Bob
    各手番のプレイヤーは、明らかに自身の手番において残っている最も大きい数字を貪欲に選ぶのが最適
    →カードの数列をソートして、大きいものから順にAlice→Bob→Alice…と割り振ったときの得点の差が答え!→AC

    View Slide

  10. 貪欲法で解くことができる問題
    N枚のカードがあります。i枚目のカードにはaiという数が書かれています。
    AliceとBobは、これらのカードを使ってゲームを行います。ゲームではAliceとBobが交互に1枚ずつカードを取っていきます。
    Alice が先にカードを取ります。
    2人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2人とも自分の得点
    を最大化するように最適な戦略を取った時、AliceはBobより何点多く取るか求めてください。
    制約
    Nは1以上100以下の整数
    ai(1≤i≤N) は1以上100以下の整数
    ABC088B - Card Game for Two (diff 93、灰色)
    20 18 2 18
    Alice Bob
    Alice Bob
    各手番のプレイヤーは、明らかに自身の手番において残っている最も大きい数字を貪欲に選ぶのが最適
    →カードの数列をソートして、大きいものから順にAlice→Bob→Alice…と割り振ったときの得点の差が答え!→AC
    ところで……

    View Slide

  11. 貪欲法で解くことができる問題
    N枚のカードがあります。i枚目のカードにはaiという数が書かれています。
    AliceとBobは、これらのカードを使ってゲームを行います。ゲームではAliceとBobが交互に1枚ずつカードを取っていきます。
    Alice が先にカードを取ります。
    2人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2人とも自分の得点
    を最大化するように最適な戦略を取った時、AliceはBobより何点多く取るか求めてください。
    制約
    Nは1以上100以下の整数
    ai(1≤i≤N) は1以上100以下の整数
    ABC088B - Card Game for Two (diff 93、灰色)
    20 18 2 18
    Alice Bob
    Alice Bob
    各手番のプレイヤーは、明らかに自身の手番において残っている最も大きい数字を貪欲に選ぶのが最適
    →カードの数列をソートして、大きいものから順にAlice→Bob→Alice…と割り振ったときの得点の差が答え!→AC
    ところで……ここ、そんなに「明らか」ですか?

    View Slide

  12. 貪欲法で解くことができる問題
    N枚のカードがあります。i枚目のカードにはaiという数が書かれています。
    AliceとBobは、これらのカードを使ってゲームを行います。ゲームではAliceとBobが交互に1枚ずつカードを取っていきます。
    Alice が先にカードを取ります。
    2人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2人とも自分の得点
    を最大化するように最適な戦略を取った時、AliceはBobより何点多く取るか求めてください。
    制約
    Nは1以上100以下の整数
    ai(1≤i≤N) は1以上100以下の整数
    ABC088B - Card Game for Two (diff 93、灰色)
    20 18 2 18
    Alice Bob
    Alice Bob
    各手番のプレイヤーは、明らかに自身の手番において残っている最も大きい数字を貪欲に選ぶのが最適
    →カードの数列をソートして、大きいものから順にAlice→Bob→Alice…と割り振ったときの得点の差が答え!→AC
    ところで……ここ、そんなに「明らか」ですか?→証明しましょう

    View Slide

  13. 貪欲法で解くことができる問題
    N枚のカードがあります。i枚目のカードにはaiという数が書かれています。
    AliceとBobは、これらのカードを使ってゲームを行います。ゲームではAliceとBobが交互に1枚ずつカードを取っていきます。
    Alice が先にカードを取ります。
    2人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2人とも自分の得点
    を最大化するように最適な戦略を取った時、AliceはBobより何点多く取るか求めてください。
    制約
    Nは1以上100以下の整数
    ai(1≤i≤N) は1以上100以下の整数
    ABC088B - Card Game for Two (diff 93、灰色)
    証明したいこと:上のゲームにおいて各手番のプレイヤーは残っている最も大きい数字を選ぶことが最適である。
    ①カードが1枚しかない場合
    手番のプレイヤーは1枚しか無いカードを選ぶ他無く、これは最も大きい数字でもあるので、
    カード1枚のゲームにおいては上が最適戦略である。

    View Slide

  14. 貪欲法で解くことができる問題
    N枚のカードがあります。i枚目のカードにはaiという数が書かれています。
    AliceとBobは、これらのカードを使ってゲームを行います。ゲームではAliceとBobが交互に1枚ずつカードを取っていきます。
    Alice が先にカードを取ります。
    2人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2人とも自分の得点
    を最大化するように最適な戦略を取った時、AliceはBobより何点多く取るか求めてください。
    制約
    Nは1以上100以下の整数
    ai(1≤i≤N) は1以上100以下の整数
    ABC088B - Card Game for Two (diff 93、灰色)
    証明したいこと:上のゲームにおいて各手番のプレイヤーは残っている最も大きい数字を選ぶことが最適である。
    ②カードがk枚のゲームにおいて上が双方最適戦略であると仮定して、カードが(k+1)枚ある場合
    ……
    ……
    カードk枚のゲームについては双方最大のカードを取るのが最適で
    あるので、最初にAliceが取るカードを決めるとゲームの最後までに
    双方が取るカードが決まる。
    このとき、もしも最初に最大以外のカードを選んでいたとすると、
    Aliceが最終的に取るカードは「最初に最大を選んだ場合」以下の
    カードのみであるので、最適ではなくなってしまう。
    したがって、最大のカードを取ることが最適
    →数学的帰納法により、上の戦略が最適であることが示された!
    最初に最大以外のカードを取ると、必ず「最初に最
    大を選んだ場合」以下の得点しか獲得できない

    View Slide

  15. 貪欲法で解くことができる問題
    N枚のカードがあります。i枚目のカードにはaiという数が書かれています。
    AliceとBobは、これらのカードを使ってゲームを行います。ゲームではAliceとBobが交互に1枚ずつカードを取っていきます。
    Alice が先にカードを取ります。
    2人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2人とも自分の得点
    を最大化するように最適な戦略を取った時、AliceはBobより何点多く取るか求めてください。
    制約
    Nは1以上100以下の整数
    ai(1≤i≤N) は1以上100以下の整数
    ABC088B - Card Game for Two (diff 93、灰色)
    証明したいこと:上のゲームにおいて各手番のプレイヤーは残っている最も大きい数字を選ぶことが最適である。
    ②カードがk枚のゲームにおいて上が双方最適戦略であると仮定して、カードが(k+1)枚ある場合
    ……
    ……
    カードk枚のゲームについては双方最大のカードを取るのが最適で
    あるので、最初にAliceが取るカードを決めるとゲームの最後までに
    双方が取るカードが決まる。
    このとき、もしも最初に最大以外のカードを選んでいたとすると、
    Aliceが最終的に取るカードは「最初に最大を選んだ場合」以下の
    カードのみであるので、最適ではなくなってしまう。
    したがって、最大のカードを取ることが最適
    →数学的帰納法により、上の戦略が最適であることが示された!
    最初に最大以外のカードを取ると、必ず「最初に最
    大を選んだ場合」以下の得点しか獲得できない

    View Slide

  16. 貪欲法で解くことができる問題
    N枚のカードがあります。i枚目のカードにはaiという数が書かれています。
    AliceとBobは、これらのカードを使ってゲームを行います。ゲームではAliceとBobが交互に1枚ずつカードを取っていきます。
    Alice が先にカードを取ります。
    2人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2人とも自分の得点
    を最大化するように最適な戦略を取った時、AliceはBobより何点多く取るか求めてください。
    制約
    Nは1以上100以下の整数
    ai(1≤i≤N) は1以上100以下の整数
    ABC088B - Card Game for Two (diff 93、灰色)
    証明したいこと:上のゲームにおいて各手番のプレイヤーは残っている最も大きい数字を選ぶことが最適である。
    ②カードがk枚のゲームにおいて上が双方最適戦略であると仮定して、カードが(k+1)枚ある場合
    ……
    ……
    カードk枚のゲームについては双方最大のカードを取るのが最適で
    あるので、最初にAliceが取るカードを決めるとゲームの最後までに
    双方が取るカードが決まる。
    このとき、もしも最初に最大以外のカードを選んでいたとすると、
    Aliceが最終的に取るカードは「最初に最大を選んだ場合」以下の
    カードのみであるので、最適ではなくなってしまう。
    したがって、最大のカードを取ることが最適
    →数学的帰納法により、上の戦略が最適であることが示された!
    最初に最大以外のカードを取ると、必ず「最初に最
    大を選んだ場合」以下の得点しか獲得できない

    View Slide

  17. 貪欲法で解くことができる問題
    N枚のカードがあります。i枚目のカードにはaiという数が書かれています。
    AliceとBobは、これらのカードを使ってゲームを行います。ゲームではAliceとBobが交互に1枚ずつカードを取っていきます。
    Alice が先にカードを取ります。
    2人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2人とも自分の得点
    を最大化するように最適な戦略を取った時、AliceはBobより何点多く取るか求めてください。
    制約
    Nは1以上100以下の整数
    ai(1≤i≤N) は1以上100以下の整数
    ABC088B - Card Game for Two (diff 93、灰色)
    証明したいこと:上のゲームにおいて各手番のプレイヤーは残っている最も大きい数字を選ぶことが最適である。
    ②カードがk枚のゲームにおいて上が双方最適戦略であると仮定して、カードが(k+1)枚ある場合
    ……
    ……
    カードk枚のゲームについては双方最大のカードを取るのが最適で
    あるので、最初にAliceが取るカードを決めるとゲームの最後までに
    双方が取るカードが決まる。
    このとき、もしも最初に最大以外のカードを選んでいたとすると、
    Aliceが最終的に取るカードは「最初に最大を選んだ場合」以下の
    カードのみであるので、最適ではなくなってしまう。
    したがって、最大のカードを取ることが最適
    →数学的帰納法により、上の戦略が最適であることが示された!
    最初に最大以外のカードを取ると、必ず「最初に最
    大を選んだ場合」以下の得点しか獲得できない

    View Slide

  18. 貪欲法まとめ
    ◼ ある「最適な戦略」が存在し、その戦略に従って選択を繰り返すことによって最適解が得られ
    る問題
    ↔動的計画法(DP):複数の小問題の解を保持しておいて、最適な解を選択する
    ◼ 解法が直感的であることが多い一方、正当性を証明することは骨が折れる事が多い

    View Slide

  19. 貪欲法まとめ
    ◼ ある「最適な戦略」が存在し、その戦略に従って選択を繰り返すことによって最適解が得られ
    る問題
    ↔動的計画法(DP):複数の小問題の解を保持しておいて、最適な解を選択する
    ◼ 解法が直感的であることが多い一方、正当性を証明することは骨が折れる事が多い
    貪欲法の正当性の証明を機械的にできるようにして、正当/不当であることを高速に
    判別したい
    マトロイド

    View Slide

  20. マトロイドの定義
    有限集合Mとその部分集合の集合Iが、以下の条件を満たすとき、(M, I)をマトロイドという。
    (A1) 空集合ϕについて、ϕ∈I
    (A2) Y∈Iで、X⊂Yならば、X∈I
    (A3) X, Y∈Iで、|X| > |Y|ならば、Xには含まるがYには含まれない e∈Mが存在して、Y∪{e}∈I(増加公理)
    また、Iに含まれる集合は「独立」であるという。(|X|とは、Xの要素数を表す)
    マトロイド(定義)
    1 2 3
    M={1,2,3}
    I={{}=φ, {1}, {2}, {1, 2}}

    View Slide

  21. マトロイドの定義
    有限集合Mとその部分集合の集合Iが、以下の条件を満たすとき、(M, I)をマトロイドという。
    (A1) 空集合ϕについて、ϕ∈I
    (A2) Y∈Iで、X⊂Yならば、X∈I
    (A3) X, Y∈Iで、|X| > |Y|ならば、Xには含まるがYには含まれない e∈Mが存在して、Y∪{e}∈I(増加公理)
    また、Iに含まれる集合は「独立」であるという。(|X|とは、Xの要素数を表す)
    マトロイド(定義)
    1 2 3
    M={1,2,3}
    I={{}=φ, {1}, {2}, {1, 2}}
    (A1)φ∈Iなので、条件を満たす

    View Slide

  22. マトロイドの定義
    有限集合Mとその部分集合の集合Iが、以下の条件を満たすとき、(M, I)をマトロイドという。
    (A1) 空集合ϕについて、ϕ∈I
    (A2) Y∈Iで、X⊂Yならば、X∈I
    (A3) X, Y∈Iで、|X| > |Y|ならば、Xには含まるがYには含まれない e∈Mが存在して、Y∪{e}∈I(増加公理)
    また、Iに含まれる集合は「独立」であるという。(|X|とは、Xの要素数を表す)
    マトロイド(定義)
    1 2 3
    M={1,2,3}
    I={{}=φ, {1}, {2}, {1, 2}}
    (A1)φ∈Iなので、条件を満たす
    (A2)Y∈Iとなる集合について、自身を除
    く部分集合を列挙すると、
    ◼ {}→(なし)
    ◼ {1}→{}
    ◼ {2}→{}
    ◼ {1, 2}→{}, {1}, {2}, {1, 2}
    であり、これらは全てIに含まれる

    View Slide

  23. マトロイドの定義
    有限集合Mとその部分集合の集合Iが、以下の条件を満たすとき、(M, I)をマトロイドという。
    (A1) 空集合ϕについて、ϕ∈I
    (A2) Y∈Iで、X⊂Yならば、X∈I
    (A3) X, Y∈Iで、|X| > |Y|ならば、Xには含まるがYには含まれない e∈Mが存在して、Y∪{e}∈I(増加公理)
    また、Iに含まれる集合は「独立」であるという。(|X|とは、Xの要素数を表す)
    マトロイド(定義)
    1 2 3
    M={1,2,3}
    I={{}=φ, {1}, {2}, {1, 2}}
    (A1)φ∈Iなので、条件を満たす
    (A2)Y∈Iとなる集合について、自身を除
    く部分集合を列挙すると、
    ◼ {}→(なし)
    ◼ {1}→{}
    ◼ {2}→{}
    ◼ {1, 2}→{}, {1}, {2}
    であり、これらは全てIに含まれる
    (A3)
    例えば、X={1, 2}, Y={1}について、
    e=2と取るとY∪{e}={1, 2}∈Iである
    他の組についても同様

    View Slide

  24. マトロイドの「お気持ち」
    有限集合Mとその部分集合の集合Iが、以下の条件を満たすとき、(M, I)をマトロイドという。
    (A1) 空集合ϕについて、ϕ∈I
    (A2) Y∈Iで、X⊂Yならば、X∈I
    (A3) X, Y∈Iで、|X| > |Y|ならば、Xには含まるがYには含まれない e∈Mが存在して、Y∪{e}∈I(増加公理)
    また、Iに含まれる集合は「独立」であるという。(|X|とは、Xの要素数を表す)
    マトロイド(定義)
    Mを集合、Iを「Mからいくつか選ぶ方法であって、ある条件を満たす取り出し方の集
    合」とする。
    (A1)→「空集合は条件を満たしている」
    (A2)→「ある集合が条件を満たす」ならば「その部分集合も条件を満たしている」
    (A3)→抽象的なので、後でもう一度戻ってきます

    View Slide

  25. マトロイド上の最大独立集合問題
    マトロイド(M, I)に重みw: M→ℝ+
    を付け加えたものを重み付きマトロイド(M, I, w)とする。こ
    のとき、以下の問題を最大独立集合問題と言う
    maximize σ𝑒∈𝑋
    𝑤(𝑒) subject to 𝑋 ∈ 𝐼
    マトロイド上の最大独立集合問題
    1 2 3
    重み付きマトロイド
    w(重み) 3 2 7
    最大独立集合問題
    独立集合Xで要素の重みの総和が最大となる
    ものについてその最大値を求めよ。
    左の例では、各独立集合の重みの総和は
    {}→0
    {1}→3
    {2}→2
    {1, 2}→5
    なので、答えは5

    View Slide

  26. マトロイド上の最大独立集合問題に対する貪欲アルゴリズム
    重み付きマトロイド(M, I, w)上の最大独立集合問題について、以下の貪欲アルゴリズムを考
    える。
    1. e∈Mをw(e)の大きい順にソートして、その順番を{e1, e2, …, en}とする
    2. 集合XをX=φで初期化する
    3. i = 1, 2, …, nについて、以下を繰り返し
    • X∪{ei}∈Iならば、X←X∪{ei}と更新する
    • X∪{ei}∉Iならば何もしない
    4. Xの各要素について重みの総和を取ったものを出力する
    貪欲アルゴリズム
    1 2 3
    w 3 2 7
    1. w(e)の大きい順にソート→{3,1,2}
    2. X={}

    View Slide

  27. マトロイド上の最大独立集合問題に対する貪欲アルゴリズム
    重み付きマトロイド(M, I, w)上の最大独立集合問題について、以下の貪欲アルゴリズムを考
    える。
    1. e∈Mをw(e)の大きい順にソートして、その順番を{e1, e2, …, en}とする
    2. 集合XをX=φで初期化する
    3. i = 1, 2, …, nについて、以下を繰り返し
    • X∪{ei}∈Iならば、X←X∪{ei}と更新する
    • X∪{ei}∉Iならば何もしない
    4. Xの各要素について重みの総和を取ったものを出力する
    貪欲アルゴリズム
    1 2 3
    w 3 2 7
    1. w(e)の大きい順にソート→{3,1,2}
    2. X={}
    3. X∪{3}はIに含まれないので、X={}

    View Slide

  28. マトロイド上の最大独立集合問題に対する貪欲アルゴリズム
    重み付きマトロイド(M, I, w)上の最大独立集合問題について、以下の貪欲アルゴリズムを考
    える。
    1. e∈Mをw(e)の大きい順にソートして、その順番を{e1, e2, …, en}とする
    2. 集合XをX=φで初期化する
    3. i = 1, 2, …, nについて、以下を繰り返し
    • X∪{ei}∈Iならば、X←X∪{ei}と更新する
    • X∪{ei}∉Iならば何もしない
    4. Xの各要素について重みの総和を取ったものを出力する
    貪欲アルゴリズム
    1 2 3
    w 3 2 7
    1. w(e)の大きい順にソート→{3,1,2}
    2. X={}
    3. X∪{1}はIに含まれるので、X={1}

    View Slide

  29. マトロイド上の最大独立集合問題に対する貪欲アルゴリズム
    重み付きマトロイド(M, I, w)上の最大独立集合問題について、以下の貪欲アルゴリズムを考
    える。
    1. e∈Mをw(e)の大きい順にソートして、その順番を{e1, e2, …, en}とする
    2. 集合XをX=φで初期化する
    3. i = 1, 2, …, nについて、以下を繰り返し
    • X∪{ei}∈Iならば、X←X∪{ei}と更新する
    • X∪{ei}∉Iならば何もしない
    4. Xの各要素について重みの総和を取ったものを出力する
    貪欲アルゴリズム
    1 2 3
    w 3 2 7
    1. w(e)の大きい順にソート→{3,1,2}
    2. X={1}
    3. X∪{2}はIに含まれるので、X={1,2}

    View Slide

  30. マトロイド上の最大独立集合問題に対する貪欲アルゴリズム
    重み付きマトロイド(M, I, w)上の最大独立集合問題について、以下の貪欲アルゴリズムを考
    える。
    1. e∈Mをw(e)の大きい順にソートして、その順番を{e1, e2, …, en}とする
    2. 集合XをX=φで初期化する
    3. i = 1, 2, …, nについて、以下を繰り返し
    • X∪{ei}∈Iならば、X←X∪{ei}と更新する
    • X∪{ei}∉Iならば何もしない
    4. Xの各要素について重みの総和を取ったものを出力する
    貪欲アルゴリズム
    1 2 3
    w 3 2 7
    1. w(e)の大きい順にソート→{3,1,2}
    2. X={1}
    3. X∪{2}はIに含まれるので、X={1,2}
    4. X={1,2}について重みの総和は5なので、5を出
    力する

    View Slide

  31. マトロイド上の最大独立集合問題に対する貪欲アルゴリズム
    重み付きマトロイド(M, I, w)上の最大独立集合問題について、以下の貪欲アルゴリズムを考
    える。
    1. e∈Mをw(e)の大きい順にソートして、その順番を{e1, e2, …, en}とする
    2. 集合XをX=φで初期化する
    3. i = 1, 2, …, nについて、以下を繰り返し
    • X∪{ei}∈Iならば、X←X∪{ei}と更新する
    • X∪{ei}∉Iならば何もしない
    4. Xの各要素について重みの総和を取ったものを出力する
    貪欲アルゴリズム
    上の貪欲アルゴリズムによって最大独立集合問題の最適解が得られる
    貪欲アルゴリズムの最適性(定理)
    1 2 3
    w 3 2 7
    1. w(e)の大きい順にソート→{3,1,2}
    2. X={1}
    3. X∪{2}はIに含まれるので、X={1,2}
    4. X={1,2}について重みの総和は5なので、5を出
    力する

    View Slide

  32. 貪欲アルゴリズムの最適性の証明
    貪欲アルゴリズムによって最大独立集合問題の最適解が得られる
    貪欲アルゴリズムの最適性(定理)
    マトロイド(M, I)についてX∈Iであって∀e∈M\XについてX∪{e}∉Iとなるものを基という
    マトロイドの基(定義)
    マトロイド(M, I)についてr: 2𝑀 →ℕをr(X)=max{|Y|| Y⊆X, Y∈I}とする。
    マトロイドの階数(ランク)関数(定義)
    →マトロイド上の極大な独立集合
    →Xの部分集合であるような独立集合について、その要素数の最大値

    View Slide

  33. 貪欲アルゴリズムの最適性の証明
    貪欲アルゴリズムによって最大独立集合問題の最適解が得られる
    貪欲アルゴリズムの最適性(定理)
    貪欲アルゴリズムの出力をB、最適解をB*とする。
    M={e1,e2,…,en}は重みの降順でソートされているものとして、Bi, Bi*を以下で定める。
    • Bi = B∩{e1,e2,…,ei}
    • Bi* = B∩{e1,e2,…,ei}
    このとき、ri=r({e1,e2,…,ei})として、①|Bi*|≦ri、②|Bi|=ri、すなわち|Bi*|≦|Bi|
    貪欲アルゴリズムの出力と最適解の要素数(補題)

    View Slide

  34. 貪欲アルゴリズムの最適性の証明
    貪欲アルゴリズムによって最大独立集合問題の最適解が得られる
    貪欲アルゴリズムの最適性(定理)
    貪欲アルゴリズムの出力をB、最適解をB*とする。
    M={e1,e2,…,en}は重みの降順でソートされているものとして、Bi, Bi*を以下で定める。
    • Bi = B∩{e1,e2,…,ei}
    • Bi* = B∩{e1,e2,…,ei}
    このとき、ri=r({e1,e2,…,ei})として、①|Bi*|≦ri、②|Bi|=ri、すなわち|Bi*|≦|Bi|
    貪欲アルゴリズムの出力と最適解の要素数(補題)
    ①の証明
    Bi*はB*∈Iの部分集合であるので独立集合である。
    階数関数の定義より、riはY⊆{e1,e2,…,ei}であるような独立集合の内極大であるものの要
    素数であるが、Bi*はそのような集合の一つであるので|Bi*|≦ri ■

    View Slide

  35. 貪欲アルゴリズムの最適性の証明
    貪欲アルゴリズムによって最大独立集合問題の最適解が得られる
    貪欲アルゴリズムの最適性(定理)
    貪欲アルゴリズムの出力をB、最適解をB*とする。
    M={e1,e2,…,en}は重みの降順でソートされているものとして、Bi, Bi*を以下で定める。
    • Bi = B∩{e1,e2,…,ei}
    • Bi* = B∩{e1,e2,…,ei}
    このとき、ri=r({e1,e2,…,ei})として、①|Bi*|≦ri、②|Bi|=ri、すなわち|Bi*|≦|Bi|
    貪欲アルゴリズムの出力と最適解の要素数(補題)
    ②の証明
    Biは作り方から明らかに独立集合である。
    ここで、もしej∈{e1,e2,…,ei}\Biであって、Bi∪{ej}∈Iであったとすると、j番目まで見たとき
    にその部分集合であるBj∪{ej}も独立集合であるはずなので、選択されていないのは矛盾。
    Biに含まれない全ての要素についてそれを加えたものは独立集合でない、ということは
    {e1,e2,…,ei}の部分集合に|X|>|Bi|となるような独立集合は存在しない。(存在するなら
    マトロイドの定義(A3)に違反)したがって|Bi|=ri ■
    以上より、|Bi*|≦|Bi|(i=1,2,…,n)■

    View Slide

  36. 貪欲アルゴリズムの最適性の証明
    貪欲アルゴリズムによって最大独立集合問題の最適解が得られる
    貪欲アルゴリズムの最適性(定理)
    B0=B0*=φ、w(e{n+1})=0とすると、

    𝑒∈𝐵
    𝑤 𝑒 = ෍
    𝑖=1
    𝑛
    𝐵𝑖
    − 𝐵𝑖−1
    𝑤(𝑒𝑖
    )
    = ෍
    𝑖=1
    𝑛
    |𝐵𝑖
    |(𝑤 𝑒𝑖
    − 𝑤(𝑒𝑖+1
    ))
    ≧ ෍
    𝑖=1
    𝑛
    |𝐵𝑖
    ∗|(𝑤 𝑒𝑖
    − 𝑤(𝑒𝑖+1
    ))
    = σ𝑖=1
    𝑛 𝐵𝑖
    − 𝐵𝑖−1
    𝑤(𝑒𝑖
    ) = σ𝑒∈𝐵∗
    𝑤(𝑒) ■

    View Slide

  37. マトロイド上の最大独立集合問題に対する貪欲アルゴリズム
    重み付きマトロイド(M, I, w)上の最大独立集合問題について、以下の貪欲アルゴリズムを考
    える。
    1. e∈Mをw(e)の大きい順にソートして、その順番を{e1, e2, …, en}とする
    2. 集合XをX=φで初期化する
    3. i = 1, 2, …, nについて、以下を繰り返し
    • X∪{ei}∈Iならば、X←X∪{ei}と更新する
    • X∪{ei}∉Iならば何もしない
    4. Xの各要素について重みの総和を取ったものを出力する
    貪欲アルゴリズム
    上の貪欲アルゴリズムによって最大独立集合問題の最適解が得られる
    貪欲アルゴリズムの最適性(定理)
    1 2 3
    w 3 2 7
    1. w(e)の大きい順にソート→{3,1,2}
    2. X={1}
    3. X∪{2}はIに含まれるので、X={1,2}
    4. X={1,2}について重みの総和は5なので、5を出
    力する

    View Slide

  38. マトロイドの定義(A3のお気持ち)
    有限集合Mとその部分集合の集合Iが、以下の条件を満たすとき、(M, I)をマトロイドという。
    (A1) 空集合ϕについて、ϕ∈I
    (A2) Y∈Iで、X⊂Yならば、X∈I
    (A3) X, Y∈Iで、|X| > |Y|ならば、Xには含まるがYには含まれない e∈Mが存在して、Y∪{e}∈I(増加公理)
    また、Iに含まれる集合は「独立」であるという。(|X|とは、Xの要素数を表す)
    マトロイド(定義)
    M={1,2,3}
    I={{}, {1}, {2}, {3}, {1, 2}}
    (A3)の条件を満たさない時、貪欲アルゴ
    リズムによって作られる独立集合が極大
    となる保証がない
    →(A3)の条件があることによって、
    貪欲によってどんな手順になっても最終
    的に必ず極大な独立集合が得られるこ
    とが強い!
    1 2 3
    w 4 3 5
    貪欲アルゴリズムでは{3}が得られる
    が、これは極大でない

    View Slide

  39. マトロイドまとめ
    有限集合Mとその部分集合の集合Iが、以下の条件を満たすとき、(M, I)をマトロイドという。
    (A1) 空集合ϕについて、ϕ∈I
    (A2) Y∈Iで、X⊂Yならば、X∈I
    (A3) X, Y∈Iで、|X| > |Y|ならば、Xには含まるがYには含まれない e∈Mが存在して、Y∪{e}∈I(増加公理)
    また、Iに含まれる集合は「独立」であるという。(|X|とは、Xの要素数を表す)
    マトロイド(定義)
    M={1,2,3}
    I={{}, {1}, {2}, {3}, {1, 2}}
    (A1)空集合は条件を満たす
    (A2)ある集合が条件を満たすなら、部
    分集合も条件を満たす
    (A3)貪欲アルゴリズムによって極大な部
    分集合が取れる
    1 2 3
    w 4 3 5
    マトロイドであるなら貪欲アルゴリズムによって最大独立集合問題の最適解が得られる
    貪欲アルゴリズムの最適性(定理)

    View Slide

  40. 補足:行列と線形独立/線形従属
    行列のいくつかの列ベクトル Ԧ
    𝑣1
    , Ԧ
    𝑣2
    , …, Ԧ
    𝑣𝑛
    を選んだ時、
    c1× Ԧ
    𝑣1
    + c2× Ԧ
    𝑣2
    +…+ cn× Ԧ
    𝑣𝑛
    を満たすようなc1,c2,…,cnの組がc1=c2=…cn=0に限られる時、 Ԧ
    𝑣1
    , Ԧ
    𝑣2
    , …, Ԧ
    𝑣𝑛
    は線形
    独立であるという。そうでないとき線形従属であるという。
    列ベクトルの線形独立/線形従属

    View Slide

  41. 補足:行列と線形独立/線形従属
    行列のいくつかの列ベクトル Ԧ
    𝑣1
    , Ԧ
    𝑣2
    , …, Ԧ
    𝑣𝑛
    を選んだ時、
    c1× Ԧ
    𝑣1
    + c2× Ԧ
    𝑣2
    +…+ cn× Ԧ
    𝑣𝑛
    を満たすようなc1,c2,…,cnの組がc1=c2=…cn=0に限られる時、 Ԧ
    𝑣1
    , Ԧ
    𝑣2
    , …, Ԧ
    𝑣𝑛
    は線形
    独立であるという。そうでないとき線形従属であるという。
    列ベクトルの線形独立/線形従属
    1 1 2
    0 1 2

    ② ③



    View Slide

  42. 補足:行列と線形独立/線形従属
    行列のいくつかの列ベクトル Ԧ
    𝑣1
    , Ԧ
    𝑣2
    , …, Ԧ
    𝑣𝑛
    を選んだ時、
    c1× Ԧ
    𝑣1
    + c2× Ԧ
    𝑣2
    +…+ cn× Ԧ
    𝑣𝑛
    を満たすようなc1,c2,…,cnの組がc1=c2=…cn=0に限られる時、 Ԧ
    𝑣1
    , Ԧ
    𝑣2
    , …, Ԧ
    𝑣𝑛
    は線形
    独立であるという。そうでないとき線形従属であるという。
    列ベクトルの線形独立/線形従属
    1 1 2
    0 1 2

    ② ③

    ①を選んだ時
    ・c1×1=0
    ・c1×0=0
    となるのはc1=0のときのみ
    →線形独立

    View Slide

  43. 補足:行列と線形独立/線形従属
    行列のいくつかの列ベクトル Ԧ
    𝑣1
    , Ԧ
    𝑣2
    , …, Ԧ
    𝑣𝑛
    を選んだ時、
    c1× Ԧ
    𝑣1
    + c2× Ԧ
    𝑣2
    +…+ cn× Ԧ
    𝑣𝑛
    を満たすようなc1,c2,…,cnの組がc1=c2=…cn=0に限られる時、 Ԧ
    𝑣1
    , Ԧ
    𝑣2
    , …, Ԧ
    𝑣𝑛
    は線形
    独立であるという。そうでないとき線形従属であるという。
    列ベクトルの線形独立/線形従属
    1 1 2
    0 1 2
    ② ③


    ②を選んだ時
    ・c2×1=0
    ・c2×1=0
    となるのはc2=0のときのみ
    →線形独立
    ※ベクトルを1本選んで線形独立で無いのは、それが零ベクトルであるときのみ

    View Slide

  44. 補足:行列と線形独立/線形従属
    行列のいくつかの列ベクトル Ԧ
    𝑣1
    , Ԧ
    𝑣2
    , …, Ԧ
    𝑣𝑛
    を選んだ時、
    c1× Ԧ
    𝑣1
    + c2× Ԧ
    𝑣2
    +…+ cn× Ԧ
    𝑣𝑛
    を満たすようなc1,c2,…,cnの組がc1=c2=…cn=0に限られる時、 Ԧ
    𝑣1
    , Ԧ
    𝑣2
    , …, Ԧ
    𝑣𝑛
    は線形
    独立であるという。そうでないとき線形従属であるという。
    列ベクトルの線形独立/線形従属
    1 1 2
    0 1 2

    ② ③

    ①と③を選んだ時
    ・c1×1+c3×2=0
    ・c1×0+c3×2=0
    となるのはc1=c3=0のときのみ
    →線形独立

    View Slide

  45. 補足:行列と線形独立/線形従属
    行列のいくつかの列ベクトル Ԧ
    𝑣1
    , Ԧ
    𝑣2
    , …, Ԧ
    𝑣𝑛
    を選んだ時、
    c1× Ԧ
    𝑣1
    + c2× Ԧ
    𝑣2
    +…+ cn× Ԧ
    𝑣𝑛
    を満たすようなc1,c2,…,cnの組がc1=c2=…cn=0に限られる時、 Ԧ
    𝑣1
    , Ԧ
    𝑣2
    , …, Ԧ
    𝑣𝑛
    は線形
    独立であるという。そうでないとき線形従属であるという。
    列ベクトルの線形独立/線形従属
    1 1 2
    0 1 2
    ② ③



    ②と③を選んだ時
    ・c2×1+c3×2=0
    ・c2×1+c3×2=0
    となるのはc1=c3=0か
    c2=-2×c3のとき
    →線形従属

    View Slide

  46. 補足:行列と線形独立/線形従属
    行列のいくつかの列ベクトル Ԧ
    𝑣1
    , Ԧ
    𝑣2
    , …, Ԧ
    𝑣𝑛
    を選んだ時、
    c1× Ԧ
    𝑣1
    + c2× Ԧ
    𝑣2
    +…+ cn× Ԧ
    𝑣𝑛
    を満たすようなc1,c2,…,cnの組がc1=c2=…cn=0に限られる時、 Ԧ
    𝑣1
    , Ԧ
    𝑣2
    , …, Ԧ
    𝑣𝑛
    は線形
    独立であるという。そうでないとき線形従属であるという。
    列ベクトルの線形独立/線形従属
    1 1 2
    0 1 2
    ② ③



    ②と③を選んだ時
    ・c2×1+c3×2=0
    ・c2×1+c3×2=0
    となるのはc2=c3=0か
    c2=-2×c3のとき
    →線形従属
    直感的には「列ベクトルの作る空間」の次元
    の方が、列ベクトルの本数よりも小さい時、
    線形従属となる

    View Slide

  47. 補足:行列と線形独立/線形従属
    行列のいくつかの列ベクトル Ԧ
    𝑣1
    , Ԧ
    𝑣2
    , …, Ԧ
    𝑣𝑛
    を選んだ時、
    c1× Ԧ
    𝑣1
    + c2× Ԧ
    𝑣2
    +…+ cn× Ԧ
    𝑣𝑛
    を満たすようなc1,c2,…,cnの組がc1=c2=…cn=0に限られる時、 Ԧ
    𝑣1
    , Ԧ
    𝑣2
    , …, Ԧ
    𝑣𝑛
    は線形
    独立であるという。そうでないとき線形従属であるという。
    列ベクトルの線形独立/線形従属
    1 1 2
    0 1 2
    ② ③



    {①,②,③}の部分集合のうち、
    選んだ列ベクトルが線形独立となるも
    のの集合は、
    {{}, {①},{②},{③},
    {①,②},{①,③}}の6個
    直感的には「列ベクトルの作る空間」の次元
    の方が、列ベクトルの本数よりも小さい時、
    線形従属となる

    View Slide

  48. ベクトルマトロイド
    行列の列ベクトルの集合をM、Mの部分集合のうち選んだ列ベクトルの組が線形独立となるよう
    な部分集合の集合をIとする。このとき(M,I)はマトロイドである(ベクトルマトロイド)
    ベクトルマトロイド
    M = {①,②,③}
    I = {{}, {①}, {②}, {③}, {①,②}, {①,③}}
    1 1 2
    0 1 2
    ② ③


    ② ③

    View Slide

  49. ベクトルマトロイド
    行列の列ベクトルの集合をM、Mの部分集合のうち選んだ列ベクトルの組が線形独立となるよう
    な部分集合の集合をIとする。このとき(M,I)はマトロイドである(ベクトルマトロイド)
    ベクトルマトロイド
    M = {①,②,③}
    I = {{}, {①}, {②}, {③}, {①,②}, {①,③}}
    1 1 2
    0 1 2
    ② ③

    (A1) 空集合ϕについて、ϕ∈I
    (A2) Y∈Iで、X⊂Yならば、X∈I
    (A3) X, Y∈Iで、|X| > |Y|なら
    ば、Xには含まるがYには含まれない
    e∈Mが存在して、Y∪{e}∈I
    (A1)
    空集合は含まれるのでOK
    (A2)
    例えば、{①,②}の部分集合の{},{①},{②}などは全てIに含
    まれる。他も同様なのでOK
    (A3)
    例えばX={①,②}とY={③}を選ぶと、eとして①を選ぶと
    Y∪{①}={①,③}∈Iとなり条件を満たす。他も同様
    →(M,I)はマトロイド

    ② ③

    View Slide

  50. ベクトルマトロイド
    行列の列ベクトルの集合をM、Mの部分集合のうち選んだ列ベクトルの組が線形独立となるよう
    な部分集合の集合をIとする。このとき(M,I)はマトロイドである(ベクトルマトロイド)
    ベクトルマトロイド
    1 1 2
    0 1 2
    ② ③

    (A1) 空集合ϕについて、ϕ∈I
    (A2) Y∈Iで、X⊂Yならば、X∈I
    (A3) X, Y∈Iで、|X| > |Y|なら
    ば、Xには含まるがYには含まれない
    e∈Mが存在して、Y∪{e}∈I
    証明(概略)
    (A1),(A2)
    線形独立の定義からほぼ明らか
    (A3)
    YよりもXの次元の方が大きいので、YにXの要素を一つづつ追加
    したときに次元が増える要素が必ず1つは存在する。この要素がe
    である。
    maspyさんの記事にもうちょっと形式的に書いてあります
    マトロイドのお勉強(JSC2019予選 [E] Card Collector)

    ② ③

    View Slide

  51. 問題演習①:最小全域木
    重み付き単純連結無向グラフ G=(V,E) に対する最小全域木の辺の重みの総和を計算するプログラムを作成してください。
    ただし、最小全域木とは与えられたグラフの部分グラフであって連結であるもののうち、辺のコストの総和が最小となるもので
    す。
    制約
    • 1 ≤ |V| ≤ 10,000
    • 0 ≤ |E| ≤ 100,000
    • 0 ≤ wi ≤ 10,000
    • 与えられるグラフは単純かつ連結である。
    Minimum Spanning Tree(AOJ GRL_2_A、一部改変)
    1
    5
    3
    2
    4
    6
    9
    1
    4
    3
    6
    8
    5
    7
    1
    5
    3
    2
    4
    6
    9
    1
    4
    3
    5

    View Slide

  52. 問題演習①:最小全域木
    グラフの辺の集合をM、辺→コストの写像をwとする。また、Mの部分集合の集合Iを
    I = {ei| ei∈M, eiからなる部分グラフが閉路を持たない}と定める。
    上で定めた(M,I,w)は重み付きマトロイドである。(閉路マトロイド)
    閉路マトロイド

    View Slide

  53. 問題演習①:最小全域木
    グラフの辺の集合をM、辺→コストの写像をwとする。また、Mの部分集合の集合Iを
    I = {ei| ei∈M, eiからなる部分グラフが閉路を持たない}と定める。
    上で定めた(M,I,w)は重み付きマトロイドである。(閉路マトロイド)
    閉路マトロイド
    1
    5
    3
    2
    4
    6
    9
    1
    4
    3
    6
    8
    5
    7



    ④ ⑤



    M = {①,②,③,④,⑤,⑥,⑦,⑧}
    I = {{},{①,④},{②,⑥,⑦},{①,②,③,⑥,⑧},…}
    ({②,③,④}などはIに含まれない)

    View Slide

  54. 問題演習①:最小全域木
    グラフの辺の集合をM、辺→コストの写像をwとする。また、Mの部分集合の集合Iを
    I = {ei| ei∈M, eiからなる部分グラフが閉路を持たない}と定める。
    上で定めた(M,I,w)は重み付きマトロイドである。(閉路マトロイド)
    閉路マトロイド
    1
    5
    3
    2
    4
    6
    9
    1
    4
    3
    6
    8
    5
    7



    ④ ⑤



    1 1 0 1 0 0 0 0
    0 1 1 0 0 0 0 0
    0 0 1 1 1 0 1 1
    0 0 0 0 0 1 1 0
    0 0 0 0 0 0 0 1
    1 0 0 0 1 1 0 0
    頂点
    1
    2
    3
    4
    5
    6
    ① ② ③ ④ ⑤ ⑥ ⑦ ⑧
    各辺が「どの頂点からどの頂点までを結んでいるか」をグラフ
    で表す。(接続行列)

    View Slide

  55. 問題演習①:最小全域木
    グラフの辺の集合をM、辺→コストの写像をwとする。また、Mの部分集合の集合Iを
    I = {ei| ei∈M, eiからなる部分グラフが閉路を持たない}と定める。
    上で定めた(M,I,w)は重み付きマトロイドである。(閉路マトロイド)
    閉路マトロイド
    1
    5
    3
    2
    4
    6
    9
    1
    4
    3
    6
    8
    5
    7



    ④ ⑤



    1 1 0 1 0 0 0 0
    0 1 1 0 0 0 0 0
    0 0 1 1 1 0 1 1
    0 0 0 0 0 1 1 0
    0 0 0 0 0 0 0 1
    1 0 0 0 1 1 0 0
    頂点
    1
    2
    3
    4
    5
    6
    ① ② ③ ④ ⑤ ⑥ ⑦ ⑧

    閉路がある時:閉路の列ベクトルを(mod2の足し算で)
    足し合わせると零ベクトルになる→線形独立でない

    View Slide

  56. 問題演習①:最小全域木
    グラフの辺の集合をM、辺→コストの写像をwとする。また、Mの部分集合の集合Iを
    I = {ei| ei∈M, eiからなる部分グラフが閉路を持たない}と定める。
    上で定めた(M,I,w)は重み付きマトロイドである。(閉路マトロイド)
    閉路マトロイド
    1
    5
    3
    2
    4
    6
    9
    1
    4
    3
    6
    8
    5
    7



    ④ ⑤



    1 1 0 1 0 0 0 0
    0 1 1 0 0 0 0 0
    0 0 1 1 1 0 1 1
    0 0 0 0 0 1 1 0
    0 0 0 0 0 0 0 1
    1 0 0 0 1 1 0 0
    頂点
    1
    2
    3
    4
    5
    6
    ① ② ③ ④ ⑤ ⑥ ⑦ ⑧

    閉路がある時:閉路の列ベクトルを(mod2の足し算で)
    足し合わせると零ベクトルになる→線形独立でない
    逆に閉路がないならどの列ベクトルの組のmod2での足し
    合わせも0でないので、これはマトロイド

    View Slide

  57. 問題演習①:最小全域木
    重み付き単純連結無向グラフ G=(V,E) に対する最小全域木の辺の重みの総和を計算するプログラムを作成してください。
    ただし、最小全域木とは与えられたグラフの部分グラフであって連結であるもののうち、辺のコストの総和が最小となるもので
    す。
    制約
    • 1 ≤ |V| ≤ 10,000
    • 0 ≤ |E| ≤ 100,000
    • 0 ≤ wi ≤ 10,000
    • 与えられるグラフは単純かつ連結である。
    Minimum Spanning Tree(AOJ GRL_2_A、一部改変)
    グラフの辺の集合をM、辺→コストの写像をwとする。また、Mの部分集合の集合Iを
    I = {ei| ei∈M, eiからなる部分グラフが閉路を持たない}と定める。
    上で定めた(M,I,w)は重み付きマトロイドである。(閉路マトロイド)
    閉路マトロイド
    =
    最小全域木
    問題
    閉路マトロイド上での
    辺コストの最小化問題
    辺のコストを-1倍して定数分ずらせば、最大独立集合問題と同じ!

    View Slide

  58. 問題演習①:最小全域木
    重み付き単純連結無向グラフ G=(V,E) に対する最小全域木の辺の重みの総和を計算するプログラムを作成してください。
    ただし、最小全域木とは与えられたグラフの部分グラフであって連結であるもののうち、辺のコストの総和が最小となるもので
    す。
    制約
    • 1 ≤ |V| ≤ 10,000
    • 0 ≤ |E| ≤ 100,000
    • 0 ≤ wi ≤ 10,000
    • 与えられるグラフは単純かつ連結である。
    Minimum Spanning Tree(AOJ GRL_2_A、一部改変)
    以下の貪欲アルゴリズムによって最適解を得ることが可能。
    グラフの辺を、コストの小さい順にソートして、その順番を{e1, e2, …, en}とする
    1. 集合XをX=φで初期化する
    2. i = 1, 2, …, nについて、以下を繰り返し
    • Xにeiを追加してもグラフが閉路を持たない(=eiがuとvを結んでいる時、Xの他の辺
    によってuとvが連結でない)ならば、X←X∪{ei}と更新する
    • そうでないならば何もしない
    3. Xの各要素について重みの総和を取ったものを出力する
    貪欲アルゴリズム

    View Slide

  59. 問題演習①:最小全域木
    重み付き単純連結無向グラフ G=(V,E) に対する最小全域木の辺の重みの総和を計算するプログラムを作成してください。
    ただし、最小全域木とは与えられたグラフの部分グラフであって連結であるもののうち、辺のコストの総和が最小となるもので
    す。
    制約
    • 1 ≤ |V| ≤ 10,000
    • 0 ≤ |E| ≤ 100,000
    • 0 ≤ wi ≤ 10,000
    • 与えられるグラフは単純かつ連結である。
    Minimum Spanning Tree(AOJ GRL_2_A、一部改変)
    以下の貪欲アルゴリズムによって最適解を得ることが可能。
    グラフの辺を、コストの小さい順にソートして、その順番を{e1, e2, …, en}とする
    1. 集合XをX=φで初期化する
    2. i = 1, 2, …, nについて、以下を繰り返し
    • Xにeiを追加してもグラフが閉路を持たない(=eiがuとvを結んでいる時、Xの他の辺
    によってuとvが連結でない)ならば、X←X∪{ei}と更新する
    • そうでないならば何もしない
    3. Xの各要素について重みの総和を取ったものを出力する
    貪欲アルゴリズム
    →Kruskal法

    View Slide

  60. 問題演習②:Spices
    スパイス屋には、スパイス1、スパイス2、… 、スパイス (2^N)-1の(2^N)−1種類のスパイスがそれぞれ1個ずつ売られてい
    ます。i=1,2,…,(2^N)−1について、スパイスiの値段はci円です。 高橋君はそれらを好きなだけ買うことができます。
    高橋君は帰宅後、買ったスパイスのうち1つ以上を選び、それらを組み合わせてカレーを作る予定です。高橋君がスパイス
    A1、スパイスA2、…、スパイスAkのk個のスパイスを組み合わせると、完成するカレーの辛さはA1⊕A2⊕…⊕Akになります。
    ここで、⊕はビットごとの排他的論理和を表します。
    高橋君は、作るカレーの辛さを帰宅後の気分で決めたいので、とりあえず1以上2^N−1以下の任意の整数の辛さのカレー
    を作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してくださ
    い。
    制約
    2≤N≤16
    1≤ci≤10^9
    Spices(ABC236-F、diff 1943)
    スパイス2
    10円
    スパイス1
    2円
    スパイス3
    8円
    スパイス4
    3円
    スパイス5
    4円
    スパイス6
    7円
    スパイス7
    6円

    View Slide

  61. 問題演習②:Spices
    スパイス屋には、スパイス1、スパイス2、… 、スパイス (2^N)-1の(2^N)−1種類のスパイスがそれぞれ1個ずつ売られてい
    ます。i=1,2,…,(2^N)−1について、スパイスiの値段はci円です。 高橋君はそれらを好きなだけ買うことができます。
    高橋君は帰宅後、買ったスパイスのうち1つ以上を選び、それらを組み合わせてカレーを作る予定です。高橋君がスパイス
    A1、スパイスA2、…、スパイスAkのk個のスパイスを組み合わせると、完成するカレーの辛さはA1⊕A2⊕…⊕Akになります。
    ここで、⊕はビットごとの排他的論理和を表します。
    高橋君は、作るカレーの辛さを帰宅後の気分で決めたいので、とりあえず1以上2^N−1以下の任意の整数の辛さのカレー
    を作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してくださ
    い。
    制約
    2≤N≤16
    1≤ci≤10^9
    Spices(ABC236-F、diff 1943)
    スパイス2
    10円
    スパイス1
    2円
    スパイス3
    8円
    スパイス4
    3円
    スパイス5
    4円
    スパイス6
    7円
    スパイス7
    6円
    スパイス2,5を選ぶ
    2、5、および2⊕5=7の辛さのカレーが作れる→全ての辛さのカレーが作れないのでNG

    View Slide

  62. 問題演習②:Spices
    スパイス屋には、スパイス1、スパイス2、… 、スパイス (2^N)-1の(2^N)−1種類のスパイスがそれぞれ1個ずつ売られてい
    ます。i=1,2,…,(2^N)−1について、スパイスiの値段はci円です。 高橋君はそれらを好きなだけ買うことができます。
    高橋君は帰宅後、買ったスパイスのうち1つ以上を選び、それらを組み合わせてカレーを作る予定です。高橋君がスパイス
    A1、スパイスA2、…、スパイスAkのk個のスパイスを組み合わせると、完成するカレーの辛さはA1⊕A2⊕…⊕Akになります。
    ここで、⊕はビットごとの排他的論理和を表します。
    高橋君は、作るカレーの辛さを帰宅後の気分で決めたいので、とりあえず1以上2^N−1以下の任意の整数の辛さのカレー
    を作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してくださ
    い。
    制約
    2≤N≤16
    1≤ci≤10^9
    Spices(ABC236-F、diff 1943)
    スパイス2
    10円
    スパイス1
    2円
    スパイス3
    8円
    スパイス4
    3円
    スパイス5
    4円
    スパイス6
    7円
    スパイス7
    6円
    スパイス2,5,6を選ぶ
    以下のようにして全ての辛さのカレーが可能
    1=2⊕5⊕6、2=2、3=5⊕6、4=2⊕6、5=5、6=6、7=2⊕5
    このときの値段の合計は10+4+7=21円

    View Slide

  63. 問題演習②:Spices
    スパイス屋には、スパイス1、スパイス2、… 、スパイス (2^N)-1の(2^N)−1種類のスパイスがそれぞれ1個ずつ売られてい
    ます。i=1,2,…,(2^N)−1について、スパイスiの値段はci円です。 高橋君はそれらを好きなだけ買うことができます。
    高橋君は帰宅後、買ったスパイスのうち1つ以上を選び、それらを組み合わせてカレーを作る予定です。高橋君がスパイス
    A1、スパイスA2、…、スパイスAkのk個のスパイスを組み合わせると、完成するカレーの辛さはA1⊕A2⊕…⊕Akになります。
    ここで、⊕はビットごとの排他的論理和を表します。
    高橋君は、作るカレーの辛さを帰宅後の気分で決めたいので、とりあえず1以上2^N−1以下の任意の整数の辛さのカレー
    を作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してくださ
    い。
    制約
    2≤N≤16
    1≤ci≤10^9
    Spices(ABC236-F、diff 1943)
    スパイス2
    10円
    スパイス1
    2円
    スパイス3
    8円
    スパイス4
    3円
    スパイス5
    4円
    スパイス6
    7円
    スパイス7
    6円
    スパイス1,4,5を選ぶ
    作れる辛さは1、4、5のみ。例えば4⊕5=1なので、組み合わせても新しい辛さを作ることができな
    い。
    →適当に3つ選べば良い訳ではなさそう……

    View Slide

  64. 問題演習②:Spices
    スパイス屋には、スパイス1、スパイス2、… 、スパイス (2^N)-1の(2^N)−1種類のスパイスがそれぞれ1個ずつ売られてい
    ます。i=1,2,…,(2^N)−1について、スパイスiの値段はci円です。 高橋君はそれらを好きなだけ買うことができます。
    高橋君は帰宅後、買ったスパイスのうち1つ以上を選び、それらを組み合わせてカレーを作る予定です。高橋君がスパイス
    A1、スパイスA2、…、スパイスAkのk個のスパイスを組み合わせると、完成するカレーの辛さはA1⊕A2⊕…⊕Akになります。
    ここで、⊕はビットごとの排他的論理和を表します。
    高橋君は、作るカレーの辛さを帰宅後の気分で決めたいので、とりあえず1以上2^N−1以下の任意の整数の辛さのカレー
    を作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してくださ
    い。
    制約
    2≤N≤16
    1≤ci≤10^9
    Spices(ABC236-F、diff 1943)
    1 0 1 0 1 0 1
    0 1 1 0 0 1 1
    0 0 0 1 1 1 1
    1
    2
    3
    ① ② ③ ④ ⑤ ⑥ ⑦
    ビット
    スパイス

    View Slide

  65. 問題演習②:Spices
    スパイス屋には、スパイス1、スパイス2、… 、スパイス (2^N)-1の(2^N)−1種類のスパイスがそれぞれ1個ずつ売られてい
    ます。i=1,2,…,(2^N)−1について、スパイスiの値段はci円です。 高橋君はそれらを好きなだけ買うことができます。
    高橋君は帰宅後、買ったスパイスのうち1つ以上を選び、それらを組み合わせてカレーを作る予定です。高橋君がスパイス
    A1、スパイスA2、…、スパイスAkのk個のスパイスを組み合わせると、完成するカレーの辛さはA1⊕A2⊕…⊕Akになります。
    ここで、⊕はビットごとの排他的論理和を表します。
    高橋君は、作るカレーの辛さを帰宅後の気分で決めたいので、とりあえず1以上2^N−1以下の任意の整数の辛さのカレー
    を作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してくださ
    い。
    制約
    2≤N≤16
    1≤ci≤10^9
    Spices(ABC236-F、diff 1943)
    1 0 1 0 1 0 1
    0 1 1 0 0 1 1
    0 0 0 1 1 1 1
    1
    2
    3
    ① ② ③ ④ ⑤ ⑥ ⑦
    ビット
    スパイス
    1⊕4⊕5=0となっている
    ⇒1⊕4=5なので「効率の悪い」選び方になってし
    まう。(組合せで新しい辛さが作れない)

    View Slide

  66. 問題演習②:Spices
    スパイス屋には、スパイス1、スパイス2、… 、スパイス (2^N)-1の(2^N)−1種類のスパイスがそれぞれ1個ずつ売られてい
    ます。i=1,2,…,(2^N)−1について、スパイスiの値段はci円です。 高橋君はそれらを好きなだけ買うことができます。
    高橋君は帰宅後、買ったスパイスのうち1つ以上を選び、それらを組み合わせてカレーを作る予定です。高橋君がスパイス
    A1、スパイスA2、…、スパイスAkのk個のスパイスを組み合わせると、完成するカレーの辛さはA1⊕A2⊕…⊕Akになります。
    ここで、⊕はビットごとの排他的論理和を表します。
    高橋君は、作るカレーの辛さを帰宅後の気分で決めたいので、とりあえず1以上2^N−1以下の任意の整数の辛さのカレー
    を作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してくださ
    い。
    制約
    2≤N≤16
    1≤ci≤10^9
    Spices(ABC236-F、diff 1943)
    1 0 1 0 1 0 1
    0 1 1 0 0 1 1
    0 0 0 1 1 1 1
    1
    2
    3
    ① ② ③ ④ ⑤ ⑥ ⑦
    ビット
    スパイス
    1⊕4⊕5=0となっている
    ⇒1⊕4=5なので「効率の悪い」選び方になってし
    まう。(組合せで新しい辛さが作れない)
    行列のいくつかの列ベクトル Ԧ
    𝑣1
    , Ԧ
    𝑣2
    , …, Ԧ
    𝑣𝑛
    を選んだ時、
    c1× Ԧ
    𝑣1
    + c2× Ԧ
    𝑣2
    +…+ cn× Ԧ
    𝑣𝑛
    を満たすようなc1,c2,…,cnの組がc1=c2=…cn=0に限られる時、 Ԧ
    𝑣1
    , Ԧ
    𝑣2
    ,
    …, Ԧ
    𝑣𝑛
    は線形独立であるという。そうでないとき線形従属であるという。
    列ベクトルの線形独立/線形従属

    View Slide

  67. 問題演習②:Spices
    スパイス屋には、スパイス1、スパイス2、… 、スパイス (2^N)-1の(2^N)−1種類のスパイスがそれぞれ1個ずつ売られてい
    ます。i=1,2,…,(2^N)−1について、スパイスiの値段はci円です。 高橋君はそれらを好きなだけ買うことができます。
    高橋君は帰宅後、買ったスパイスのうち1つ以上を選び、それらを組み合わせてカレーを作る予定です。高橋君がスパイス
    A1、スパイスA2、…、スパイスAkのk個のスパイスを組み合わせると、完成するカレーの辛さはA1⊕A2⊕…⊕Akになります。
    ここで、⊕はビットごとの排他的論理和を表します。
    高橋君は、作るカレーの辛さを帰宅後の気分で決めたいので、とりあえず1以上2^N−1以下の任意の整数の辛さのカレー
    を作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してくださ
    い。
    制約
    2≤N≤16
    1≤ci≤10^9
    Spices(ABC236-F、diff 1943)
    1 0 1 0 1 0 1
    0 1 1 0 0 1 1
    0 0 0 1 1 1 1
    1
    2
    3
    ① ② ③ ④ ⑤ ⑥ ⑦
    ビット
    スパイス
    1⊕4⊕5=0となっている
    ⇒1⊕4=5なので「効率の悪い」選び方になってし
    まう。(組合せで新しい辛さが作れない)
    →ベクトルマトロイド上で、コスト最小となる最大
    独立部分集合を選ぶ問題
    (辺のコストを-1倍して定数分ずらすと最大独立
    部分集合問題そのもの)

    View Slide

  68. 問題演習②:Spices
    スパイス屋には、スパイス1、スパイス2、… 、スパイス (2^N)-1の(2^N)−1種類のスパイスがそれぞれ1個ずつ売られてい
    ます。i=1,2,…,(2^N)−1について、スパイスiの値段はci円です。 高橋君はそれらを好きなだけ買うことができます。
    高橋君は帰宅後、買ったスパイスのうち1つ以上を選び、それらを組み合わせてカレーを作る予定です。高橋君がスパイス
    A1、スパイスA2、…、スパイスAkのk個のスパイスを組み合わせると、完成するカレーの辛さはA1⊕A2⊕…⊕Akになります。
    ここで、⊕はビットごとの排他的論理和を表します。
    高橋君は、作るカレーの辛さを帰宅後の気分で決めたいので、とりあえず1以上2^N−1以下の任意の整数の辛さのカレー
    を作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してくださ
    い。
    制約
    2≤N≤16
    1≤ci≤10^9
    Spices(ABC236-F、diff 1943)
    以下の貪欲アルゴリズムによって最適解を得ることが可能。
    スパイスを、コストの小さい順にソートして、その順番を{e1, e2, …, e{(2^N)-1}}とする
    1. 集合XをX=φで初期化する
    2. i = 1, 2, …, nについて、以下を繰り返し
    • Xに含まれるどのベクトルとも、eiが線形独立ならば、X←X∪{ei}と更新する
    • そうでないならば何もしない
    3. Xの各要素について重みの総和を取ったものを出力する
    貪欲アルゴリズム

    View Slide

  69. 問題演習②:Spices
    スパイス屋には、スパイス1、スパイス2、… 、スパイス (2^N)-1の(2^N)−1種類のスパイスがそれぞれ1個ずつ売られてい
    ます。i=1,2,…,(2^N)−1について、スパイスiの値段はci円です。 高橋君はそれらを好きなだけ買うことができます。
    高橋君は帰宅後、買ったスパイスのうち1つ以上を選び、それらを組み合わせてカレーを作る予定です。高橋君がスパイス
    A1、スパイスA2、…、スパイスAkのk個のスパイスを組み合わせると、完成するカレーの辛さはA1⊕A2⊕…⊕Akになります。
    ここで、⊕はビットごとの排他的論理和を表します。
    高橋君は、作るカレーの辛さを帰宅後の気分で決めたいので、とりあえず1以上2^N−1以下の任意の整数の辛さのカレー
    を作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してくださ
    い。
    制約
    2≤N≤16
    1≤ci≤10^9
    Spices(ABC236-F、diff 1943)
    スパイス2
    10円
    スパイス1
    2円
    スパイス3
    8円
    スパイス4
    3円
    スパイス5
    4円
    スパイス6
    7円
    スパイス7
    6円
    X={}
    1はX内のどの要素とも線形独立なので、含める

    View Slide

  70. 問題演習②:Spices
    スパイス屋には、スパイス1、スパイス2、… 、スパイス (2^N)-1の(2^N)−1種類のスパイスがそれぞれ1個ずつ売られてい
    ます。i=1,2,…,(2^N)−1について、スパイスiの値段はci円です。 高橋君はそれらを好きなだけ買うことができます。
    高橋君は帰宅後、買ったスパイスのうち1つ以上を選び、それらを組み合わせてカレーを作る予定です。高橋君がスパイス
    A1、スパイスA2、…、スパイスAkのk個のスパイスを組み合わせると、完成するカレーの辛さはA1⊕A2⊕…⊕Akになります。
    ここで、⊕はビットごとの排他的論理和を表します。
    高橋君は、作るカレーの辛さを帰宅後の気分で決めたいので、とりあえず1以上2^N−1以下の任意の整数の辛さのカレー
    を作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してくださ
    い。
    制約
    2≤N≤16
    1≤ci≤10^9
    Spices(ABC236-F、diff 1943)
    スパイス2
    10円
    スパイス1
    2円
    スパイス3
    8円
    スパイス4
    3円
    スパイス5
    4円
    スパイス6
    7円
    スパイス7
    6円
    X={1}
    4はX内のどの要素とも線形独立(4⊕1≠0)なので、含める

    View Slide

  71. 問題演習②:Spices
    スパイス屋には、スパイス1、スパイス2、… 、スパイス (2^N)-1の(2^N)−1種類のスパイスがそれぞれ1個ずつ売られてい
    ます。i=1,2,…,(2^N)−1について、スパイスiの値段はci円です。 高橋君はそれらを好きなだけ買うことができます。
    高橋君は帰宅後、買ったスパイスのうち1つ以上を選び、それらを組み合わせてカレーを作る予定です。高橋君がスパイス
    A1、スパイスA2、…、スパイスAkのk個のスパイスを組み合わせると、完成するカレーの辛さはA1⊕A2⊕…⊕Akになります。
    ここで、⊕はビットごとの排他的論理和を表します。
    高橋君は、作るカレーの辛さを帰宅後の気分で決めたいので、とりあえず1以上2^N−1以下の任意の整数の辛さのカレー
    を作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してくださ
    い。
    制約
    2≤N≤16
    1≤ci≤10^9
    Spices(ABC236-F、diff 1943)
    スパイス2
    10円
    スパイス1
    2円
    スパイス3
    8円
    スパイス4
    3円
    スパイス5
    4円
    スパイス6
    7円
    スパイス7
    6円
    X={1,4}
    5はX内の要素と線形独立でない(1⊕4⊕5=0)なので、含めない

    View Slide

  72. 問題演習②:Spices
    スパイス屋には、スパイス1、スパイス2、… 、スパイス (2^N)-1の(2^N)−1種類のスパイスがそれぞれ1個ずつ売られてい
    ます。i=1,2,…,(2^N)−1について、スパイスiの値段はci円です。 高橋君はそれらを好きなだけ買うことができます。
    高橋君は帰宅後、買ったスパイスのうち1つ以上を選び、それらを組み合わせてカレーを作る予定です。高橋君がスパイス
    A1、スパイスA2、…、スパイスAkのk個のスパイスを組み合わせると、完成するカレーの辛さはA1⊕A2⊕…⊕Akになります。
    ここで、⊕はビットごとの排他的論理和を表します。
    高橋君は、作るカレーの辛さを帰宅後の気分で決めたいので、とりあえず1以上2^N−1以下の任意の整数の辛さのカレー
    を作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してくださ
    い。
    制約
    2≤N≤16
    1≤ci≤10^9
    Spices(ABC236-F、diff 1943)
    スパイス2
    10円
    スパイス1
    2円
    スパイス3
    8円
    スパイス4
    3円
    スパイス5
    4円
    スパイス6
    7円
    スパイス7
    6円
    X={1,4}
    7はX内のどの要素とも線形独立なので、含める

    View Slide

  73. 問題演習②:Spices
    スパイス屋には、スパイス1、スパイス2、… 、スパイス (2^N)-1の(2^N)−1種類のスパイスがそれぞれ1個ずつ売られてい
    ます。i=1,2,…,(2^N)−1について、スパイスiの値段はci円です。 高橋君はそれらを好きなだけ買うことができます。
    高橋君は帰宅後、買ったスパイスのうち1つ以上を選び、それらを組み合わせてカレーを作る予定です。高橋君がスパイス
    A1、スパイスA2、…、スパイスAkのk個のスパイスを組み合わせると、完成するカレーの辛さはA1⊕A2⊕…⊕Akになります。
    ここで、⊕はビットごとの排他的論理和を表します。
    高橋君は、作るカレーの辛さを帰宅後の気分で決めたいので、とりあえず1以上2^N−1以下の任意の整数の辛さのカレー
    を作れるように、購入するスパイスの組み合わせを決定します。高橋君が支払う金額としてあり得る最小値を出力してくださ
    い。
    制約
    2≤N≤16
    1≤ci≤10^9
    Spices(ABC236-F、diff 1943)
    スパイス2
    10円
    スパイス1
    2円
    スパイス3
    8円
    スパイス4
    3円
    スパイス5
    4円
    スパイス6
    7円
    スパイス7
    6円
    X={1,4,7}
    3つのスパイスが選ばれたので、これ以上選ばれることは無い。6+2+3=11が答え

    View Slide

  74. まとめ
    ◼ 貪欲法
    ◼ 「そのときに最適」な戦略を取ることで、一番最適な解を得ることができる方法
    ◼ どんな問題にも使えるわけではなく、正当性を示すことは難しい
    ◼ マトロイド
    ◼ 集合と、その部分集合の集合の組であって特定の性質を満たすもの
    ◼ (A1) 空集合ϕについて、ϕ∈I
    ◼ (A2) Y∈Iで、X⊂Yならば、X∈I
    ◼ (A3) X, Y∈Iで、|X| > |Y|ならば、Xには含まるがYには含まれない
    e∈Mが存在して、Y∪{e}∈I
    ◼ 直感的には「貪欲アルゴリズムによって極大な部分集合が取れる」ようなことを
    表している
    ◼ マトロイド上での最大独立部分集合は、貪欲アルゴリズムによって得ることができる
    さらに勉強したい方は……
    ・様々なグラフマトロイド(bicircular matroid,横断マトロイド)
    ・マトロイド交差
    資料:
    離散最適化基礎論(電気通信大学 岡本吉央先生)
    マトロイドの凸構造(けんちょんさん)

    View Slide