User Tag List

+ Trả lời chủ đề
Trang 1/2 12 CuốiCuối
Hiện kết quả từ 1 tới 10 của 16

Chủ đề: Thuật toán tối ưu

  1. #1
    CNNer-Amser-HUTer Avatar của Binhjuventus™
    Tham gia ngày
    Sep 2003
    Bài gửi
    570

    Mặc định Thuật toán tối ưu

    Đã lâu lắm rồi không đụng chạm vào vấn đề này, nay mình gặp phải nên cũng muốn trao đổi với các bạn.

    Cái này đặt vào phần ngôn ngữ C/C++ cũng tạm hợp lý vì ngôn ngữ này được sử dụng để mô tả thuật toán rất tốt.

    Bài toán: Một tòa nhà có N tầng (N>=5). Để đi từ tầng (i) lên tầng (i+1), thang máy mất 2 đơn vị năng lượng trong khi ngược lại, đi từ tầng (i+1) xuống tầng (i), thang máy chỉ mất 1 đơn vị năng lượng.

    Cho biết vị trí ban đầu của thang máy là M (1<= M <= N). Hãy tìm thuật toán cho thang máy sao cho tỉ số (path/energy) với một hành trình của thang máy là tối ưu.

    Biết rằng một đơn vị hành trình là một hành trình đi lên hay xuống tầng kế. Một hành trình bao gồm tổng các đơn vị hành trình từ lúc nhận lệnh (số lệnh được hạn chế ở 10) cho đến khi thực hiện hết các lệnh.

    Bài toán này mình được hỏi trong một lần phỏng vấn xin việc. Vấn đề ở đây tất nhiên là vấn đề tư duy thuật toán và giới hạn thời gian. Tuy nhiên giả định các bạn có quỹ thời gian vô hạn, các bạn có thể tìm kiếm được một giải thuật tối ưu cho bài toán này hay ko? Bài này có tính trao đổi là nhiều, nhất là các bạn học CNTT (mình ko có background IT) khi học về giải thuật và tối ưu.

    Notes: Trên thực tế, bài toán tối ưu còn phức tạp hơn vì tại các tòa nhà, số lượng thang máy thường nhiều, khoảng 3-6 thang máy (elevator group problem).

  2. Có 2 thành viên cảm ơn bài viết của Binhjuventus™ có chất lượng:


  3. #2
    .:: Grumpy svBKer ::. Avatar của 1973
    Tham gia ngày
    Mar 2010
    Bài gửi
    3.793

    Mặc định Re: Thuật toán tối ưu

    Ui, em đọc mãi mà vẫn chưa hiểu đề bài anh ạ
    Contact me:
    Email: sangnd [at] svBK.vn
    Personal website: My Blog | Chat với người lạ
    Facebook Page của Bách Khoa Forum: http://www.facebook.com/svbk.vn

  4. #3
    Khánh Hòa
    Tham gia ngày
    Apr 2010
    Bài gửi
    159

    Mặc định Re: Thuật toán tối ưu

    Mình nói rõ đề hơn cho anh em. Có k(k<10) người Đang ở tầng thứ M của tòa nhà. Họ cùng vào thang máy và muốn tới các tầng khác nhau của tòa nhà. Yêu cầu là hãy tìm hành trình tới các tầng sao cho chi phí về năng lượng là thấp nhất

  5. #4
    CNNer-Amser-HUTer Avatar của Binhjuventus™
    Tham gia ngày
    Sep 2003
    Bài gửi
    570

    Mặc định Re: Thuật toán tối ưu

    Đúng là bài toán chưa đủ dữ liệu để chúng ta thảo luận.

    @1973: Anh lấy ví dụ, thang máy ở tầng 3, cùng lúc ở tầng 5 và 2 đều có lệnh gọi với giả định người ở tầng 2 sẽ lên tầng 4 và người tầng 5 sẽ xuống tầng 1. Khi nhận lệnh gọi, thang máy đã biết sẽ trả người ở tầng nào. Hành trình được cho là tối ưu sẽ như sau:
    - Thang máy xuống tầng 2 (+1 vào giá trị path, +1 vào giá trị năng lượng)
    - Thang máy lên tầng 4 và trả người (+2 vào giá trị path và +4 vào giá trị năng lượng)
    - Thang máy lên tầng 5 đón người (+1 vào giá trị path, +2 vào giá trị năng lượng)
    - Thang máy xuống tầng 1 (+5 vào giá trị path và +10 vào giá trị năng lượng)
    PATH = 9
    Energy = 17

    @khanhoatink4: Cách hiểu của bạn là một cách và nó đơn giản hóa bài toán cần thực hiện.

    Tuy nhiên còn có một cách khác (là cách mà người phỏng vấn mình nêu ra ví dụ), theo cách này, thang máy sẽ thực hiện hành trình đón (những người ở các tầng khác nhau cùng gọi thang máy - giả định) và hành trình đưa (trả người trong thang máy ở hành trình đón đúng tầng yêu cầu). Cách hiểu này khiến bài toán gần với thực tế hơn nhưng bị một giả định phi thực tế là có một tập lệnh gọi cùng một lúc ở tất cả các tầng và thang máy biết trước lệnh yêu cầu của mỗi tầng gọi.

    Dữ liệu đầu vào có thể ở dạng
    M N
    (i, j)

    M là vị trí thang máy
    N là số tầng của tòa nhà
    Dòng thứ i
    - i=0 tương ứng với ko có lệnh gọi, i = 1 tương ứng với có lệnh gọi
    - j: Tầng sẽ gọi đến

    Đầu ra:
    PATH
    ENERGY
    danh sách hành trình

  6. Có 2 thành viên cảm ơn bài viết của Binhjuventus™ có chất lượng:


  7. #5
    Khánh Hòa
    Tham gia ngày
    Apr 2010
    Bài gửi
    159

    Mặc định Re: Thuật toán tối ưu

    ở đây energy phải là 12 chứ a. khi từ tầng 5->1 mấy 5 năng lượng

  8. #6
    Khánh Hòa
    Tham gia ngày
    Apr 2010
    Bài gửi
    159

    Mặc định Re: Thuật toán tối ưu

    theo đề bài là tỷ số path/energy là tối ưu nhất(e không biết là tỷ số này lớn nhất hay là nhỏ nhất ạ) theo phương pháp tối ưu anh đưa ra thì e thấy tỷ số này là lớn nhất

  9. #7
    .:: Grumpy svBKer ::. Avatar của 1973
    Tham gia ngày
    Mar 2010
    Bài gửi
    3.793

    Mặc định Re: Thuật toán tối ưu

    Công nhận là chưa biết được tỉ số path/energy như thế nào gọi là tối ưu. Ví dụ với cùng 1 dữ liệu vào, một giải thuật cho ra tỉ số này là 4/8, một giải thuật khác cho ra tỉ số này là 5/10. Như vậy 2 tỉ số này là bằng nhau, tuy nhiên rõ ràng giải thuật đầu tiên là tối ưu hơn giải thuật thứ 2 vì đi ít hơn và tốn ít năng lượng hơn (mặc dù 2 tỉ số này bằng nhau)

    @ Anh Bình: phải có 1 chuẩn thế nào đó gọi là tối ưu chứ anh? Nếu không thì đề vẫn hơi mơ hồ

  10. #8
    CNNer-Amser-HUTer Avatar của Binhjuventus™
    Tham gia ngày
    Sep 2003
    Bài gửi
    570

    Mặc định Re: Thuật toán tối ưu

    thực ra thì đường đi mà dài thì không chắc đã tiêu thụ ít năng lượng. Ở bài toán này, người phỏng vấn anh sử dụng từ minimize this ratio. Thế thì trước hết là chúng ta tìm hành trình có tỉ số này nhỏ nhất đi!

    Energy trong ví dụ đúng là 12 chứ ko phải 17, cái này thì anh bị nhầm lẫn

  11. #9
    .:: Grumpy svBKer ::. Avatar của 1973
    Tham gia ngày
    Mar 2010
    Bài gửi
    3.793

    Mặc định Re: Thuật toán tối ưu

    Quote Nguyên văn bởi khanhoatink4 Xem bài viết
    ở đây energy phải là 12 chứ a. khi từ tầng 5->1 mấy 5 năng lượng
    Thật ra phải là 11, từ 5 --> 1 chỉ mất có 4 thôi .

  12. #10
    Khánh Hòa
    Tham gia ngày
    Apr 2010
    Bài gửi
    159

    Mặc định Re: Thuật toán tối ưu

    nếu đi theo hướng ngược lại, 3>5>1>2>4 thì path=11 và energy=17, tỷ số này tối ưu hơn chứ nhỉ

+ Trả lời chủ đề
Trang 1/2 12 CuốiCuối

Thông tin chủ đề

Users Browsing this Thread

Hiện có 1 người đọc bài này. (0 thành viên và 1 khách)

Chủ đề tương tự

  1. [Hỏi đáp] Sự khác nhau giữa hệ cử nhân kĩ thuật và kĩ sư kĩ thuật
    Gửi bởi spiderman trong mục For Teen - THPT
    Trả lời: 35
    Bài cuối: 04-10-2012, 08:00 PM

Từ khóa (Tag) của chủ đề này

Quyền viết bài

  • Bạn không thể gửi chủ đề mới
  • Bạn không thể gửi trả lời
  • Bạn không thể gửi file đính kèm
  • Bạn không thể sửa bài viết của mình


About svBK.VN

    Bách Khoa Forum - Diễn đàn thảo luận chung của sinh viên ĐH Bách Khoa Hà Nội. Nơi giao lưu giữa sinh viên - cựu sinh viên - giảng viên của trường.

Follow us on

Twitter Facebook youtube