2

任務の手伝いを求めています。連言正規方程式 (cnf) を解くアルゴリズムを (C で) 書かなければならず、かなりの数時間後にそれを機能させることができません...

私のプログラムはDPLLを実装しています。より正確には、インスタンス化するリテラルを選択した直後に cnf を単純化する部分で、問題が発生します。私は非常に明確であるかどうかわからないので、ここに例を示します:

式 : (a OR b) AND (not-a OR not-b) AND (not-a OR b)

インスタンス化: a=TRUE b=FALSE

この時点で関数 simple を使用すると、(not-a OR b) が満たされなくなるはずですが、すべての節が満たされていることがわかります。

私が定義したデータ型は次のとおりです (管理しやすいように、リテラルには char の代わりに整数を使用しました)。

#define TRUE 1
#define FALSE 0
#define UNDEF -1

typedef int literal;

typedef int* interpretation;

typedef struct node {
    literal lit;
    struct node* next;
} * clause;

typedef struct _formula {
    clause c;
    struct _formula* next;
} * formula;

typedef struct _cnf {
    int nb_lit;
    formula f;
} * cnf;

そして、ここに私の単純化関数があります

void simplify(cnf F, interpretation I) {
  clause pred, curr;
  int skip,b=FALSE;
  formula form, parentForm;
  form = F->f;
  parentForm = form;

  // Iterating through each clause of the formula
  while (form != NULL) {
    curr = form->c;
    pred = curr;
    skip = FALSE;
    while (curr != NULL && !skip) {
      b = FALSE;
      // If a literal appears as true and has benn interpreted as true
      if (curr->lit > 0 && I[curr->lit] == TRUE) {
        // We remove the current clause from the formula
        if (parentForm == form) {
          F->f = form->next;
          free(form);
          form = F->f;
          parentForm = form;
        } else {
          parentForm->next = form->next;
          free(form);
          form = parentForm->next;
        }
        skip = TRUE;
      }
      // Same goes with false
      if (curr->lit < 0 && I[-curr->lit] == FALSE) {
        if (parentForm == form) {
          F->f = form->next;
          free(form);
          form = F->f;
          parentForm = form;
        } else {
          parentForm->next = form->next;
          free(form);
          form = parentForm->next;
        }
        skip = TRUE;
      }

      // However if a literal appears as true and is interpreted as false (or
      // the opposite)
      if (curr->lit > 0 && I[curr->lit] == FALSE) {
        // We remove it from the clause
        if(pred == curr)
        {
          curr = curr->next;
          free(pred);
          form->c = curr;
          pred = curr;
          b=TRUE;
        }
        else
        {
          pred->next = curr->next;
          free(curr);
          pred = curr;
        }
      }
      else if (curr->lit < 0 && I[-curr->lit] == TRUE) {
        if(pred == curr)
        {
          curr = curr->next;
          free(pred);
          form->c = curr;
          pred = curr;
          b=TRUE;
        }
        else
        {
          pred->next = curr->next;
          free(curr);
          pred = curr;
        }
      }

      pred = curr;
      if(!b) curr = curr->next;
    }
    parentForm = form;
    if(!skip) form = form->next;
  }
}

長いコードで申し訳ありません。どの重要な部分に注目すべきか正確にはわかりません。完全ではないメモリの解放など、他にもいくつかの問題が残っていることを私は知っています（私は思う）。

それとは別に、問題をデバッグしようとしているときにいくつかのエラーを見つけましたが、古いものを修正しながら新しいものを作成しているような気がします:/

誰かがこれについて私を助けることができるなら、前もってThx！また、重要な場合は、Windows 10 を使用しており、cygwin を介して gcc でコンパイルしています。

gcc *.c

4

1 に答える 1

1

また、重要であれば、私はWindows 10を使用しており、cygwinを介してgccでコンパイルしています

実はそうでした…以前に確認しなかったこととは何の関係もないだろうと確信していました。

とにかく、Linux システムで試してみましたが、一見すると問題なく動作するように見えます。

ご不便おかけしてすみません

于 2016-04-04T18:37:35.350 に答える