0

遺伝的アルゴリズムによるナップサックDPのやり方(これもDP)

14
0
$$$$

遺伝的アルゴリズムによるナップサックDPのやり方(これもDP)

  1. (これがナップサックDP独特の部分)g当たりの平均値を求め近似解$A$を出す。
    2.袋の数$n=1$兆とかの場合もあるが、まず近似解を利用して平均値のより高い2, 3, 4, 5個の組$X$を作る。これは射になる。
    そこから更に、それを2, 3, 4, 5個組み合わせた射を作る。
    これを繰り返し、$100$個程度の元を持つ空間$Y$を作る。途中からMC法で作る。
    3.近似解から、$Y$の元同士で交換し総当たりでより良い値$B$がないか探す。必ず$A≦B$。MC法で$B$を更新し、最終的には総当り。一つずつ射を逆に辿り、最後に$X$。MC法から総当り。
投稿日:2023422

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

のんびりしようね。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中