Thuật toán của người mất trí nhớ

Có một bài toán “khá đơn giản” sau về vấn đề thuật toán, tôi biết chắc chắn là giải được (vì có định lý về vấn đề này), có điều tôi thử tự tìm lời giải mà loay hoay mãi chưa ra:

Có một người ở một làng bị mất trí và được cho vào bệnh viện của làng. Người này trốn viện đi về nhà. Người này nếu nhìn thấy nhà mình thì sẽ nhớ ra đó là nhà của mình, nhưng không biết đường đi về nhà, và chỉ nhớ được rất ít, vài thông tin thôi, còn lại có đi qua một phố nào rồi một lúc sau đến lại phố đó thì sẽ không nhớ là đã đi qua nó hay chưa. Hỏi làm sao có một thuật toán nào (đến các ngã phố thì rẽ như thế nào), để cho người này chắc chắn đi được về đến nhà mình. (Đây là người mất trí nhớ chứ không phải người say, và thuật toán là xác định chứ không phải là ngẫu nhiên) ?

Có ai có cách làm “sơ cấp” nào chỉ giùm với !

 

Print Friendly

12 comments to Thuật toán của người mất trí nhớ

  • Thanh Hậu MonsterID Icon Thanh Hậu

    Em không có học toán nhưng đọc thì thấy bài này hình như có liên quan đến k means ++

  • Bài toán của thầy hay, nhưng các giả thiết đều chưa chặt với các điều kiện rõ ràng thì không thể nào có lời giải được ngoài cứ random exploration thôi thầy ah. Thầy phải nói rõ, map loại thế nào, rộng bao nhiêu, dài bao nhiêu; điều kiện của việc Nhớ (trong bao lâu), có bao nhiều landmarks biết trước và bố trí của lanmarks như thế nào (vì nếu các lanmarks phân bố phù hợp để giúp người này cứ theo landmarks đi từ initial to goal thì bài toán coi như đã có lời giải :-))

    Bài toán này rất giống các vắn đề của mobile robots. Cụ thể:
    1- Trong một unknown map giống trong thành phố hay building (đường đi chỉ trong dạng I, L, T forms), kick thức L x W
    2- Cho biết vị trí của initial và goal trên map đó
    3- The robot có sensing range, rc
    4- The robot có khả năng nhớ một số lượng lanmarks trong N bước (hoặc trong quãng đường L)

    Bài toán của thây là tìm giải pháp path planning tối ưu nhất để robot có thể đi từ initial to goal? Nếu vậy thì chẳng phải là bài toán dễ đầu thầy ah. Rất khó đằng khác và cái ông mất tri nhớ đó mà không ăn no trước khi xuất phát thì chắc chắn toi trên đường ngay vì rất nhiều quá trình random ở đây.

    Bài toán của thầy có thể đưa giải thiết hơi khác môt chút là môt số landmarks biết trước và ở mỗi landmarks thì robot biết hướng đi tiếp theo. Nếu vậy thì có thể dễ hơn, những cũng cần phải quan tâm giả thiết 3 va 4 thì mới biết có cách nào để giải quyết được không.

    Có bạn nào đã nói đến BFS and DFS rồi đấy, tuy nhiều cả hai cái đó đều phải có điều kiện của việc phải có khả năng nhớ với một số lượng nhất định trong một khoảng thời gian nhất định.

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  

  

  

This blog is kept spam free by WP-SpamFree.