Algoritma okulu bir takvim oluşturmak için

SORU

1 ŞUBAT 2010, PAZARTESİ

Algoritma okulu bir takvim oluşturmak için

Eğer okul bir takvim oluşturma algoritması için çözüm belli olup olmadığını merak ediyordum. Temel olarak, en iyi duruma getirme "saat dağılımı" (hem öğretmenler hem de sınıflar halinde)-konu sınıf-öğretmen dernekleri verildi. Giriş dersleri, ders konuları ve öğretmenler birbirleri ile ilişkili ayarlar ve zaman çizelgesi sabah 8 ve akşam 4 arasında uygun olmalıdır varsayabiliriz.

Muhtemelen bunun için doğru algoritma yok sanırım, ama belki birisi iyi bir yaklaşım biliyor ya da onu geliştirmek için ipuçları.

CEVAP

1 ŞUBAT 2010, PAZARTESİ

Bu sorunNP-Complete!
Özetle tek kabul edilebilir çözümler listesini bulmak için tüm olası kombinasyonları keşfetmek gerekiyor. Bu sorunun çeşitli okullarda görünür koşullarda varyasyonları (örneğin: sınıflar ile ilgili kısıtlamalar mı?, var çünkü Sınıfların alt grupları biraz zaman?, bölünmüş bazılarıdır Bu haftalık bir program mı? vb.) tüm zamanlama sorunlarına karşılık bir iyi bilinen bir sınıf sorunu yok. Belki, Knapsack problem geniş bu sorunlar ile benzerlik birçok unsur vardır.

Bu hem zor bir sorun olduğunu ve insanlar kalıcı bir çözüm aramak tek bir onay, bu (uzun) list of (mostly commercial) software scheduling tools kontrol etmektir

En büyük kaynağı, genellikle, öğretim üyesinin istediği değişkenleri dahil, büyük sayıda nedeniyle ;-)..., bu genelliklepratik tüm olası kombinasyonları numaralandırma düşünün. Yerine/çözüm alanlarda sorun kümesini ziyaret eden bir yaklaşım seçmeniz gerekir.
-Genetik Algoritmalarbaşka bir atıf (ya da, ne DEMELİ . cevap ^em>görünüyoriyi yarı-güdümlü bu tür bir arama gerçekleştirmek için donanımlı (adaylar bir sonraki nesil için tutulması için sorun iyi bir değerlendirme fonksiyonu bulmak için)
- Graph Rewriting yaklaşımlar da tümleşik optimizasyon problemleri bu tip kullanın.

Otomatik zamanlama jeneratörü programı belli uygulamaları odaklanmak yerine, tavsiye ederimuygulanabilecek bazı stratejiler,sorun tanımı seviyesinde.
Genel gerekçe en gerçek dünya planlama sorunları, bazı tavizler gerekli olacak, tüm kısıtlamalar, ifade ve ima: tam. tatmin olacak Bu nedenle kendi kendimize yardım ediyoruz:

Ve bilinen tüm tanımlama sıralama kısıtlamaları
Sorunu azaltmak boşluk, el ile, bir dizi sağlarekkısıtlamaları.
Bu görünse de mantıksız ama örnek sağlayan bir başlangıç, kısmen dolu çizelgesi (yaklaşık 0 zaman dilimi), bir şekilde tam olarak karşılayan tüm kısıtlamalar ve dikkate bu kısmi zamanlama değişmez, biz önemli ölçüde azaltmak, zaman/mekan ihtiyacı için aday çözümler üretmek.
Başka bir yol ek kısıtlamalar yardımcı olur örneğin "yapay" ekleme kısıtlaması olan öğretim engellemek için bazı konularda bazı günler bu hafta (eğer bu bir haftalık program...); bu tip kısıtlamalar sonuçları azaltmak sorunu/çözümü boşluk olmadan, genellikle, dahil olmayan önemli sayıda iyi adaylar.
Sorunun kısıtlamaları bazı sağlamaktan hızlı bir şekilde hesaplanabilir. Bu genellikle veri sorunu göstermek için kullanılan bir model seçimi ile ilişkilidir, bu fikri hızlı bir şekilde-tercih (veya erik) bazı seçenekler edebilmek için.
Sorunu tanımlama ve kısıtlamalar bazı bozulmak için izin, birkaç kez (genellikle sonuna doğru grafik düğümleri). Burada fikir ya da kaldırmaktırbazıkısıtlamaları dolum-son birkaç yuva zamanlama, yoksa otomatik zamanlama generator program durdurmak utangaç tamamlanması bütün program, yerine sağlamak bizim listesi ile bir düzine kadar makul aday. Bir insan genellikle daha iyi bir pozisyon için tam bir bulmaca, belirtildiği gibi, muhtemelen kırma bir kaç kısıtları kullanarak bilgi yok genellikle paylaşımlı ile otomatik mantık (örneğin "Hayır matematik öğleden sonra" yönetecek biri kırık durumda "ileri düzey matematik ve fizik" sınıfı ya da "olur daha sonra aradan bir Bay Jones gereksinimleri daha bir Ms Smith ... ;-) )

Prova-okuma bu cevap , kesin bir yanıt sağlayarak oldukça utangaç olduğunu biliyorum ama bu hiç pratik öneriler daha az tam. Bu ne ile yardım, umarım, bir "zor sorun".

Bunu Paylaş: