Ջրային սափորի խնդիրը AI-ում — Ուսումնասիրություն Python-ով | 2023 թ

Ջրի սափորի խնդրի պարզ ըմբռնում AI-ում | Քարթիքեյան Նագարաջ

Ես հենց նոր հանդիպեցի իմ դասարանում ջրի սափորների խնդրի թեմային և ուզում էի այն կիսել AI մարդկանց համայնքի հետ, որը ներառված է python ծրագրի հետ՝ խնդիրը լուծելու Ընդհանուր ձևով

Խնդիր.

Ձեզ տրվում է 2 սափոր, 4 գալոն և 3 գալոն: Սափորներից և ոչ մեկի վրա Չափիչ նշաններ չկան: Կա պոմպ, որով կարելի է սափորները ջրով լցնել։ Ինչպե՞ս կարող ենք ճիշտ 2 գալոն ջուր ստանալ 4 գալոն սափորում:

Ներածություն:

• Ջրի սափորի խնդիրը արհեստական ​​ինտելեկտի (AI) դասական խնդիր է, որը ներառում է ջրի որոշակի քանակություն չափելու միջոց գտնել՝ օգտագործելով տարբեր հզորություններ ունեցող երկու սափորներ:
• Նպատակը սափորներից մեկում ջրի որոշակի նպատակային քանակի հասնելն է՝ չգերազանցելով դրա տարողությունը՝ ջուրը մի սափորից մյուսը տեղափոխելու միջոցով:
• Այս խնդիրը կարելի է լուծել՝ օգտագործելով պետական ​​տարածքի որոնման ալգորիթմը:

Պետական ​​տիեզերական որոնում.

• Պետական ​​տարածության որոնումը տեխնիկա է, որն օգտագործվում է AI-ում՝ խնդրի լուծումը գտնելու համար՝ փնտրելով խնդրի վիճակի տարածությունը:
• Այս մոտեցման դեպքում խնդիրը ներկայացված է որպես գրաֆիկ, որտեղ հանգույցները վիճակներ են, իսկ եզրերը՝ անցումներ:
• Որոնման ալգորիթմը սկսվում է սկզբնական վիճակից և ուսումնասիրում է գրաֆիկը՝ հասնելու նպատակային վիճակին:
• Ջրի սափորի խնդրի մեջ վիճակի տարածությունը կարող է ներկայացվել որպես բազմակի (x, y), որտեղ x և y-ը երկու սափորների ջրի քանակությունն են:
• Սկզբնական վիճակը (0, 0) է, իսկ նպատակային վիճակն է (x, y) կամ իմ դեպքում դա (2, y) է, որտեղ x-ը և y-ը ջրի ցանկալի քանակներն են:

Արտադրության կանոններ.

Արտադրության կանոնները, որոնք նաև հայտնի են որպես կանոններ կամ էվրիստիկա, օգտագործվում են վիճակի տարածության որոնումների մեջ՝ սահմանելու գործողությունները, որոնք կարող են ձեռնարկվել մի վիճակից մյուսը տեղափոխվելու համար: Ջրի սափորի խնդրի դեպքում կան վեց հնարավոր գործողություն.

1. Լրացրեք առաջին սափորը իր տարողությամբ:
2. Լրացրեք երկրորդ սափորը իր տարողությամբ:
3. Դատարկեք առաջին սափորը:
4. Դատարկեք երկրորդ սափորը:
5. Առաջին սափորից ջուր լցնել երկրորդ կուժը, մինչև կամ առաջին կուժը դատարկվի, կամ երկրորդը լցվի:
6. Երկրորդ սափորից ջուր լցնել առաջին սափորը, մինչև կամ առաջին կուժը լցվի, կամ երկրորդը դատարկվի:

Ալգորիթմ:

Ջրային սափորի խնդիրը լուծելու ալգորիթմը, օգտագործելով պետական ​​տարածության որոնումը, կարելի է ուրվագծել հետևյալ կերպ.

1. Ներկայացրե՛ք խնդիրը որպես վիճակի տարածության գրաֆիկ, որտեղ հանգույցները վիճակներ են, իսկ եզրերը՝ անցումներ:
2. Նախաձեռնեք բաց ցուցակը սկզբնական վիճակով (0, 0):
3. Կրկնեք հետևյալ քայլերը, մինչև բաց ցուցակը դատարկվի.

• ա. Ընտրեք մի պետություն բաց ցուցակից և հեռացրեք այն ցուցակից:
• բ. Եթե ​​պետությունը նպատակային վիճակ է, վերադարձրեք լուծումը։
• գ. Հակառակ դեպքում, արտադրեք բոլոր հնարավոր իրավահաջորդ պետությունները՝ օգտագործելով արտադրության կանոնները և ավելացրեք դրանք բաց ցուցակում, եթե դրանք նախկինում չեն այցելել:

4. Եթե նպատակային վիճակը չի հասնում, վերադարձի ձախողում:

Python ծրագիր՝ խնդիրը լուծելու համար

Ահա Python ծրագիրը, որն իրականացնում է ջրի սափորի խնդիրը լուծելու ալգորիթմը.

def water_jug_problem(capacity1, capacity2, target):
    # initial state (x, y) where x and y are the amounts of water in the two jugs
    state = (0, 0)
    parent = {}
    frontier = [state]
    while frontier:
        state = frontier.pop(0)
        if state == (target, 0) or state == (0, target):
            # goal state reached
            path = [state]
            while state in parent:
                state = parent[state]
                path.append(state)
            path.reverse()
            return path
        x, y = state
        # generate all possible successor states
        states = [(capacity1, y), (x, capacity2), (0, y), (x, 0), (min(x + y, capacity1), max(0, x + y - capacity1)), (max(0, y + x - capacity2), min(y + x, capacity2))]
        for new_state in states:
            if new_state not in parent:
                parent[new_state] = state
                frontier.append(new_state)
    return None

# example
capacity1 = 4
capacity2 = 3
target = 2
path = water_jug_problem(capacity1, capacity2, target)
if path is None:
    print("No solution found.")
else:
    for state in path:
        print(state)

Բացատրություն:

1. Ծրագիրը սկսվում է վիճակի տարածության գրաֆիկը սկզբնական վիճակով (0, 0) և բաց ցուցակը սկզբնական վիճակով:
2. while ցիկլը շարունակվում է այնքան ժամանակ, մինչև բաց ցուցակը դատարկվի կամ հասնի նպատակային վիճակին:
3. Յուրաքանչյուր կրկնության ժամանակ ամենացածր արժեք ունեցող պետությունը հանվում է բաց ցուցակից և ստուգվում նպատակային վիճակի հետ:
4. Եթե ​​դա նպատակային վիճակ է, լուծումը վերադարձվում է որպես վիճակների ցանկ:
5. Եթե ​​նպատակային վիճակը չի հասնում, ծրագիրը ստեղծում է բոլոր հնարավոր հաջորդող պետությունները՝ օգտագործելով արտադրության կանոնները և ավելացնում դրանք բաց ցուցակում, եթե դրանք նախկինում չեն այցելել:
6. Ծնողական բառարանն օգտագործվում է յուրաքանչյուր նոր պետության համար ծնող վիճակին հետևելու համար:

Եզրակացություն:

• Ջրի սափորի խնդիրը կարող է ունենալ բազմաթիվ լուծումներ, և ծրագիրը վերադարձնում է դրանցից մեկը:
• Ալգորիթմի ժամանակային բարդությունը էքսպոնենցիալ է, ուստի մեծ խնդիրների լուծումը գտնելու համար կարող է երկար ժամանակ պահանջվել:
• Այնուամենայնիվ, երաշխավորված է գտնել օպտիմալ լուծում, եթե այդպիսին կա:

Ազատորեն հարցրեք LinkedIn-ի միջոցով և ինձ համար սուրճ գնեք :)

Շնորհակալություն կարդալու համար!!

Happy Programming ~

Author: Karthikeyan Nagaraj ~ Cyberw1ng