3

変数classes（〜100）、rooms（20）、terms（8）、およびweekdays（5）で構成される古典的なタイムテーブルの問題があります。

問題を単純化するために、以下に制約を減らします。

1日は9時間です。

一部のクラスは学生に必須であり、用語1、3、5、7（および2、4、6、8）の必須クラスは互いに重複してはなりません。

クラスの重みは時間で異なり、2時間のものもあれば、3時間のものもあります。

一部のクラスは特定の部屋で行う必要があります。

同じクラスで同時に2つの講義を行うことはできません。

logilabspython制約モジュールを使用します。また、変数とドメインを適切に選択すると、問題を解決するための時間が短縮されることを認識しています。問題は、これまで制約プログラミングを行ったことがなく、どこから何から始めればよいかを見つけるために問題を構築するのに苦労していることです。例えば：

「同じ部屋に2つのクラスがなく、同じ日にお互いの時間枠が重なることはありません」などの制約を設定できます。または、「同じ日に9時間以上予約できる部屋はない」から始めて、ソリューションドメインを減らして続行します。私は、最初の制約が他の制約よりも解決にはるかに長い時間がかかると見積もっています（試していませんでした）。しかし、それはまた（私が推測する）変数とソリューションドメインの変更またはより小さな問題の再構築を必要とします。私はすでに変数、ドメイン、間隔、実装などで少し迷っています。

簡単に言えば、問題を構築するためのいくつかのポインタ、ソリューションドメイン、変数の賢明な選択などが必要です。

ありがとう

アップデート

logilab-constraintパッケージを使用して、基本的なアプリケーションを作成し、それをgithubにアップロードしました

4

2 に答える 2

1

DroolsPlannerのカリキュラムコースのサンプルコードをご覧ください。基本的には同じですが、用語が少し異なります。各コース（=クラス）には、部屋（=部屋）と期間（=各平日の各用語は期間）にスケジュールする必要のある講義がいくつかあります。

秘訣は、クリーンなドメインモデルを維持し、それを制約ルールから分離しておくことです。クラスの重みは時間で異なるため、aLectureにのみ割り当てられることをお勧めします。startingPeriodしたがって、講義を別の期間のセットに移動するためのコードはそれほど多くありません（最初の期間を再割り当てするだけです）。

于 2011-05-08T13:46:47.277 に答える
-1

最終的に、「変数を賢く選択する」ことと「選択時にドメインを減らす」ことをバンドルしたソリューションになりました。以下は、私が行っているdjangoベースのタイムテーブルアプリケーションのスニペットです。

class Course(models.Model):
    name = models.CharField(max_length=255, null=False, blank=False)
    duration = models.PositiveSmallIntegerField(blank=False)
    type = models.ForeignKey(CourseType, blank=False, null=False)
    mandatory = models.BooleanField(default=False)
    '''
        following are the basic constraints  
    '''
    days = models.ManyToManyField(Day, blank=True, null=True)
    terms = models.ManyToManyField(Term)
    rooms = models.ManyToManyField('ClassRoom', blank=True, null=True)


    def __unicode__(self):
        return u'%s' % self.name

「このコースは月曜日または火曜日、部屋1または2または3または4または5の1または2または3である可能性があります」などの基本的な制約をクラスに埋め込んだので、これらの基本的な制約を直接適用できます。データベースからコースを選択するときの最初の制約。

「同じ日の同じ時間帯に2つのコースを同じ部屋に置くことはできない」などの一般的な制約は、データベースで行われた選択から生じる削減された可変ドメインに適用されます。

今のところ機能しているようです。

于 2011-05-11T11:37:48.413 に答える