Awesome

SapporoTdZddApps

TdZdd と SAPPOROBDD の橋渡しライブラリ

実装予定の機能は下記の通り

• 各種制約下での DD 構築
  • グラフ制約（FrontierBasedSearchWithVetexIndices の焼き直し）
    • s-t パス
    • サイクル
    • 連結成分系（木、森を含む）
      • 単一成分、木
      • 複数成分、森
    • 次数制約
    • シュタイナー制約
  • その他の制約
    • 線形不等式（整数のみ）
  • 関連する機能
    • DdStructure <--> ZBDD の変換
    • DDの変数順序に合わせたグラフデータの取得
    • 辺の順序付けを行う Beam Search（優先度：低）
• SAPPOROBDD の拡張としての新規演算など
  • Power set の作成
  • 特定の部分集合を表すZDDの作成
  • 特定のアイテム集合に着目したZDDへの変換（グラフ制約のZDDから頂点変数だけ抜き出すときなどに便利）
  • 特定のアイテムを含む/含まない（OnSet などの別名）
  • 特定のアイテム間の xor を適用
  • DisjointJoin（優先度：低）
  • JointJoin（優先度：低）
• 最適化
  • 線形最適化のDP
• その他の機能
  • DdStructure の解凍
  • ZBDD の解凍