Đăng nhập | Đăng ký

Danh sách thành viên | Cá nhân | Nhà đất, bất động sản

Diễn đàn    Window Form programming    Các giải thuật xếp thời khoá biểu đại học

Thành viênNội dung
khanhjin

khanhjin
17  bài
14-05-2009 02:25:18
Tìm kiếm địa phương
Bài toán xếp lịch thuộc lớp các bài toàn NP-complete. Không thể tìm kết quả tối ưu.
Hàm mục tiêu
Ràng buộc
một tập hợp các biến số
thỏa mãn phương trình, bất phương trình.
Tìm kiếm địa phương (Local Search)

Các bài toán kinh điển
Bài toán 8 con hậu (n hậu)
Tô màu bản đồ (graph coloring)
SEND MORE MONEY
Sodoku
Xếp lịch
TKB
Làm việc
Máy bay

Simulated annealing
Process annealing
Mục tiêu dựng thanh đao đúng hình dạng đủ bền vững
Phương pháp: nung nóng chảy, và tôi thép thành hình thanh đao, rồi làm nguội = nước.
Khi tôi 1 lần thanh đao sẽ rất giòn, nếu quá trình tôi thực hiện nhiều lần (nung nóng, tôi hình, làm nguội) thanh đao sẽ thỏa mãn các ràng buộc
Các kết quả sau tốt hơn các kết quả trước, nhiệt độ nung của các lần sau sẽ giảm dần.

Thuật toán di truyền
Dựa trên lý thuyết di truyền của Darwin
Cá thể mạnh tồn tại, cá thể yếu chết
Mama và papa gặp nhau (2 cá thể mạnh gặp nhau)
Chung sống với nhau và sinh ra 1 cá thể con mới (có bộ gen khỏe = gen papa + gen mama) đồng thời chết đi 1 cá thể yếu.
Do 1 sinh 1 mất nên tổng số cá thể bảo toàn trong mỗi chu kỳ sinh nở.
Sau nhiều chu kỳ sinh nở các cá thể còn tồn tại là các cá thể có bộ gen rất mạnh (kết quả rất tối ưu thỏa mãn các ràng buộc)
Tô màu đồ thị
Bài toán: mỗi nước trên bản đồ thế giới tô = 1 màu, các nước gần nhau có màu # nhau.
Áp dụng tốt nhất cho TKB
Mỗi màu là một sự kiện
Tô màu vào bảng thời gian mỗi người sao cho các sự kiện (màu) chỉ suất hiện 1 lần
Tabu Search
Ý tưởng chính là tạo một bộ khóa.
Trong quá trình tìm kiếm kết quả chúng ta thường gặp tình huống kết quả lần trước và lần sau là giống nhau.
Chương trình tìm kiếm sẽ rơi vào vòng lặp vô hạn.
Để tránh vòng lặp vô hạn và có kết quả tốt hơn chúng ta sử dụng Tabu

Mô hình hóa
Sự kiện là một nhóm sinh viên học một môn học duới sự giảng dạy của một giáo viên tại một phòng
Nếu coi bảng thời gian của giáo viên, phòng, lớp, sinh viên là các bảng 2 chiều mxn.
Xếp lịch là hành động xếp các sự kiện vào các ô trống thời gian, đảm bảo các ràng buộc
Bài toán TKB
Không giáo viên, phòng, sinh viên .. Cùng thời gian có 2 sự kiện.
Độ khó của bài toán phụ thuộc vào các chiều giáo viên, phòng học, sinh viên, lớp …
Giải pháp chung
Tìm kiếm phương án khởi tạo Init
Từ phương án khởi tạo, tìm các kết quả mới tốt hơn dựa trên các thuật toán có sẵn hoặc lai ghép các thuật toán.
Tìm kiếm địa phương sử dụng phương pháp tính trước hậu quả để dự đoán kết quả sau có tốt hơn không?
Tín chỉ
Bài toán 1 : xếp lịch học tín chỉ trước, sau đó xếp SV vào các lớp.
Đơn giản dễ viết ít ràng buộc
Một số SV không được chấp nhận lựa chọn của mình vì không còn lớp
Bài toán 2 : Xếp lịch học sau khi SV đăng ký
Khó phức tạp vì nhiều ràng buộc
Có thể nảy sinh trường hợp không tìm ra kết quả
 
myvan09


2  bài
02-06-2009 02:52:29
ua, may bai mau dau rui ong anh
---
 
vu282909


1  bài
15-12-2009 08:06:40
Tìm kiếm địa phương
Bài toán xếp lịch thuộc lớp các bài toàn NP-complete. Không thể tìm kết quả tối ưu.
Hàm mục tiêu
Ràng buộc
một tập hợp các biến số
thỏa mãn phương trình, bất phương trình.
Tìm kiếm địa phương (Local Search)

Các bài toán kinh điển
Bài toán 8 con hậu (n hậu)
Tô màu bản đồ (graph coloring)
SEND MORE MONEY
Sodoku
Xếp lịch
TKB
Làm việc
Máy bay

Simulated annealing
Process annealing
Mục tiêu dựng thanh đao đúng hình dạng đủ bền vững
Phương pháp: nung nóng chảy, và tôi thép thành hình thanh đao, rồi làm nguội = nước.
Khi tôi 1 lần thanh đao sẽ rất giòn, nếu quá trình tôi thực hiện nhiều lần (nung nóng, tôi hình, làm nguội) thanh đao sẽ thỏa mãn các ràng buộc
Các kết quả sau tốt hơn các kết quả trước, nhiệt độ nung của các lần sau sẽ giảm dần.

Thuật toán di truyền
Dựa trên lý thuyết di truyền của Darwin
Cá thể mạnh tồn tại, cá thể yếu chết
Mama và papa gặp nhau (2 cá thể mạnh gặp nhau)
Chung sống với nhau và sinh ra 1 cá thể con mới (có bộ gen khỏe = gen papa + gen mama) đồng thời chết đi 1 cá thể yếu.
Do 1 sinh 1 mất nên tổng số cá thể bảo toàn trong mỗi chu kỳ sinh nở.
Sau nhiều chu kỳ sinh nở các cá thể còn tồn tại là các cá thể có bộ gen rất mạnh (kết quả rất tối ưu thỏa mãn các ràng buộc)
Tô màu đồ thị
Bài toán: mỗi nước trên bản đồ thế giới tô = 1 màu, các nước gần nhau có màu # nhau.
Áp dụng tốt nhất cho TKB
Mỗi màu là một sự kiện
Tô màu vào bảng thời gian mỗi người sao cho các sự kiện (màu) chỉ suất hiện 1 lần
Tabu Search
Ý tưởng chính là tạo một bộ khóa.
Trong quá trình tìm kiếm kết quả chúng ta thường gặp tình huống kết quả lần trước và lần sau là giống nhau.
Chương trình tìm kiếm sẽ rơi vào vòng lặp vô hạn.
Để tránh vòng lặp vô hạn và có kết quả tốt hơn chúng ta sử dụng Tabu

Mô hình hóa
Sự kiện là một nhóm sinh viên học một môn học duới sự giảng dạy của một giáo viên tại một phòng
Nếu coi bảng thời gian của giáo viên, phòng, lớp, sinh viên là các bảng 2 chiều mxn.
Xếp lịch là hành động xếp các sự kiện vào các ô trống thời gian, đảm bảo các ràng buộc
Bài toán TKB
Không giáo viên, phòng, sinh viên .. Cùng thời gian có 2 sự kiện.
Độ khó của bài toán phụ thuộc vào các chiều giáo viên, phòng học, sinh viên, lớp …
Giải pháp chung
Tìm kiếm phương án khởi tạo Init
Từ phương án khởi tạo, tìm các kết quả mới tốt hơn dựa trên các thuật toán có sẵn hoặc lai ghép các thuật toán.
Tìm kiếm địa phương sử dụng phương pháp tính trước hậu quả để dự đoán kết quả sau có tốt hơn không?
Tín chỉ
Bài toán 1 : xếp lịch học tín chỉ trước, sau đó xếp SV vào các lớp.
Đơn giản dễ viết ít ràng buộc
Một số SV không được chấp nhận lựa chọn của mình vì không còn lớp
Bài toán 2 : Xếp lịch học sau khi SV đăng ký
Khó phức tạp vì nhiều ràng buộc
Có thể nảy sinh trường hợp không tìm ra kết quả
 

Chủ đề gần đây :

Cùng loại :

 
Tên file Người đăng Ngày Lượt
WebApplication1.rar
Sample su dung thuat toan ma hoa tripDES, co khoa bi mat (privateKey)
aspnet 3/30/2018 10:06:35 PM 2
NETMdbToolsTestApp.rar
dotNet MdbTools for Access 2003/2007/2016 without Microsoft Jet Engine, source C#, https://www.codeproject.com/Articles/283626/MsAccess-MdbTools-with-MFC-and-NET
aspnet 3/26/2018 11:43:16 PM 0
Cryptography_MD5_TriDES_src.zip
Thuật toán mã hóa 2 chiều TriDES, gồm Encrypt và Decrypt, aspnet 2.0
aspnet 3/22/2018 11:20:44 AM 0
mvc.rar
sample project MVC on C#
aspnet 3/20/2018 9:25:36 AM 0
EduPortal.rar
Edu portal frame work for VB.NET
aspnet 3/14/2018 12:00:41 AM 4
AutoEntity.rar
Gencode vb.net visual studio 2015. dotnet v2.0
aspnet 3/13/2018 11:59:16 PM 1
GenCode.rar
Gencode XML, XSLT, Info, DAL .. engine enterprise for quick app database
aspnet 2/5/2018 9:37:28 AM 7
DataXml.rar
Read DB from SQL to XML file, Convert string TCVN to Unicode
aspnet 1/29/2018 2:15:45 PM 3
DesktopModules.rar
Module quản lý tin tức, CMS, quản lý nhóm tin trên dotnetnuke 6.x
aspnet 3/7/2013 4:47:49 PM 1690
News Ticker Demo.rar
jQuery Carousellite cho cuộn các khối tin nhẹ nhàng mượt mà, sử dụng cho module Tin tức (CMS) hoặc giới thiệu sản phẩm
aspnet 5/7/2011 8:59:52 AM 1110
cms_source_dll_sql_2010.rar
source C# + SQL Script + Dll module CMS trên DNN 5x, (bản chạy ổn định không lỗi)
aspnet 9/5/2010 6:05:54 PM 2881
killforever.rar
Script diệt virus forever.exe (lây nhiễm qua USB) mà không cần cài lại window
aspnet 7/28/2010 6:51:30 AM 410
CSharp Coding Standards.pdf
C# Coding standard, for all user, quy tắc viết mã lập trình c# dotnet.
aspnet 6/1/2010 8:27:39 AM 1874
weather_forex_gold.rar
module DNN : "vàng + thời tiết + tỷ giá ngoại tệ" của seekill
coder 3/11/2010 3:50:09 AM 1669
Training DotNetNuke.zip
Tài liệu hướng dẫn cài đặt DNN, tạo module DNN đơn giản, nâng cao
quanlv 9/30/2009 9:11:36 AM 4457
Viet va them 1 module don gian vao website.doc
Hướng dẫn viết module đơn giản trên DNN (word) có hình, gửi bởi vinahana
aspnet 9/18/2009 6:15:24 PM 2097
Moduel NEWs Demo.zip
Một số module bao gồm: News, WorkScheduler, QA, Comment, Menu, ...
quanlv 8/22/2009 10:44:15 AM 3794
MenuDNN5.rar
Menu DNN 51 Page.aspx
aspnet 7/21/2009 12:22:38 PM 2610
diendan.zip
Cài đặt diễn đàn (VSP) chỉ với 4 bước.
aspnet 6/15/2009 2:18:13 AM 2005
roll_updown.zip
Roll up, roll down news list using javascript, simple, easy to use.
radiogaga 6/1/2009 11:29:51 AM 585
CODERVN.NET
Công ty cổ phần công nghệ và dịch vụ AWAS
Công ty cổ phần công nghệ và dịch vụ AWAS, cổng thông tin, chính phủ điện tử, phần mềm quản lý điểm, quản lý sinh viên, http://awas.vn, http://awas.com.vn, phần mềm ứng dụng, dịch vụ công trực tuyến, thiết kế website, thiet ke web, thiết kế web, điện lực, phần mềm quản lý đào tạo, cao đẳng, đại học,cổng thông tin tích hợp, cổng thông tin điện tử, webportal, thư viện điện tử, electric library, library online, email, web, quản lý quan hệ khách hàng, CRM, dịch vụ công trực tuyến, phần mềm hành chính một cửa,